算法设计知识点自查表
四则运算、$\mathbf{Z}_N$ 下四则运算+幂运算复杂度；
欧几里得 GCD 递归复杂度证明；
拓展欧几里得算法求乘法逆元；
利用同余性质推算大数能否被整除；
费马小定理完整证明；
非 Carmichael 合数的费马测试证明；
对称加密、非对称加密、证书；
大师定理；
比较排序的时间下界证明（$n!$ 如何确定两边界？）；
快选算法在 25%-75% 判据下的时间复杂度；
矩阵算法、计数逆序（及拓展）时间复杂度推导、算法设计；
有向图中，有自环等价于存在回边的证明；
DAG 中，最大 post number 意味着源点、最小 post number 意味着汇点；
证明 DAG 中，至少有一个源点和一个汇点；
普通有向图中，最大 post number 意味着位于源点强连通部件内。但最小 post number 没有特性；
记忆：任何有向图的嵌图都是 DAG；
$G$ 中的源点强连通部件是 $G^R$ 中的汇点强连通部件；
证明：
DFS explore 子过程若从 $u$ 开始，必然以 $u$ 及其所有可达结点遍历结束后结束（反证）；
$G$ 的两个不同的强连通部件 $C_1,C_2$，如果有从 $C_1$ 到 $C_2$ 的边，则 $C_1$ 的最大 post number 大于 $C_2$ 的最大 post number（不是所有），证明时讨论遍历开始的位置；
- 同第 14 条；
线性时间查找有向图强连通部件算法；
问题：
- 线性时间找到有向图中能到达其他所有顶点的点（如果不存在需要指出）；
- 线性时间判断无向图是否为二部图：证明使用着色法；
- 线性时间判断有向图是否存在奇数个顶点的环：每个强连通子图上 DFS 二染色。对回边（好理解）/ 前向边 / 交叉边（如果强连通部件中从 $u$ 到 $v$ 间有两条道路，并且这两条道路奇偶数不同，因为违反染色规则了所以不同。则必然存在一个奇数环和一个偶数环）违反规则的情况认为是含有奇数顶点的环；
- 线性时间找 DAG 中从指定顶点 $u$ 到 $v$ 的路径数目：从 $u$ DFS 遍历时，遇到无论什么边，只要是指向 $v$ 的，都让计数加一；
- 线性时间判断 DAG 中的 Hamilton 路径的存在性：修改线序化算法。每次检查是否有多于一个入度为 0 的结点，如果是就不存在。
lemma：BFS 过程中，对每个 $d\in\mathbf{N}$，都总存在一个时刻，使得：
- 所有与 $s$ 间距小于等于 $d$ 的顶点都被正确地设置了距离；
- 其他顶点的距离都还未被设置（$+\infty$）;
- 队列中只含有与 $s$ 间距为 $d$ 的顶点；
分析 d-堆、二叉堆、数组作为 Dijkstra 算法的优先级队列时的时间复杂度情况；
Dijkstra 算法：
- 所有结点初始化距离为 $\infty$，只有源点是 0；然后对所有结点构建优先级队列；
- 在队列不空时循环出队：
- 出队 $u$ 时，更新相邻结点距离。如果更小就覆盖（此举会改变相邻点在优先级队列中的位置），并且维护最短路径列表
pre[]（如果需要）；
- 出队 $u$ 时，更新相邻结点距离。如果更小就覆盖（此举会改变相邻点在优先级队列中的位置），并且维护最短路径列表
时间复杂度：$|V|$ 次删除、$|V|+|E|$ 次
decreaseKey；证明 Dijkstra 算法正确性：归纳假设
预设：对于一个图 $G$，设定源点 $s$，希望测量的目标点 $v$，假定算法运行时已经设定距离（完整更新一轮邻居后的结果）的结点的集合为 $S$。下面对 $S$ 的大小与算法正确性归纳；
奠基：$|S|=1$ 的情况显然算法正确（$s$ 的最短距为 0）；
假设：假设对于 $|S|\ge1$ 的情况算法都是正确的；
归纳：进行下一轮邻居更新时，设更新到的结点 $v$ 将被加入 $S$，设 $(u,v)$ 是最后一条边。则 $s$ 至 $u$ 的最短路径一定位于 $S$ 中（算法正确性保证），记为 $dist[u]$，我们只需要证明 $dist[u]+l(u,v)$ 比其他任何 $s$ 到 $v$ 间的路径都短就行。
假设 $(x,y)$ 是新一轮迭代中第一条边（最有可能更短），并且 $y$ 到 $v$ 右边。我们记 $s$ 到 $x$ 的路径为 $p^\prime$，则：
$l(p^\prime)+l(x,y)\ge dist[u]+l(x,y)\ge dist[y]\ge dist[v]$；
注意到，如果存在负边权，$dist[y]\ge dist[v]$ 不再成立，因为可能 $l(y,v)$ 是个绝对值很大的负数。
这个时候如果需要更新 $v$，发现 $v$ 已经被弹出去了，没法更新了，因此 Dijkstra 算法在负权下不再是正确的了。
Bellman-Ford 算法：
- 从源点开始，同时地更新一次（不能把这轮更新的信息用来更新其他结点）每条边的两端点的距离信息；
- 重复上述动作 $|V|-1$ 次；
时间复杂度 $O(|V||E|)$；
证明为何 Bellman-Ford 算法只需要重复更新 $|V|-1$ 次：
- 因为从源点 $s$ 到任意一点 $t$ 的最短路径 $s\rightarrow v_1\rightarrow v_2\rightarrow\cdots\rightarrow v_k\rightarrow t$ 最多包含了 $|V|-1$ 个顶点（这条用反证法）。
- 更新了 $|V|-1$ 次后，即便再多的更新都是安全的（$\min$ 不会变大），并且不会缺漏（顶点不会移除）；
如何检测负环？让 Bellman-Ford 算法在运行 $|V|-1$ 次后再进行一次，如果还有顶点的距离在变化，则说明有负环。
可以含负权的 DAGs 的单元最短路径算法：先拓扑排序，再按线序顺序更新结点的距离信息；
时间复杂度：$O(|V|)$；
问题：
强连通图的某点 $v_0$ 通过的边全部是正权的。找任意两点间的最短路，要求必须经过 $v_0$；
先求 $v_0$ 为源的到各点的最短距离，然后 $dist(u,v_0)+dist(v_0,v)$；
无向正权图中有一条边 $e_0$，求含 $e_0$ 的最短环的长度；
设 $e_0=(u,v)$，在 $G-e_0$ 中执行 Dijkstra 算法找到 $u$ 到 $v$ 的最短距离，加上 $l(e_0)$ 即可；
有向正权图的最短环？
环是由 $u$ 到 $v$ 和 $v$ 到 $u$ 的路径拼接而成。
先求每两个点间的最短路径（数组数据结构 $O(|V|^3)$），在遍历查找 $dist(u,v)+dist(v,u)$ 最小值；
有向正权图中最简最长路径？
NP Hard 问题；可以将 Hamilton 图问题规约到这个问题。
无向正权图的最短环？
遍历所有边，每轮循环时删除当前边，并且选取一端运行 Dijkstra 算法。如果另一端是可达的（不是 $\infty$，记为 $c_i$），那么说明原图中存在一个长度为 $c_i+l(e)$ 的环。遍历找长度最小的那个。
无向等权图中指定两点间最短路径数量？
BFS 使用两个队列。类似 copy collection，最终在队列 1 中找到与 $u$ 相邻的结点终止。然后统计队列中还有哪些与 $u$ 相邻的结点。其数量即为所求。
这个方法的原理是利用 BFS 的性质（参见第 20 条 lemma）：在每轮结束后队列中放的是相同长度的结点（分开放能确保下一轮的结点不会混入当前队列中）。
证明 $|V|-1=|E|$ 的无向连通图等价于树数据结构；
必要性：归纳。对顶点归纳的话，就是 $k$ 个顶点推 $k+1$ 个；对边归纳的话，就是向 $n$ 个顶点中加边看连通部件数是否减为 1；
充分性：反证。假设不是树，则必然存在环，重复去环得到 $|E^\prime|\lt|E|$，由必要性可知 $|E^\prime|=|V|-1=|E|$，矛盾；
证明一个无向图是一棵树 当且仅当 任意两结点间有一条唯一路径；
- 充分性：反证。如果不是就有环，违反定义；
- 必要性：先判断是连通图，再反证。假设存在环，则存在两个结点间路径不唯一，矛盾；
Kruskal：向顶点中加尽可能小的边，成环就舍去。直至加够 $|V|-1$ 条；
割定理：割集间的最短边一定在最小生成树中：分类讨论 + 反证法；
Prim：顶点割集 + 顶点的策略。正确性由割定理保证；
上色算法求 MST：破圈（染红没有红边的环）、闭圈（染蓝没有蓝边的割边集合中最短边）；
证明贪婪算法作为近似算法求解 set cover 问题的近似比为 $\ln n$（设 $n_t$ 是 $t$ 轮选取后剩下的顶点数）；
01 背包和完全背包问题的状态转移方程、边界条件（出口）、时空复杂度；
多重背包问题（不含二进制优化）算法设计以及时间复杂度分析；
硬币找零问题最优解算法；
子序列系列问题：
- 最长递增子序列：构造 DAG 再动归边；
- 最长公共子序列、最长公共子串；
- 分治法和动态规划分别求解 最大连续子序列（即子串）和（为什么讨论以 $a_i$ 结尾的子串？子串更适合这种方法！）；
三分问题的状态转移方程；
Shortest Reliable Path Lite：经过不超过指定边数的最短路径问题；
和 Shortest Reliable Path 的 NP-Complete 问题不一样；
详情参见第 50 条；
矩阵乘法最优分配：化归为二叉树，动归二叉树代价；
动态规划尝试解决 TSP 问题算法；
线性时间找出树的 independent set 大小：分类讨论，孙子结点可以在、儿子结点只能替代；
棋子放置问题：模式、相容 与动态规划；
DP 难题：
假设 $M[i,j,p,q]$ 表示对子串 $s[i]\sim s[j]$ 分割，涉及分割点在数组中 $d[p]\sim d[q]$，分割后的最小代价；
状态转移方程：$M[i,j,p,q]=j-i+1+\min\limits_{p\le k\le q}\{M[i,d[k],p,k]+M[d[k]+1,j,k+1,q]\}$；
算法复杂度 $O(m^2n^2)$；
设在 $x\times y$ 的布料上制作前 $i$ 个产品的最大价值为 $P(i,x,y)$，则状态转移方程为：
主要注意到布料是可以旋转使用的！因此分为旋转后再裁剪（$P_v$）和不旋转直接裁剪（$P_h$）两种手段。
规范型线性规划转对偶式；
单纯形算法时间复杂度推导 $O(n(m+n)C_{m+n}^n)$；
单纯形算法求解多元线性规划；
最大流问题变式：
- 含有多个源点和汇点的最大流问题：定义新的源点和汇点；
- 每个顶点有流量限制：将每个顶点拆成两个，这两个顶点间用一条有向边连接，容量就是限制。转换成普通最大流问题；
- 每条边在容量的基础上添加限制，要求流量不得低于某个限制。或者某些节点间存在流量损耗：直接规约成一般线性规划问题；
瓶颈边（增大会导致总流增大）、临界边（减小会导致总流减小）：注意它们俩是不一样的！！
查找临界边：
剩余图中只有反向边的；
但也不全是。可能某条在最大流中流满的边，其容量下降后，最大流中缺少的流量可以从其他边的流量得到补充。通过在剩余图中 DFS 能通过的这些反向边就不是临界边，排除它们即可。
证明：二部图的最小顶点覆盖能够被规约为最大流问题。
边不相交问题（化归为最大流问题，需要证明）；
常见 NP-Complete 问题规约：
- 稠密子图问题（a 个顶点中至少 b 条边）：$b=\dfrac{a(a-1)}{2}$，从最大团问题规约；
- 稀疏子图问题（a 个顶点中至多 b 条边）：$b = 0$，从最大独立集问题规约；
- 集合覆盖问题：从顶点覆盖规约（子问题，一个元素只会同时存在于两个集合中）；
- 子图同构问题（G 能否只通过删除一些点、边，修改名称来得到 H）：从哈密顿回路规约（构造图 G 是一个 N 元环，N 为输入图的顶点数）；
- 最大公共子图（同时删除 G 和 H 一些点和对应边，使二者相同，预算 b）：从最大独立集规约；
- 哈密顿回路、哈密顿道路相互规约；
- 最长初级路径（simple longest path）：从哈密顿路径规约；
- K-Coloring 问题：从 3-SAT 问题规约（构建 OR-gadget 和 Clause gadget）；
- 可靠网络问题（shortest reliable path，给定顶点、距离矩阵(边权)、连接需求(重边数量)、预算，构建一个总代价不超过预算、两点间的不同路径数等于对应连接需求的图）：从 TSP 问题规约（预算 $b=n$，距离矩阵全为 1 或 2，表示有边和没有边，连接需求全为 2，表示在环上）；
近似算法解决 NP 问题：
- 贪婪算法求解集合覆盖问题。近似比 $ln n$；
- 极大匹配算法（贪婪选取尽可能多的 endpoints 的边，然后删除共享 endpoints 的边）求解顶点覆盖问题。近似比 2；
- 贪婪算法求解 k-clustering 问题：先任取一个点作为第一个中心，然后每次取离当前点最远的，中垂线分割。近似比为 2；
- MST + skip 近似 metric-space-TSP 问题：近似大小不大于最小生成树长度两倍。而最优解不不小于最小生成树长度。因此近似比为 2；
- rescale value 近似背包问题：缩小 $\hat{v_i}=\dfrac{n}{\varepsilon v_{\max}}$，总价值 $\sum v_i\ge\sum\hat{v_i}=K^\star(1-\varepsilon)$，即近似比为用户指定的任意接近；
- wechat
- alipay
