OI知识点总结

**由于历史遗留原因，存在大量滥用 $\LaTeX$ 现象。请勿以此为标准写题解。** 基本完工。最后更新于 2020/04/02 本文仅供 ss 内部交流使用。 大致按照个人理解分类，并附上一定的题目和看法，不全面，仅供参考。 打$*$的是提高组必学，两个$*$的最好学。太基础的没写。 不配题的大多数是随便都能找到的，少部分是找不到的。 学习一个新算法的时候要先思考如何实现，然后结合题解代码考虑自己没考虑到的问题以及哪些步骤可以简化。 学习博客基本上按照洛谷模板题/我的推荐题目的题解就可以了。 大部分学完就可以大量刷题了，可以参考我的刷题记录。不要看算法标签。 $1$ 基本操作和一些杂谈 $\ \ \ \ *1.1$ IO $\ \ \ \ \ \ \ \ $使用 `scanf` 替代 `cin`。 $\ \ \ \ \ \ \ \ $字符串通常使用 `while`+`getchar()` 滤掉所有无关字符比较方便，防止系统差异的问题，也防止出题人不小心使用 '\0' 等不可见字符作为空格 $\ \ \ \ \ \ \ \ $快读常用 `getchar()` ，如果 IO 量大于 $3\times 10^6$ 个 `int` 最好用 $fread$ 加速。用法: `fread(c,1,n,stdin)`，从标准读入读进 $n$ 个字符到 `c` 数组中，从 `c[0]` 开始储存。返回值为成功读取的个数，如果不写成 `c[fread(c,1,n,stdin)]=0` 可能会出错（在后面接了一些奇怪字符，但这个错误很玄学，偶尔才会出来，建议不要冒险）。 $\ \ \ \ **1.2$ 重载运算符 $\ \ \ \ \ \ \ \ $[示例](https://www.luogu.com.cn/paste/e2ixthng)，其中 $structname$ 是结构体名称。 $\ \ \ \ **1.3$ $bigsmall$系列思想 $\ \ \ \ \ \ \ \ $ 包括 meet in the middle （即[折半搜索](https://www.luogu.com.cn/problem/P4799)）、按数字大小分类题、部分贪心 $\ \ \ \ 1.4$ 线性基 [题](https://www.luogu.com.cn/problem/P3292) $\ \ \ \ 1.5$ cdq 分治 本质是解决一类三维数点问题，要会抽象到三维数点模型。 $\ \ \ \ *1.6$ 矩阵加速递推 [题1](https://www.luogu.com.cn/problem/P3873)，[题2](https://www.luogu.com.cn/problem/P1707) $\ \ \ \ 1.7$ 二分三分 $\ \ \ \ \ \ \ \ *1.7.1$ 三分法 $\ \ \ \ \ \ \ \ \ \ \ \ $ 以先增后减函数为例，注意函数在峰前必须是**严格递增**的，如果有**不降**区间可能会导致三分结果出错。 $\ \ \ \ \ \ \ \ 1.7.2$ 二分法 $\ \ \ \ \ \ \ \ \ \ \ \ *1.7.2.1$ 普通二分 $\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ $ 注意边界。 $\ \ \ \ \ \ \ \ \ \ \ \ 1.7.2.2$ 带权二分（wqs 二分/dp 凸优化） $\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ $ 注意边界！！！这个的边界需要特别留意，建议多用几个方法写[这题](https://www.luogu.com.cn/problem/P4072)然后你会发现一些做法会 $\text{WA}$ 一个点的，要仔细分析理解。另外推荐[题](https://www.luogu.com.cn/problem/P2619) $\ \ \ \ \ \ \ \ \ \ \ \ 1.7.2.3$ 整体二分 $\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ $ 本质上和 cdq 分治一样都是一类统一考虑贡献的方法。[题1](https://www.luogu.com.cn/problem/P1527)，[题2](https://www.luogu.com.cn/problem/P4175)。 $\ \ \ \ 1.8$ 最小乘积类问题 [题](https://www.luogu.com.cn/problem/P3236) $\ \ \ \ 1.9$ 线性规划 [题1](https://www.luogu.com.cn/problem/P3337)，[题2](http://uoj.ac/problem/179) $\ \ \ \ 1.10$ 舞蹈链（DLX） $\ \ \ \ 1.11$ 龟速乘与光速乘 $\ \ \ \ *1.12$ 一点小建议 $\ \ \ \ \ \ \ \ $ 不要使用指针，尽量数组代替。 $\ \ \ \ \ \ \ \ $ 注意常数优化的一些技巧，例如减少不必要的取模/除法运算，用无符号整数，循环展开，`register/inline` 等等。有人说它没用，但实际上确实有效。 $2.$ 数据结构 $\ \ \ \ *2.1$ 基础数据结构（如队列及循环队列、栈等，建议手写） $\ \ \ \ \ \ \ \ 2.1.1$ 单调栈 [题](https://www.luogu.com.cn/problem/P5300) $\ \ \ \ \ \ \ \ 2.1.2$ 单调队列 [题](https://www.luogu.com.cn/problem/P1886) $\ \ \ \ *2.2\ \text{stl}$ $\ \ \ \ \ \ \ \ \text{stl}$中包含 `priority_queue,pb_ds,set,multiset,bitset,vector,map,pair` 等常用容器，以及 `sort`,`unique` 等常用函数。但是建议 `map` 改用手写哈希，用类似链式前向星的挂链法。 $\ \ \ \ 2.3$ 堆 $\ \ \ \ \ \ \ \ $包括*二叉堆、左偏树、斐波那契堆、配对堆等，后两种虽然复杂度优但是不常用，前两种必学 $\ \ \ \ 2.4$ 树状数组及线段树 $\ \ \ \ \ \ \ \ *2.4.1$ 树状数组 $\ \ \ \ \ \ \ \ \ \ \ \ $ 掌握到二维区间修改区间求和以及在最值中的运用。[题1](https://www.luogu.com.cn/problem/P3287),[题2](https://www.luogu.com.cn/problem/P4514) $\ \ \ \ \ \ \ \ 2.4.2$ 线段树 $\ \ \ \ \ \ \ \ \ \ \ \ $ 建议把 pushup 和 pushdown 单独写，方便调试。 $\ \ \ \ \ \ \ \ \ \ \ \ *2.4.2.1$ 线段树建树、单标记 $\ \ \ \ \ \ \ \ \ \ \ \ *2.4.2.2$ 线段树多标记（注意顺序），[题1](https://www.luogu.com.cn/problem/P3373)，[题2](https://www.luogu.com.cn/problem/P4560)。 $\ \ \ \ \ \ \ \ \ \ \ \ 2.4.2.3$ 线段树分裂和合并，[题](https://www.luogu.com.cn/problem/P4556)。 $\ \ \ \ \ \ \ \ \ \ \ \ 2.4.2.4$ 线段树分治，[题1](https://loj.ac/problem/121)，[题2](https://www.luogu.com.cn/problem/P3733)，[题3](https://www.luogu.com.cn/problem/CF1140F)。 $\ \ \ \ \ \ \ \ \ \ \ \ 2.4.2.5$ 李超线段树，[题](https://www.luogu.com.cn/problem/P4097)。 $\ \ \ \ \ \ \ \ \ \ \ \ **2.4.2.6$ 势能线段树，[题1](https://www.luogu.com.cn/problem/P4145),[题2](https://www.luogu.com.cn/problem/P3747)。 $\ \ \ \ \ \ \ \ \ \ \ \ **2.4.2.7$ 线段树维护点对统计，[题](https://www.luogu.com.cn/problem/P4065)。 $\ \ \ \ \ \ \ \ \ \ \ \ **2.4.2.8$ 动态开点线段树，[题](https://www.luogu.com.cn/problem/CF915E)。 $\ \ \ \ \ \ \ \ \ \ \ \ **2.4.2.9$ 权值线段树，[题1](https://www.luogu.com.cn/problem/P3988)，[题2](https://www.luogu.com.cn/problem/CF1146E) $\ \ \ \ \ \ \ \ \ \ \ \ 2.4.2.10$ 划分树 $\ \ \ \ 2.5$ 二叉树 $\ \ \ \ \ \ \ \ **2.5.1$ 普通二叉树 $\ \ \ \ \ \ \ \ \ \ \ \ $本质上是按照中序遍历保存的一种数据保存方式，理解原理即可，用的一般都是后面的二叉树。 $\ \ \ \ \ \ \ \ 2.5.2$ 平衡树 $\ \ \ \ \ \ \ \ \ \ \ \ $平衡树产生的原因是对于一个中序遍历有不同的树形态。如下图左右两种中序遍历都是 1234567  $\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ $其中一些形态最深点深度较大，意味着访问这个节点代价比较高（因为访问都是从根往下找），如右图的节点 $7$ 。平衡树作为二叉排序树时，旋转的目的就是使得不要产生代价太大的访问，即把访问复杂度控制在 $O(log_2n)$，如左图访问代价就比较均匀。当然并不能保证形成恰好 $log_2n$ 层，只是 $O(log_2n)$。 $\ \ \ \ \ \ \ \ \ \ \ \ 2.5.2.1\ \text{treap}$ $\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ $本质上是 $tree+heap$，通过随机节点权值的方法，使得树形态随机。对于任意给出的权值都能产生一个二叉树，使得中序遍历符合给定顺序，而权值符合堆的大小关系（小根堆大根堆都可以）。（这个我没证过，但应该没问题），因此可以用随机权值来打乱树的形态，而形态随机的时候最大深度是 $O(log_2n)$ 的。插入节点后可能要改变树的形态使它符合上述条件，要配合旋转操作（splay也要）。旋转操作建议自行画图模拟，反正看一下怎样能把当前点更靠近树根并且符合二叉树顺序就可以了。 $\ \ \ \ \ \ \ \ \ \ \ \ 2.5.2.2\ \text{fhq-treap}$ $\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ $前置知识：线段树。与 $\text{treap}$ 原理相同，但是通过 $\text{split}$ 和 $\text{merge}$ 操作替代旋转，可以可持久化，支持区间操作。 $\ \ \ \ \ \ \ \ \ \ \ \ 2.5.2.3\ \text{splay}$ $\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ $前置知识：线段树。本质上是有一个操作可以不断旋转把节点旋转到根，复杂度我不会证。 $\text{splay}$ 的最重要功能是实现区间操作。假如把数组下标看作节点权值，那么就可以在 $\text{splay}$ 上维护一个区间了。如果提取区间 $[l,r]$ ，只需要把 $l-1$ 旋转到根，把 $r+1$ 旋转到根右儿子，那区间对应子树就是 $r+1$ 的左儿子。切记：学 $splay$ **不**要看一本通。[题1](https://www.luogu.com.cn/problem/P2042)，[题2](https://www.luogu.com.cn/problem/U74090)。[封装之后的代码](https://sserxhs.blog.luogu.com.cn/splay-ban-zi) $\ \ \ \ \ \ \ \ \ \ \ \ 2.5.2.4\ $~~珂朵莉树~~ 适用范围较窄 $\ \ \ \ 2.6$ 分块及莫队 $\ \ \ \ \ \ \ \ $ 分块本质是平衡复杂度。例如区间修改区间求和，有一个朴素的暴力优化思路是同时维护相邻五个数的情况以减少操作常数。而若直接考虑设置一个块大小 $B$ ，对于跨过整个块的询问直接加上那个块的总和（修改则打标记并修改总和），对于左右两端的非完整块暴力一个一个加，则复杂度为 $O(B+\frac{n}{B})$，由基本不等式得知当 $B=\sqrt n$ 时最小。同理，对于不同题目，要自己分析复杂度，确定一个合理的块大小。注意两边的常数差异可能会导致块大小不是复杂度分析的那个（但一定线性相关），应该灵活调整。这一点在 bzoj 上一道 fft 套分块的题目体现得比较明显，~~我至今也不知道那题块大小该怎么调~~ $\ \ \ \ \ \ \ \ **2.6.1$ 分块题目推荐：[题](https://www.luogu.com.cn/problem/P5048)。 $\ \ \ \ \ \ \ \ 2.6.2$ 莫队 $\ \ \ \ \ \ \ \ \ \ \ \ $莫队的核心是对于一些二维数点 $[l,r]$ 的以曼哈顿距离为长度的最短哈密顿回路问题的**较优**解(不是最优解)，转化到区间问题上就是对一类支持左右端点快速移动（也就是说，从 $[l,r]$ 移动到 $[l-1,r]$ 可以快速更新答案）的询问。莫队的最佳块大小为 $\frac{n}{\sqrt q}$，复杂度是 $O(n\sqrt q)$。 $\ \ \ \ \ \ \ \ \ \ \ \ 2.6.2.1$ 普通莫队 [题1](https://www.luogu.com.cn/problem/P1494)，[题2](https://www.luogu.com.cn/problem/P3674)，[题3](https://www.luogu.com.cn/problem/P5268)。 $\ \ \ \ \ \ \ \ \ \ \ \ 2.6.2.2$ 带修莫队 [题1](https://www.luogu.com.cn/problem/P1903)，[题2](https://www.luogu.com.cn/problem/CF940F)。 $\ \ \ \ \ \ \ \ \ \ \ \ 2.6.2.3$ 树上莫队 前置知识：树剖，题目[coat2]、[CF600E]（找不到了） $\ \ \ \ \ \ \ \ \ \ \ \ 2.6.2.4$ 回滚莫队 [题](https://www.luogu.com.cn/problem/AT1219) $\ \ \ \ \ \ \ \ \ \ \ \ 2.6.2.5$ 二次离线莫队 [题1](https://www.luogu.com.cn/problem/P4887)，[题2](https://www.luogu.com.cn/problem/P5047) $\ \ \ \ 2.7$ 可持久化数据结构（重点：主席树） 包括可持久化 $\text{trie}$、数组、线段树、$\text{fhq-treap}$、左偏树。主席树的思想是维护前缀和，而带修主席树思想是：修改单点等同于修改区间的前缀和（因为主席树维护前缀和），对主席树差分一下还是修改单点，就可以用 $\text{bit}$维护修改了。而原本我们只需要拿一棵主席树出来，现在由于差分需要用 $\text{bit}$ 查询前缀和，提取出所有需要的主席树。这个思想和区修单求 $\text{bit}$ 非常相似。总的来说，这个数据结构其实就是两种数据结构的组合，只不过把原本单纯在 $\text{bit}$ 上修改数组一个值变成了修改主席树上的一个值的区别罢了，没有实质差异。[题](https://www.luogu.com.cn/problem/P3332) $\ \ \ \ 2.8$ 树套树（两种树套一起） $\ \ \ \ 2.9$ 可追溯化数据结构 $\ \ \ \ \ \ \ \ $ 参考 $\text{WC2019}$ 营员交流。 $\ \ \ \ *2.10$ ST表 [题](https://www.luogu.com.cn/problem/P3793) $\ \ \ \ 2.11$ 跳表 $3.$ 数论 $\ \ \ \ *3.1$ 简单数论 包括容斥定理（[1](https://www.luogu.com.cn/problem/CF559C)）（[2](https://www.luogu.com.cn/problem/P4859)）（[3](https://www.luogu.com.cn/problem/P3349)）、同余理论， $gcd\ \&\ exgcd\ \&\ crt\ \&\ excrt$，欧拉定理和扩展欧拉定理，组合数学的上指标求和恒等式、吸收恒等式、范德蒙德卷积、两类斯特林数，卡特兰数，逆元的四种求法:[exgcd/ex欧拉定理](https://www.luogu.com.cn/problem/P1082)，[普通线性逆元](https://www.luogu.com.cn/problem/P3811)，[一般线性逆元](https://www.luogu.com.cn/problem/P5431)。 $\ \ \ \ 3.2$ 数论进阶 二次剩余、原根理论、特征多项式和特征矩阵，容斥定理的运用（二项式反演等）。 $\ \ \ \ *3.3$ 高斯消元（包括普通解方程组/解行列式/向量线性基） $\ \ \ \ 3.4$ *$\text{BSGS}$ （大步小步算法）和 $\text{exBSGS}$ $\ \ \ \ 3.5$ 莫比乌斯反演以及线性筛 $\ \ \ \ \ \ \ \ *3.5.1$ 线性筛 $\ \ \ \ \ \ \ \ \ \ \ \ $线性筛的基本作用是筛出所有素数，拓展之后的作用是在 $O(n)$ 的时间复杂度内预处理一个积性函数。线性筛的原理是每个数字只会被最小素数（也就是枚举的内层循环）筛掉，由这个可以在能快速计算 $f(p^k)$ 的情况下根据积性线性筛 $f(x)$。可以线性筛常用的积性函数包括$\mu(x),\varphi(x),x^k,d(x)$（约数函数）。 $\ \ \ \ \ \ \ \ 3.5.2$ 莫比乌斯反演 $\ \ \ \ \ \ \ \ \ \ \ \ $本质用的公式就是百度百科的那个公式，莫比乌斯反演要多做题，学会交换求和次序、改变求和上下界的技巧。 $\ \ \ \ \ \ \ \ 3.5.3$ 狄利克雷卷积和杜教筛 $\ \ \ \ \ \ \ \ \ \ \ \ $属于看一遍就要懂得自己推的内容（指的是原式的推导），但是具体要卷一个什么函数还是要看题目的要求。常用的是对 $\varphi$ 卷 $id$ 函数，对 $\mu$ 卷 $[x==1]$，如果有其他系数按照题目来具体分析。[推荐题目](https://www.luogu.com.cn/problem/P3768) $\ \ \ \ \ \ \ \ 3.5.4$ 洲阁筛和 $\text{min\_25}$ 筛 $\ \ \ \ 3.6$ $\text{polya}$ 定理和 $\text{burnside}$ 引理 $\ \ \ \ 3.7$ $\text{Lucas}$ 定理和 $\text{exLucas}$ 定理 最好能理解到本质 $\ \ \ \ 3.8$ 拉格朗日插值和拉格朗日重心插值法，推荐[题1](https://www.luogu.com.cn/problem/CF622F),[题2](https://www.luogu.com.cn/problem/P5223)。 $\ \ \ \ 3.9$ 多项式全家桶 $\ \ \ \ \ \ \ \ 3.9.1$ 虚数和复平面初步 $\ \ \ \ \ \ \ \ 3.9.2$ 快速傅立叶变换 $(\text{FFT})\ \ $ 预处理单位复根会失精，但是可以提高速度。 $\ \ \ \ \ \ \ \ 3.9.3$ 快速数论变换 $(\text{NTT})\ \ $ 这是一切多项式题目的必备，必须要在短时间内写出来，并且常数不能太大。 $\ \ \ \ \ \ \ \ 3.9.4$ 快速沃尔什变换 $(\text{FWT})$ 本质上是求子集和/父集和，$\text{xor}$可以看作高维 $\text{FFT}$ [题](https://www.luogu.com.cn/problem/P3349) $\ \ \ \ \ \ \ \ 3.9.5$ 多项式中的牛顿迭代 $\ \ \ \ \ \ \ \ 3.9.6$ 多项式的求导与积分 $\ \ \ \ \ \ \ \ 3.9.7$ 多项式求逆 前置：$3.9.2\ ,\ 3.9.5$ $\ \ \ \ \ \ \ \ 3.9.8$ 多项式带余除法 前置：$3.9.7$ $\ \ \ \ \ \ \ \ 3.9.9$ 多项式对数函数 前置：$3.9.6\ ,\ 3.9.7$ $\ \ \ \ \ \ \ \ 3.9.10$ 多项式指数函数 前置：$3.9.9$ $\ \ \ \ \ \ \ \ 3.9.11$ 多项式幂函数 前置：$3.9.10$ $\ \ \ \ \ \ \ \ 3.9.12$ 多项式的 cdq 分治 前置：$1.5\ ,\ 3.9.3$ $\ \ \ \ \ \ \ \ 3.9.13$ 多项式三角函数和反三角函数（没用） $\ \ \ \ \ \ \ \ 3.9.14$ 多项式开方 前置：$3.9.7$ $\ \ \ \ \ \ \ \ 3.9.15$ $\text{MTT}$ 前置：$3.9.3$ $\ \ \ \ \ \ \ \ 3.9.16$ 线性齐次递推的加速 前置：$3.9.8$ $\ \ \ \ \ \ \ \ 3.9.17$ 多项式多点求值 $\ \ \ \ \ \ \ \ 3.9.18$ 多项式快速插值 前置：$3.9.17$ $\ \ \ \ \ \ \ \ 3.9.19$ 多项式复合逆 $\ \ \ \ $都学会了推荐[题1](https://loj.ac/problem/150)，[题2](https://www.luogu.com.cn/problem/P4389)。多项式算法我学得非常浅，需要了解一下 $exp/ln$ 的用法。 $\ \ \ \ 3.10$ 矩阵求逆 $\ \ \ \ 3.11$ $\text{MR}$ 素性测试和 $\text{PR}$ 质因数分解 [板子](https://www.luogu.com.cn/problem/P4718) $\ \ \ \ 3.12$ $\text{min}$~$\text{max}$ 容斥以及 $\text{kth-min}$~$\text{max}$ 容斥 [这题](https://www.luogu.com.cn/problem/P4707) $\ \ \ \ 3.13$ 其他数论技巧 $\ \ \ \ \ \ \ \ 3.13.1$ [转下降幂](https://www.luogu.com.cn/problem/P2791) $\ \ \ \ \ \ \ \ 3.13.2$ BM(Berlekamp Massey) 算法 $4.$ 图论 $\ \ \ \ 4.1$ 普通图问题 $\ \ \ \ \ \ \ \ *4.1.1$ 最短路 要掌握 $\text{dijkstra}$ 及其堆优化以及 $\text{spfa}$ 、$\text{floyd}$。注意：堆优化$/\text{dfs}\ $~$\text{spfa}$ 复杂度是指数级的，可以参考[这题](http://oj.gdsyzx.edu.cn/problem.php?id=3002)。另外推荐[这题](https://www.luogu.com.cn/problem/P5304)。注意 $01$~$spfa$ 可以写到 $O(n+m)$。 $\ \ \ \ \ \ \ \ \ \ \ \ 4.1.1.1$ [最短路计数](https://www.luogu.com.cn/problem/P1144)/次短路 $\ \ \ \ \ \ \ \ \ \ \ \ 4.1.1.2$ [二进制分组最短路](https://www.luogu.com.cn/problem/P5304) $\ \ \ \ \ \ \ \ *4.1.2$ 并查集 $\ \ \ \ \ \ \ \ \ \ \ \ 4.1.2.1$ 拆点并查集 [题](https://www.luogu.com.cn/problem/P2024) $\ \ \ \ \ \ \ \ \ \ \ \ 4.1.2.2$ 路径压缩和按秩合并 $\ \ \ \ \ \ \ \ \ \ \ \ 4.1.2.3$ 带权并查集 [题1](https://www.luogu.com.cn/problem/P2342)，[题2](https://www.luogu.com.cn/problem/P5024)，[题3](https://www.luogu.com.cn/problem/CF1140G) $\ \ \ \ \ \ \ \ *4.1.3$ $dag$ 的处理技巧，推荐[这题](https://www.luogu.com.cn/problem/P3573)。 $\ \ \ \ \ \ \ \ 4.1.4$ 仙人掌的处理技巧、圆方树 $\ \ \ \ \ \ \ \ 4.1.5$ *强连通分量、*双连通分量、[广义圆方树](https://www.luogu.com.cn/problem/CF487E)、2-sat $\ \ \ \ \ \ \ \ 4.1.6$ *欧拉回路和 $\text{BEST}$ 定理 $\ \ \ \ \ \ \ \ 4.1.7$ 数据结构优化建图，$**$[线段树优化建图](https://www.luogu.com.cn/problem/U68916)，[后缀树优化建图](https://www.luogu.com.cn/problem/P5284)。17年的 GDSOI 考到了主席树优化建图，题意：有1e5个人，每个人都有a,b,c三种能力值，若两个人对决，含有两种或以上能力值比对方高的那一方胜（不存在相等能力值）。直到剩下一人时结束，该人作为赢家，求可能会赢的人数 现在这题没了，说一下题意：1e5个点，1e5次连边操作（区间连区间），求单源最短路 $\ \ \ \ \ \ \ \ *4.1.8$ $\text{floyd}$的拓展（矩阵快速幂） [题](https://www.luogu.com.cn/problem/P3758) $\ \ \ \ \ \ \ \ *4.1.9$ 差分约束 $\ \ \ \ \ \ \ \ **4.1.10$ 最短路树和最短路 $\text{dag}$ $\ \ \ \ \ \ \ \ *4.1.11$ 分层图/拆点构图 [题1](https://www.luogu.com.cn/problem/P5060)，[题2](https://www.luogu.com.cn/problem/P3953)，[题3](https://www.luogu.com.cn/problem/P4822) $\ \ \ \ 4.2$ 计算几何 $\ \ \ \ \ \ \ \ **4.2.1$ 计算几何基本概念 包括向量、直线交、叉乘等 $\ \ \ \ \ \ \ \ 4.2.2$ 凸包和动态凸包 [题](https://www.luogu.com.cn/problem/P2521) $\ \ \ \ \ \ \ \ 4.2.3$ 半平面交 $\ \ \ \ \ \ \ \ 4.2.4$ 最小圆覆盖 $\ \ \ \ \ \ \ \ 4.2.5$ $k$ 维最大哈密顿距离 $\ \ \ \ \ \ \ \ 4.2.6$ $\text{kd-tree}$，也可以解决三维数点问题。 $\ \ \ \ \ \ \ \ 4.2.7$ 旋转卡壳 $\ \ \ \ \ \ \ \ 4.2.8$ 平面最近点对 $\ \ \ \ \ \ \ \ 4.2.9$ 自适应辛普森法 $\ \ \ \ \ \ \ \ 4.2.10$ 闵可夫斯基合并凸包 [题1](https://www.luogu.com.cn/problem/P4557)，[题2](https://www.luogu.com.cn/problem/P5073) $\ \ \ \ 4.3$ 树形问题 $\ \ \ \ \ \ \ \ *4.3.1$ $\text{MST}$ 包括与 $\text{dijkstra}$ 相似的 $\text{prim}$，最常用的 $\text{kruskal}$ 和复杂度 $O(mlog_2n)$ 并且可以变形到类似 [这题](https://www.luogu.com.cn/problem/CF888G) 的题目的 $\text{Boruvka}$ 算法。对于平面曼哈顿距离最小生成树好像有一种 $O(nlog_2n)$ 的算法。另外可以学习一下最小树形图的朱刘算法（省选算法）,似乎还有 $\text{tarjan}$ 更优算法。 $\ \ \ \ \ \ \ \ 4.3.2$ $\text{kruskal}$重构树 $\ \ \ \ \ \ \ \ *4.3.3$ $\text{LCA}$ 基础的包括 $O(nlog_2n)-O(log_2n)$的倍增、离线 $O(n+q)$ 的 $\text{tarjan}$，$O(nlog_2n)-O(1)$ 的 $\text{ST}$ 表，也可以学一下 $O(n)-O(1)$ 的基于 $+1/-1\ \text{rmq}$ 的 $\text{LCA}$ $\ \ \ \ \ \ \ \ *4.3.4$ $\text{dfs}$ 序的性质以及树上差分 子树的 $\text{dfs}$ 序连续；树上遍历指定点的最短路径是按照 $\text{dfs}$ 序排列指定点之后相邻两指定点的距离。 $\ \ \ \ \ \ \ \ 4.3.5$ 树链剖分 $\ \ \ \ \ \ \ \ \ \ \ \ $ 本质上有两点：其一，把边划分成轻边和重边（使得每个点最多向孩子连一条重边），如果选取子树最大的儿子连重边，那向父亲走时每次走过轻边都会至少使子树大小加倍，保证从任何一个点走到根最多 $log_2n$ 条轻边，这样可以保证暴力跳轻边与整条重链复杂度；其二，把同一条重链上的节点 $\text{dfs}$ 序弄成连续的，就可以用数据结构维护了。也可以做 $\text{LCA}$ ,而且代码好写常数小，建议常用。技巧：对点的修改直接线段树修改，对边的修改可以转化为对该边中深度高的点的修改。 $\ \ \ \ \ \ \ \ \ \ \ \ **4.3.5.1$ 维护点权 $\ \ \ \ \ \ \ \ \ \ \ \ **4.3.5.2$ 维护边权 $\ \ \ \ \ \ \ \ \ \ \ \ **4.3.5.3$ 换根树剖 [题1](https://www.luogu.com.cn/problem/P3979)，[题2](https://www.luogu.com.cn/problem/CF916E) $\ \ \ \ \ \ \ \ \ \ \ \ 4.3.5.4$ 动态 dp $\ \ \ \ \ \ \ \ \ \ \ \ 4.3.5.5$ 全局平衡二叉树 $\ \ \ \ \ \ \ \ *4.3.6$ 数据结构维护 $\text{bfs}$ 序 $\ \ \ \ \ \ \ \ 4.3.7$ 树上启发式合并 $(\text{dsu on tree})$ [题](https://www.luogu.com.cn/problem/CF741D) $\ \ \ \ \ \ \ \ 4.3.8$ $LCT$ $\ \ \ \ \ \ \ \ \ \ \ \ 4.3.8.1$ 普通 $LCT$：本质上也是轻重链剖分，但这里的轻重链剖分不再以 $size$ 为标准，而是以把根和指定节点连接 $(\text{access}$ 操作$)$。对于每一条重链用 $\text{splay}$ 中 $\text{child\&father}$ 两条边定位（注意，这里维护的是深度升序，并非直接相连关系），对于轻边用 $\text{father}$ 边单向定位。技巧：维护边权时拆边为点。 $\ \ \ \ \ \ \ \ \ \ \ \ 4.3.8.2$ 黑白连通块 $\text{LCT}$ 参考[这题](https://www.luogu.com.cn/problem/SP16580) $\ \ \ \ \ \ \ \ \ \ \ \ 4.3.8.3$ $\text{LCT}$ 维护圆方树 参考神鱼 $\text{NaCly\_Fish}$ 的[博客](https://www.luogu.com.cn/blog/NaCly-Fish-blog/solution-p4320)和[题](https://www.luogu.com.cn/problem/P5489) $\ \ \ \ \ \ \ \ \ \ \ \ 4.3.8.4$ $\text{toptree}$ 本质上是再用数据结构维护虚子树 $\ \ \ \ \ \ \ \ 4.3.9$ 虚树 参考[我的洛谷日报](https://www.luogu.com.cn/blog/SSerxhs/qian-tan-xu-shu) $\ \ \ \ \ \ \ \ 4.3.10$ 支配树 $\ \ \ \ \ \ \ \ 4.3.11$ 树同构 可以通过 $sort$ 孩子哈希值来保证孩子顺序无影响。 $\ \ \ \ \ \ \ \ 4.3.12$ 点分治和边分治和点分树 注意淀粉质找重心有很多错误写法，珂以见[这个讨论](https://www.luogu.com.cn/discuss/show/207604?page=3) $\ \ \ \ \ \ \ \ 4.3.13$ 生成树计数 $\ \ \ \ \ \ \ \ \ \ \ \ 4.3.13.1$ $\text{purfer}$ 序 通常与度数相关，推荐[题](https://www.luogu.com.cn/problem/P5219) $\ \ \ \ \ \ \ \ \ \ \ \ 4.3.13.2$ $\text{matrix-tree}$ 定理 可以拓展到树形图，注意特殊题目中依据行列式性质可以快速消元。[题](https://www.luogu.com.cn/problem/SP104)，注意模意义下的写法。 $\ \ \ \ \ \ \ \ 4.3.14$ 基环树 $\ \ \ \ 4.4$ 弦图与区间图 参考 cdq 的《弦图与区间图》[板子1](https://www.luogu.com.cn/problem/SP5446),[板子2](https://www.luogu.com.cn/problem/P3196) 比较冷门 $\ \ \ \ 4.5$ 二分图匹配 $\ \ \ \ \ \ \ \ 4.5.1$ 匈牙利算法、$\text{BM}$ 算法 $\ \ \ \ \ \ \ \ 4.5.2$ 二分图匹配系列定理和经典模型 $\ \ \ \ \ \ \ \ 4.5.3$ 二分图博弈 [题](https://www.luogu.com.cn/problem/P4055) $\ \ \ \ \ \ \ \ 4.5.4$ 带花树 $\ \ \ \ 4.6$ 网络流 $\ \ \ \ \ \ \ \ 4.6.1$ 最大流与最小割 $\ \ \ \ \ \ \ \ \ \ \ \ 4.6.1.1$ $\text{EK}$算法 $\ \ \ \ \ \ \ \ \ \ \ \ 4.6.1.2$ $\text{dinic/isap}$ 以及当前弧优化 $\ \ \ \ \ \ \ \ \ \ \ \ 4.6.1.3$ 预流推进 $\ \ \ \ \ \ \ \ \ \ \ \ 4.6.1.4$ 常用的黑白染色和最大权闭合子图的模型。[题1](https://www.luogu.com.cn/problem/P4313)，[题2](https://www.luogu.com.cn/problem/P3973) $\ \ \ \ \ \ \ \ \ \ \ \ 4.6.1.5$ 对偶图 [这题洛谷数据太水](https://www.lydsy.com/JudgeOnline/problem.php?id=1001) $\ \ \ \ \ \ \ \ \ \ \ \ 4.6.1.6$ 最小割树 $\ \ \ \ \ \ \ \ 4.6.2$ 费用流 $\ \ \ \ \ \ \ \ \ \ \ \ 4.6.2.1$ 普通费用流 黑白染色、修车模型、志愿者招募等 $\ \ \ \ \ \ \ \ \ \ \ \ 4.6.2.2$ $\text{zkw}$ 费用流 $\ \ \ \ \ \ \ \ \ \ \ \ 4.6.2.3$ 费用流消负圈 $\ \ \ \ \ \ \ \ \ \ \ \ 4.6.2.4$ 最小费用可行流 $\ \ \ \ 4.7$ 其他图论珂技 $\ \ \ \ \ \ \ \ \ \ \ \ 4.7.1$ 三元环计数 $\ \ \ \ \ \ \ \ \ \ \ \ 4.7.2$ 竞赛图的性质 $5$ 字符串算法 $\ \ \ \ *5.1$ 字符串哈希 $\ \ \ \ \ \ \ \ $ （在出题人良心的情况下）推荐使用 $\text{unsigned long long}$ 的自然溢出，字符串总长 $10^6$ 出错率不到万分之一，如果用 $\text{unsigned int}$ 自然溢出**不**出错率低于万分之一。但要小心被出题人卡自然溢出。（出错指的是存在两个冲突，不一定能够在询问中体现） $\ \ \ \ *5.2$ $\text{mp \& kmp \& exkmp}$ $\ \ \ \ \ \ \ \ $ 所谓 $\text{next}$ 数组其实就是后面用到的失配指针，也就是考虑失配的时候还能匹配到哪一段。 $\ \ \ \ 5.3$ 一些自动机 $\ \ \ \ \ \ \ \ *5.3.1$ $\text{AC}$ 自动机 [题](https://www.luogu.com.cn/problem/P2444) $\ \ \ \ \ \ \ \ 5.3.2$ 回文自动机 $(\text{PAM})$ $\ \ \ \ \ \ \ \ 5.3.3$ 序列自动机 [题1](https://www.luogu.com.cn/problem/P4112)，[题2](https://www.luogu.com.cn/problem/P4608) $\ \ \ \ \ \ \ \ 5.3.4$ $\text{kmp}$ 自动机 $\ \ \ \ 5.4$ 带失配符的字符串匹配 $\ \ \ \ \ \ \ \ $ 如果只有 $?$ 可以用 $\text{fft}$，如果有 $*$ 参考[这题](https://www.luogu.com.cn/problem/P3167) $\ \ \ \ 5.5$ 后缀全家桶 $\ \ \ \ \ \ \ \ 5.5.1$ 后缀数组 $(\text{SA})$ $\ \ \ \ \ \ \ \ \ \ \ \ $ 前置知识：基数排序。本质上是倍增+基数排序。 $\ \ \ \ \ \ \ \ 5.5.2$ 后缀平衡树 $\ \ \ \ \ \ \ \ \ \ \ \ $ 前置知识：$5.5.1$，本质上是用平衡树维护后缀数组 $\ \ \ \ \ \ \ \ 5.5.3$ 后缀自动机 $(\text{SAM})$ [题](https://www.luogu.com.cn/problem/P4770) $\ \ \ \ \ \ \ \ 5.5.4$ 后缀树 $\ \ \ \ \ \ \ \ \ \ \ \ $ 存在直接用反串 $SAM$ 构建法/ $ukkonen$ 构建法。 $ukk$ 法推荐[博客1](https://blog.csdn.net/zzuchengming/article/details/50935645)，[博客2](https://blog.csdn.net/zzuchengming/article/details/50935677) $\ \ \ \ \ \ \ \ 5.5.5$ ~~后缀仙人掌~~ $\ \ \ \ 5.6$ 最小表示法 [题](https://www.luogu.com.cn/problem/P1368) $\ \ \ \ 5.7$ $\text{manacher}$ 算法 $6$ 搜索和动态规划 $\ \ \ \ 6.1$ 搜索 $\ \ \ \ \ \ \ \ $ 如果万不得已需要搜索骗分，在可能的情况下打乱输入数据会有奇效。[题](https://www.luogu.com.cn/problem/P4212) $\ \ \ \ \ \ \ \ *6.1.1$ $\text{bfs}$ 和 $\text{dfs}$ $\ \ \ \ \ \ \ \ *6.1.2$ 搜索剪枝 [题](https://www.luogu.com.cn/problem/P1120) $\ \ \ \ \ \ \ \ \ \ \ \ $ 恰当的剪枝能优化不少分数，但剪枝一定要剪在瓶颈上，否则就是白花功夫甚至常数更大。 $\ \ \ \ \ \ \ \ 6.1.3$ $\text{A*}$ $\ \ \ \ \ \ \ \ \ \ \ \ $ $\text{OI}$ 中的主要用途是求 $k$ 短路（是错解）。 $\ \ \ \ \ \ \ \ 6.1.4$ 迭代加深 $\ \ \ \ \ \ \ \ *6.1.5$ 记忆化搜索 $\ \ \ \ \ \ \ \ \ \ \ \ $ 在大多数情况下和 dp 等价，在有许多无用状态的时候常数小，在需要遍历所有状态的时候常数大。 $\ \ \ \ \ \ \ \ 6.1.6$ 启发式搜索 $\ \ \ \ \ \ \ \ \ \ \ \ $ 主要是 ~~膜您~~ 模拟退火或者爬山，可以骗分，有时会有奇效。 $\ \ \ \ 6.2$ 动态规划 $\ \ \ \ \ \ \ \ *6.2.1$ 动态规划初步 $\ \ \ \ \ \ \ \ \ \ \ \ $ 包括背包九讲、区间 dp、坐标 dp 等。 $\ \ \ \ \ \ \ \ 6.2.2$ 数据结构优化 dp $\ \ \ \ \ \ \ \ \ \ \ \ *6.2.2.1$ 单调栈 $\ \ \ \ \ \ \ \ \ \ \ \ 6.2.2.2$ 单调队列 $\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ *$ 本质上是维护一个队列，使得队列的所有元素都**可能**有用。为什么说是可能呢？因为假如有一个转移点不仅转移的答案不优而且会先失效（即超过题目要求的转移范围），则这个点是不可能有用的。[题](https://www.luogu.com.cn/problem/P3957) $\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ *6.2.2.2.1$ 单调队列上二分 $\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ 6.2.2.2.2$ 斜率优化 $\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ *$ 本质上是维护二维数点的一个凸壳，对于每一个转移点都有一个特征值 $k$ （根据题目不同而不同，最终化出来的式子形如 $k\leq \frac{y_i-y_j}{x_i-x_j}$ ，也有可能是大于），然后对于满足上式则 $i$ 更优。在凸壳上，由于斜率单增（或单降），所以只要找到一个点使得恰好半边满足上式另外半边不满足即可。当 $k$ 单调递增时，可以用单调队列维护。推荐题目是普及组的题目。[题](http://oj.gdsyzx.edu.cn/problem.php?id=2982) $\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ **6.2.2.2.2.1$ 二分斜率 $\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ $ 对于不满足 $k$ 单调性的需要二分斜率。 $\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ 6.2.2.2.2.2$ 动态凸包维护 $\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ $ 对于不满足 $x_i$ 单调性的需要动态凸包维护。似乎也可以 cdq 分治，未了解是否有局限性。 $\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ $ 注意以上两种特殊情况可以结合。[题](https://www.luogu.com.cn/problem/P4655)。 $\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ 6.2.2.2.2.3$ $\text{wqs}$ 二分和 dp 凸优化。 $\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ **6.2.2.2.3$ 单调队列优化多重背包 $\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ $ 略快于二进制分组优化。[题（不要求提高会做）](https://www.lydsy.com/JudgeOnline/problem.php?id=4182) $\ \ \ \ \ \ \ \ \ \ \ \ *6.2.2.3$ 树状数组和线段树优化 dp。 $\ \ \ \ \ \ \ \ *6.2.3$ 四边形不等式优化 dp [题1](https://www.luogu.com.cn/problem/P1880)，[题2](https://www.luogu.com.cn/problem/P4767) $\ \ \ \ \ \ \ \ 6.2.4$ 状压 dp $\ \ \ \ \ \ \ \ \ \ \ \ *6.2.4.1$ 普通状压 $\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ $ 枚举子集的技巧： ```for (i=j;i;i=i-1&j)```，注意复杂度的分析，如果对所有的 $2^n$ 个集合枚举全体子集，那么复杂度是 $O(3^n)$ 的。 $\ \ \ \ \ \ \ \ \ \ \ \ 6.2.4.2$ 插头 dp （轮廓线 dp ） $\ \ \ \ \ \ \ \ **6.2.5$ 数位 dp $\ \ \ \ \ \ \ \ *6.2.6$ 树上 dp $\ \ \ \ \ \ \ \ \ \ \ \ 6.2.6.1$ 树上背包 注意可以快速转移，推荐[题1](https://www.luogu.com.cn/problem/P2014)要做到 $O(nm)$。[题2](https://www.lydsy.com/JudgeOnline/problem.php?id=4182)提高组不要求。 $\ \ \ \ \ \ \ \ \ \ \ \ 6.2.6.2$ 基环树 dp $7$ 博弈论 $\ \ \ \ *7.1$ 博弈论基本原理 $\ \ \ \ *7.2$ $SG$ 函数原理及应用 $\ \ \ \ \ \ \ \ $ 注意在大多数情况下 $\text{SG}$ 函数都不会只有 $0/1$ 两个取值，不要带小学奥数心态看待博弈论。 $\ \ \ \ **7.3$ 取石子游戏及其变种 推荐[洛谷日报](https://www.luogu.com.cn/blog/Wolfycz/qian-tan-suan-fa-bo-yi-lun-zong-ling-kai-shi-di-bo-yi-lun-post) $\ \ \ \ **7.4$ 博弈 dp $*8$ 贪心 $\ \ \ \ 8.1$ 贪心的思想 $\ \ \ \ \ \ \ \ $ 最好用到贪心的时候证明一下。 $\ \ \ \ 8.2$ 后悔贪心 [题1](https://www.luogu.com.cn/problem/P4053)，[题2](https://www.luogu.com.cn/problem/P4370)，[题3](https://www.luogu.com.cn/problem/P1792) $\ \ \ \ 8.3$ 部分贪心 即一类小规模会错大规模是对的的贪心算法。也可以用暴力写小数据贪心写大数据来骗分。