从很久以前的洛谷讲课课件搬了过来
题单
1.dfs
\(dfs\)是一种用于遍历整个图或树和枚举各种状态的算法，核心思路就是不断利用递归函数调用自身，沿着一条路走到底，走到头后再回来走另一条路。
大致结构：
dfs(v) // v 可以是图中的一个顶点，也可以是抽象的概念，如 dp 状态等。在 v 上打访问标记for 枚举状态dfs(u)end
end
例：P2585 三色二叉树
设 \(f_1[i][0/1/2]\)表示以\(i\)为根，将\(i\)染成绿色（\(0\)）/红色（\(1\)）/蓝色（\(2\)），\(i\)及其子节点最多能染成绿色的点的个数，\(f_2[i][0/1/2]\)相反。
分三种情况：
当\(i\)子节点个数为\(0\)时，直接把\(f_1[i][0]\)和\(f_2[i][0]\)打上标记即可。
当\(i\)子节点个数为\(1\)时：
\(f_1[i][0]=max(f_1[i+1][1],f_1[i+1][2])+1\)
\(f_1[i][1]=max(f_1[i+1][0],f_1[i+1][2])\)
\(f_1[i][2]=max(f_1[i+1][0],f_1[i+1][1])\)
当\(i\)子节点个数为\(2\)时：
设\(x\)为\(i\)的左节点，\(k\)为\(i\)的右节点。
\(f_1[i][0]=max(f_1[x][1]+f_1[k][2],f_1[x][2]+f_1[k][1])+1\)
\(f_1[i][1]=max(f_1[x][0]+f_1[k][2],f_1[x][2]+f_1[k][0])\)
\(f_1[i][2]=max(f_1[x][0]+f_1[k][1],f_1[x][1]+f_1[k][0])\)
\(f_2\)把\(max\)改为\(min\)即可。
上面的可能有些简单，所以再来一道。
P4160 生日快乐
要求每人必须获得面积相同的蛋糕，所以切到最后每块蛋糕的面积必定为\(\frac{x*y}{k}\)，每块蛋糕的长最小为\(\frac{x}{k}\)，宽最小为\(\frac{y}{k}\)。
设\(dx=\frac{x}{k}\)，\(dy=\frac{y}{k}\)，容易看出横着切每一刀切的必定是\(dy\)的倍数，竖着切每一刀必定是\(dx\)的倍数，否则一定无法保证每块蛋糕面积均为\(\frac{x*y}{k}\)，枚举每一刀横着切或竖着切切完的两块蛋糕比值的最大值，最后取\(min\)即可。
2.双向搜索
双向搜索分为了两种：双向同时搜索和折半搜索。
（1）双向同时搜索
基本思想就是从状态图的两头同时进行深搜或广搜，若两头在中间相遇了，则被视为可行解。
（2）折半搜索
主要思想就是将枚举的内容分为两半，分别枚举后再合并即可。折半搜索能将普通搜索的时间复杂度从\(O(2^n)\)优化为\(O(2^\frac{n}{2})\)，适用于\(n \le 40\)的范围。
这两种搜索方式其实没什么太大差别，一般能用双向同时搜索的也能用折半。这就是洛谷标签只有折半的原因吗
例：P4799 世界冰球锦标赛
纯板题。
\(n\le40\)，单纯爆搜肯定过不了，考虑折半，复杂度变为\(O(2^\frac{n}{2})\)。
将\(n\)分为\(1\sim\frac{n}{2}\)和\(\frac{n}{2} +1\sim n\)两组，分别搜一遍，将结果从小到大排序，最后统计答案即可。
还可以试试这个题：抱枕+双倍经验
3.迭代加深搜索
迭代加深搜索是一种每次限制搜索深度的深度优先搜索。
为什么要用迭代加深搜索？
迭代加深搜索一般用于找最优解，\(bfs\)也是，但是\(bfs\)是基于队列实现，空间复杂度很大，所以就有了迭代加深搜索，实际上就相当于用\(dfs\)来实现\(bfs\)，空间复杂度较小。
迭代加深搜索的本质还是深搜，但搜索的同时设有一个深度，当深度达到时就返回，如果对于一个深度没找到，再换下一个深度继续搜索。
操作步骤：
- 设定一个较小的深度作为变量
- \(dfs\)
- 当深度大于设定深度时返回
- 未发现目标，深度加\(1\)
- 发现目标，回溯(可以记录路径)
例：UVA529 Addition Chains
可以发现，普通的\(dfs\)可能得不到答案，\(bfs\)会爆空间，考虑将两者结合，也就是迭代加深。将\(x\)从零开始枚举，看是否能构造出长度为\(x\)的序列，有直接输出并退出，没有，继续枚举\(x+1\)。
这就完了吗？当你信心满满的交上去之后，你会发现你\(T\)了。所以还需要进行亿点点剪枝。
我们可以一眼丁真的发现，题面给出序列是单调递增的，因此可以判断一下当前搜索的数是否已经大于\(n\)，是的话直接跳出。
然后你发现还是\(T\)了。
再稍微看两眼性质，可以发现，\(a[i]\)最大是\(a[i-1]\)的二倍，而\(i\)后有\(x-i\)个数（\(x\)表示序列长度），所以当第\(i\)个数是\(a[i]\)的时候，\(a[x]\)最大为\(a[i]*2^{x-i}\)，而题目要求\(a[i]\)为\(n\)，将两数比较一下，如果最大的数都小于\(n\)，说明这种情况肯定无法满足要求，直接跳出。
这样就引出了下一个版块——剪枝。
4.剪枝
剪枝，字面意思就是把一棵树多余的枝条剪掉。当我们发现普通的\(dfs\)过不了的时候，我们就可以选择适当剪枝，通过对题目一些性质的推理，来达到对时间和空间复杂度的优化。
常见的剪枝有三种：记忆化剪枝，可行性剪枝，最优性剪枝。
记忆化搜索：因为在搜索中，相同的传入值往往会带来相同的解，那我们就可以用数组来记忆。
最优性剪枝：在搜索中导致运行慢的原因还有一种，就是在当前解已经比已有解差时仍然在搜索，那么我们只需要判断一下当前解是否已经差于已有解。
可行性剪枝：在搜索过程中当前解已经不可用了还继续搜索下去也是运行慢的原因。
例：P1391 方阵安排
爆搜思路不难想，将矩阵每个点依次枚举，最后\(n^2\)判断是否符合要求。复杂度\(O(2^n*n^2)\)，\(n\le18\)，显然不合格，考虑剪枝。
剪枝一（最优性剪枝）：当已修改过的点数大于等于之前搜到的点数最优解时，可以直接返回。
剪枝二（可行性剪枝）：可以发现，一个点\((x,y)\)，在上下左右四个点都被枚举过后就能判断，通俗的来讲就是枚举点\((x+1,y+1)\)的时候可以顺便判断点\((x,y)\)，所以我们可以在枚举\((x,y)\)的过程中顺便判断\((x-1,y-1)\)是否符合要求，不符合直接返回。
5.Dancing Links(DLX)
精准覆盖问题
含义：对于一个集合\(S\)，有\(n\)个子集\(s\)，\(\forall s_i,s_j\)，使得\(s_i \cap s_j=\varnothing\)，且\(s_1\cup s_2\cup \cdots \cup s_n=S\)。
例：
\(S={1,2,3,4,5,6,7}\)
\(s_1={1,2,3}\)
\(s_2={4,5,6}\)
\(s_3={5,6,7}\)
\(s_4={4,7}\)
\(s_5={5,6}\)
\(s_6={7}\)
\(s_1,s_2,s_6\) 和 \(s_1,s_4,s_5\)就分别是精确覆盖集合\(S\)的解（即每个小集中的元素合起来，使其每个元素都在大集中出现且出现一次，大集中的每个元素也都在小集中出现且出现过一次）。
用\(01\)矩阵表示上述集合就是
\(\begin{bmatrix} 1 & 1 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 1 & 1 & 0 \\ 0 & 0 & 0 & 0 & 1 & 1 & 1 \\ 0 & 0 & 0 & 1 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 & 1 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 \end{bmatrix}\)
目标是选出矩阵的若干行，使得其中的\(1\)在所有列中出现且仅出现一次。其中第\(i\)行表示\(s_i\)，而这一行的每一个数依次表示\([1\in s_i]\)，\([2\in s_i]\)，\(\cdots\)，\([7\in s_i]\)。
实现：太长，懒得写了，直接看dalao的罢
补：DLX最经典的使用就是填数独。考虑将数独转化为更大的矩阵，行表示选法，列表示限制。用DLX跑一遍精准覆盖即可。