第一天:
DFS枚举-01枚举
01DFS---是一种处理每个元素有“选”或“不选”两种状态的递归算法
通过深度优先遍历所有可能的选择组合,枚举所有子集,
并根据问题目标(计数、最值、可行性等)统计或优化结果。
O(2^n)
优先考虑 01DFS:
1.元素数量少:n≤20
2.二元选择:每个元素仅有“选”或“不选”两种独立状态(无顺序依赖)
3.目标明确:需统计满足条件的子集数(计数)、求最优子集(最值)、判断是否存在可行子集(可行性)等。
01枚举模板:
DFS枚举-排列枚举
1. 多选择枚举:每阶段不止“选/不选”,而是有k(k≥2)种选择(如T76854每个位置选a/b/c,T76855每人选1~a[i]份)。
2. 带约束枚举:选择需满足额外条件(如T76858八皇后“行列对角线唯一”)。
3. 目标多样:输出所有合法方案(按字典序)、输出前m个解、统计解的总数等。
排列枚举模板:
第二天:
Meet in the middle 折半搜索
DFS综合应用
第三天:
连通块&&深度优先搜索
方向数组 - DFS
邻接矩阵 - DFS
第四天:
BFS/DFS综合应用
第五天:
广度优先搜索---邻接表
map容器---字典:键值对
map<string,int>
第六天:
广度优先搜索---迷宫
迷宫问题BFS
多源最短路
第七天:
树的路径
树的深度
树的宽度:桶标记---记录每一层有多少个节点---找最多的那一层的个数
第八天:
树的子树大小
树的子树个数
第九天:
拓扑排序的模板
拓扑排序---判环
拓扑排序---反向建图
__int128 128位整数 10^38