saver - 洛谷保存站

各位神犇的好东西都来我这里吃灰。

# $\Huge 1.$

**由于历史遗留原因，存在大量滥用 $\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
![](https://cdn.luogu.com.cn/upload/pic/64956.png)

$\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ $其中一些形态最深点深度较大，意味着访问这个节点代价比较高（因为访问都是从根往下找），如右图的节点 $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$ 部分贪心 即一类小规模会错大规模是对的的贪心算法。也可以用暴力写小数据贪心写大数据来骗分。

# $\Huge 2.$

# 各种套路

（不是非常全，想到就更）

## 数据结构

- 树状数组上二分：当前位置$pos$满足$2^b|pos$，枚举下一段长度$2^j$，其中$j<b$，节点$pos+2^j$上存的值为$[pos+1,pos+2^j]$中的贡献，如果当前值加上区间中的值满足条件，就跳到$pos+2^j$上继续枚举 [P6619 [省选联考 2020 A/B 卷] 冰火战士](https://www.luogu.com.cn/problem/P6619)

- 01trie整体+1：对于每个节点，交换01儿子，递归到原来的1儿子节点+1[P6623 [省选联考 2020 A 卷] 树](https://www.luogu.com.cn/problem/P6623)

- 单点修改，区间求和：有时修改和查询次数并不相同，可以进行平衡
    - $O(\log n)$修改，$O(\log n)$查询：树状数组
    - $O(1)$修改，$O(\sqrt n)$查询：分块，修改时只修改点值和块内和。查询时整块直接查块内值，散块暴力查询每个值
    - $O(\sqrt n)$修改，$O(1)$查询：分块，修改时维护块内前缀和，块间前缀和。查询整块用块间前缀和算，散块用块内前缀和算
    
- 并查集：01序列上，可以把0修改成1，询问某个位置前的第一个0

- 长度为$n$的序列，有$m$次区间染色操作，求最后序列的状态

倒序枚举每个操作，用并查集维护每个位置下一个没染的地方，暴力把区间内所有没颜色的地方染色，均摊复杂度为$O(n\operatorname\alpha(n))$

- [P3826 [NOI2017] 蔬菜](https://www.luogu.com.cn/problem/P3826)
    
- 动态开点平衡树：每个节点维护一个区间，等到分裂的时候再新建节点 [链接](https://www.luogu.com.cn/blog/Guoyh/dong-tai-kai-dian-Treap) [P7739 [NOI2021] 密码箱](https://www.luogu.com.cn/problem/P7739)

- 楼房重建，用线段树维护区间单调栈，线段树update的时候线段树二分找右儿子$\geq$左边最大值的单调栈，复杂度$O(n\log^2n)$ [从《楼房重建》出发浅谈一类使用线段树维护前缀最大值的算法——小粉兔](https://www.luogu.com.cn/blog/PinkRabbit/Segment-Tree-and-Prefix-Maximums) [P4198 楼房重建](https://www.luogu.com.cn/problem/P4198)，[U237227 带修区间单调栈长度（楼房重建加强）](https://www.luogu.com.cn/problem/U237227)

- 二进制分组：对于某些需要$O(n)$预处理，且不支持插入的数据结构（如AC自动机），可以用二进制分组实现均摊$O(\log n)$动态插入

新插入一个元素时，把它自己归为一组，每次判断左边的组大小是否和我一样，如果一样就合并，否则退出
    $$
    \{8,2,1\}\to\{8,2,1,1\}\to\{8,2,2\}\to\{8,4\}
    $$
    每个元素只会被重构$\log n$次，插入均摊复杂度$O(\log n)$

[CF710F String Set Queries](https://www.luogu.com.cn/problem/CF710F)
    
- 线段树维护历史和：转化成$kx+b$ [P8868 [NOIP2022] 比赛](https://www.luogu.com.cn/problem/P8868)

- 序列区间询问考虑能否线段树维护

- cdq分治实质：可以快速（如$O(n\log n)$）统计一个矩形内的贡献，需要统计一个直角三角形，将三角形拆成$O(\log n)$层矩形，每层矩形边长和为$O(n)$

![](https://cdn.luogu.com.cn/upload/image_hosting/ovuzom1e.png)

- 条状cdq：先将条分成若干个直角三角形，再做cdq

![](https://cdn.luogu.com.cn/upload/image_hosting/vsko9ghn.png)

- set-beats：线段树区间取min，区间加，查询区间和，查询区间最大值
	
    维护区间的最大值，严格次大值，最大值个数，区间和
    
    tag就是加法，最大值对$x$取min
    
    修改时，如果取min的值要大于次大值，直接改，否则往下递归
    
    不带区间加：$O(n\log n)$，带区间加：$O(n\log^2n)$常数极小

## 贪心

- 相邻交换法

- 将取min或取max的不等式转换为逻辑表达式，例如：

$$\max\{A,B\}\leq C\Leftrightarrow A\leq C \&\&B\leq C$$

- 可反悔贪心，把反悔选项扔到决策集合里 [P1484 种树](https://www.luogu.com.cn/problem/P1484)，[P2209 [USACO13OPEN]Fuel Economy S](https://www.luogu.com.cn/problem/P2209)

- 当限制为“到某时刻截止”时，可以考虑时光倒流，让限制变为“从某时刻开始”[P1954 [NOI2010] 航空管制](https://www.luogu.com.cn/problem/P1954)，[P3826 [NOI2017] 蔬菜](https://www.luogu.com.cn/problem/P3826)

- 超级钢琴：若干种决策，有依赖关系，且每种决策的收益小于其所依赖的前置决策

每次选择在所有当前可选的决策选一个收益最大的（用优先队列维护），将新的可选决策放入优先队列

[P2048 [NOI2010] 超级钢琴](https://www.luogu.com.cn/problem/P2048)，[P1315 [NOIP2011 提高组] 观光公交](https://www.luogu.com.cn/problem/P1315)，[BZOJ3784 树上的路径](https://darkbzoj.tk/problem/3784)
    
- 合并果子：决策之间满足某种单调性，用队列维护 [P1090 [NOIP2004 提高组] 合并果子](https://www.luogu.com.cn/problem/P1090)，[P2827 [NOIP2016 提高组] 蚯蚓](https://www.luogu.com.cn/problem/P2827)，

## 组合

- 范德蒙德恒等式运用$\sum\limits_{i=0}^n\begin{pmatrix}k\\i\end{pmatrix}\begin{pmatrix}n-k\\i\end{pmatrix}=\sum\limits_{i=0}^k\begin{pmatrix}k\\i\end{pmatrix}\begin{pmatrix}n-k\\n-k-i\end{pmatrix}=\begin{pmatrix}n\\n-k\end{pmatrix}$ [U183887 山区建小学期望版](https://www.luogu.com.cn/problem/U183887)

## 容斥

- 本质

$\pi$为$a$所有可能取值的集合，$p_i$为$a_i$所有可以取的值的集合，$U=\{x\in\mathbb{Z}|1\leq x\leq n\}$
  
	$$\begin{aligned}
        \sum\limits_{a\in\pi}\prod\limits_{1\leq i\leq n}[a_i\in p_i]&=\sum\limits_{a\in\pi}\prod\limits_{1\leq i\leq n}(1-[a_i\in p_i])\\
        &=\sum\limits_{a\in\pi}\sum\limits_{S\subseteq U}\prod\limits_{i\in S}[a_i\notin p_i](-1)^{|S|}\\
        &=\sum\limits_{S\subseteq U}(-1)^{|S|}\sum\limits_{a\in\pi}\prod\limits_{i\in S}[a_i\notin p_i]
     \end{aligned}
  $$

- min-max容斥

$$\max(S)=\sum_{T\subseteq S}(-1)^{|T|+1}\min(T)$$

- 证明：

$$\begin{aligned}
		\max(S)&=\sum_{i\in S}a_i\prod_{j\in S,j\neq a_i}[a_i>a_j]\\
		&=\sum_{i\in S}a_i\prod_{j\in S,j\neq a_i}(1-[a_i\leq a_j])\\
		&=\sum_{i\in S}a_i\sum_{T\subseteq S,i\in T}(-1)^{|T|+1}\prod_{j\in T}[a_i\leq a_j]\\
		&=\sum_{T\subseteq S}(-1)^{|T|+1}\sum_{i\in T}a_i\prod_{j\in T}[a_i\leq a_j]\\
		&=\sum_{T\subseteq S}(-1)^{|T|+1}\min(T)
		\end{aligned}$$
	
	- 期望线性性：

$$E(\max(S))=\sum_{T\subseteq S}(-1)^{|T|+1}E(\min(T))$$

[P3175 [HAOI2015]按位或](https://www.luogu.com.cn/problem/P3175)
    
- 选一个排列=1~n每个数都选=没有不选的数（虽然是废话，但是做容斥的时候可能有用）

- $m$个相同的球放进$n$个不同的盒子，但是每个盒子有上限：容斥，枚举一个集合超过上限

## 概率

- 若对于每个状态，有一个合法转移集合$S_1$，每次随机选取合法转移集合中的一个状态转移

对每个状态构造另一个集合$S_2$满足$S_1\subseteq S_2$，上述操作等价于每次从$S_2$中随机选取一个元素，若不合法再重选（重选时可以指定新的集合$S_3$满足$S_1\subseteq S_3$）

- 用六面骰子造出$1/5$的概率——每次骰到一个数，如果是1\~5的数就直接取，如果是6就再骰一遍
    - [[ARC114E] Paper Cutting 2](https://atcoder.jp/contests/arc114/tasks/arc114_e) 随机一个操作排列，若切到外面就跳过，若切到矩形就停止，每条线的贡献为它排在所有令它不合法的线前面的概率
    - [P5644 [PKUWC2018]猎人杀](https://www.luogu.com.cn/problem/P5644) 死了不能再杀$\to$死了还能继续杀
    - [USACO21DEC]T3 反着来，随机一个排列，若不合法则跳过$\to$每次在合法区间里随机选一个

- 搞清楚是事先做出所有决策还是决策可以动态调整

- 期望线性性：对于任意两变量$X,Y$（**不要求独立**），有$E(X+Y)=E(X)+E(Y)$

- 期望状态倒着设，因为不知道从各入边到达的概率，但知道从各出边出发的概率

## 排列

- 每个排列都是由若干个置换环组成的
- 考虑dp第i个位置有多少向后的箭头
- DP的时候考虑从小往大或从大往小插入每个元素 [P2401 不等数列](https://www.luogu.com.cn/problem/P2401)
- DP记录当前的值在剩下可取数中的排名 [P2467 [SDOI2010]地精部落](https://www.luogu.com.cn/problem/P2467)

## 序列DP

- 单调栈、单调队列、斜率优化、决策单调性，总之各种单调都要注意利用

- 如果将序列分成2部分，$f_{i,0/1}$表示决策完前$i$个，且第$i$个分到了$0/1$类，且$i$是当前一段的结尾，$i+1$和$i$不一样，这样枚举上一个点的时候就方便判断是否合法[CF1144G Two Merged Sequences](https://www.luogu.com.cn/problem/CF1144G)，[AT2292 [AGC009C] Division into Two](https://www.luogu.com.cn/problem/AT2292)

- $f_i=\min\{\max(g(j),w(j,i))\}$，$w(j,i)$随$j$单调递增，随$i$单调递增

显然转移点应该在$g$的单调栈上，每次转移点只用找$g$的单调栈和$w$两函数相交的点，用一个指针维护转移点[[蓝桥杯2021A]分果果](https://www.lanqiao.cn/problems/1459/learning/) [P1973 [NOI2011] NOI 嘉年华](https://www.luogu.com.cn/problem/P1973)

![](https://cdn.luogu.com.cn/upload/image_hosting/ffld7mso.png)

- 括号序列区间DP：枚举$l$左括号所匹配的右括号 [P7914 [CSP-S 2021] 括号序列](https://www.luogu.com.cn/problem/P7914)
  
- 一个一个消数：考虑一个区间最后一个消掉的数 [U188373 比赛](https://www.luogu.com.cn/problem/U188373)
  
- 区间消消乐 $f_{val,l,r}$表示目前正在消$[l,r]$，且$l$前面还跟着一段（包含$l$），其权值为$val$，转移就是消掉$l$前面这一段或者枚举下一个和$l$一起消的元素
  $$f_{val,l,r}=\max\left\{f_{w[l+1],l+1,r}+val,\max\limits_{l<k\leq r}\left\{f_{merge(val,w[k]),k,r}+f_{w[l+1],l+1,k-1}\right\}\right\}$$

[P5336 [THUSC2016]成绩单](https://www.luogu.com.cn/problem/P5336)
  
- 区间最值可以考虑笛卡尔树，区间最值就是两端点在笛卡尔树上的LCA，转化为树上问题[CF1580D Subsequence](https://www.luogu.com.cn/problem/CF1580D)

- 如果dp数组值域特别小，可以考虑把dp值计入状态，把原来的状态变成新的dp值 [CF1342F Make It Ascending](https://www.luogu.com.cn/problem/CF1342F)

- 延迟决策，遍历到某个点的时候，可以把它先晾着，到后面再决策

## 状压DP

- $3^n$枚举子集（问保安）

```cpp
    for (int s = 0; s < (1 << n); s++){
        for (int s1 = s; ; s1 = (s1 - 1) & s){
            //...
            if (!s1) break;
    	}
    }
    ```

- $f_{s1,s2}$表示上一个数前$n/2$位为$s1$，这一个数后$n/2$位为$s2$时的贡献 [P3773 [CTSC2017]吉夫特](https://www.luogu.com.cn/problem/P3773)，[[CSP-S2020初赛] 第 20 题](https://ti.luogu.com.cn/problemset/1035/training)

- 状压DP多记录一些中间状态帮助转移
	- [P3921 小学数学题](https://www.luogu.com.cn/problem/P3921) 多记录一维$j$表示当前集合前$j$位已经决策完成
   - [U86022 瘟疫公司（plague）](https://www.luogu.com.cn/problem/U86022) 记录当前的集合的大小就行，剩下一维记录可以转移的集合

- 强连通分量容斥：统计不合法的情况，枚举当前点集中拓扑序最小的强连通分量，这个强联通分量向点集中其他点都连出边 [CF1556F Sports Betting](https://www.luogu.com.cn/problem/CF1556F)

- 无向连通图容斥：枚举集合中某个特定点所在的连通块

令$f_{S,i}$为在集合$S$的生成子图中选$i$条边联通的方案数
    $$
    \forall u\in S, f_{S,i}=\begin{pmatrix}cnt(S)\\i\end{pmatrix}-\sum\limits_{u\in T,T\subsetneq S}\sum\limits_{j\leq i}f_{T,j}\begin{pmatrix}cnt(S-T)\\i-j\end{pmatrix}
    $$

[P3343 [ZJOI2015]地震后的幻想乡](https://www.luogu.com.cn/problem/P3343)

## 树

- 转移$f'_u=\operatorname{merge}(f_u,f_v)$

![](https://cdn.luogu.com.cn/upload/image_hosting/456187tf.png)

- 子树DP$f$，裤衩DP$g$

![](https://cdn.luogu.com.cn/upload/image_hosting/iilb5r1x.png)

- 子树合并：若每个节点$u$合并子树$v$时的复杂度为$O(sz_u\cdot sz_v)$，则总复杂度为$O(n^2)$

- 虚树上边权和：所有点按照dfn排序，相邻两个点的路径和再加上第一个点和最后一个点的路径和 [P5840 [COCI2015]Divljak](https://www.luogu.com.cn/problem/P5840)
  
- 入栈序（$dfn$）、出栈序（$T$）
    - $v$在$u$子树中：$dfn_u\leq dfn_v\leq dfn_u+sz_u-1$
    - $v$在$u$至根的路径中：$dfn_u\leq dfn_w$且$T_u\geq T_w$ [P2305 [NOI2014] 购票](https://www.luogu.com.cn/problem/P2305)

- 直径：从任意一点开始DFS，找到距离最远的点即为直径的一个端点，再从这个端点DFS找到距离最远的点，就是直径的另一个端点

- 多想一想这张图，每棵子树的深度都小于顶点和直径端点的距离[P2491 [SDOI2011]消防](https://www.luogu.com.cn/problem/P2491)

![](https://cdn.luogu.com.cn/upload/image_hosting/fuk9lsg9.png)

- 树的重心$\Leftrightarrow$所有子树大小小于一半$\Leftrightarrow$和所有点的距离和最小

- 一棵树的重心在这棵树以任意点为根的重链上 [P5666 [CSP-S2019] 树的重心](https://www.luogu.com.cn/problem/P5666)

- 修改一个点（路径）附近点的权值：父亲和重儿子暴力改，其他儿子打tag，查询时直接看链顶父亲的tag [CF487E Tourists](https://www.luogu.com.cn/problem/CF487E) [P7735 [NOI2021] 轻重边](https://www.luogu.com.cn/problem/P7735)

- $V-E$容斥，统计所有点的贡献，再减去所有边的贡献，就是所有连通块的贡献

对于树上一个联通子图$S$，有$[S\neq\phi]=\sum\limits_{v\in S}1-\sum\limits_{e\in S}1$
  
	- [P5291 [十二省联考 2019] 希望](https://www.luogu.com.cn/problem/P5291) 令连通块$S$内满足条件的点所构成的子图为$T(S)$，答案可表示为
	$$
		\begin{aligned}
			ans&=\sum_{S_1,S_2,\cdots,S_k}[T(S_1\cap S_2\cap\cdots\cap S_k)\neq\phi]\\
        &=\sum_{S_1,S_2,\cdots,S_k}(\sum_{v\in T(S)}1-\sum_{e\in T(S)}1)\quad S=S_1\cap S_2\cap\cdots\cap S_k\\
        &=\sum_v f(v)^k-\sum_e g(e)^k\quad f(v)=\sum_{v\in T(S)} 1,g(e)=\sum_{e\in T(S)} 1
		\end{aligned}
	$$
	- [[PKUWC2019]你和虚树的故事](https://www.luogu.com.cn/problem/U172646) 
	$$
    \begin{aligned}
			ans_i&=\sum_{c_1,c_2,\cdots,c_i}[T\neq\phi]\quad T=\bigcap_{j=1}^iS_{c_j}\\
			&=\sum_{c_1,c_2,\cdots,c_i}(\sum_{v\in T}1-\sum_{e\in T}1)\\
			&=\sum_v\begin{pmatrix}f(v)\\i\end{pmatrix}-\sum_e\begin{pmatrix}g(e)\\i\end{pmatrix}\quad f(v)=\sum_j[v\in S_j],g(e)=\sum_j[e\in S_j]\end{aligned}
  $$
	
- 点分树优化DP：用点分树将$dis(u,v)$拆成$dep[u]+dep[v]$ [[牛客挑战赛54] F-小葱的树](https://ac.nowcoder.com/acm/contest/11194/F?&headNav=acm)

- 点分治接单调队列，按照分治中心每个子树的高度排序，这样单调队列预处理复杂度就一定小于当前子树大小 [P4292 [WC2010]重建计划](https://www.luogu.com.cn/problem/P4292)

- 对于树上边集的一个子集，$u$和$v$在一个连通块中等价于$v$和最靠上能到达$u$的点分治中心在同一连通块

- [P5311 [Ynoi2011] 成都七中](https://www.luogu.com.cn/problem/P5311)

- 关于$dep(LCA(u,v))$：可以考虑修改$u$到祖先的链，查询$v$到祖先的链 [P5305 [GXOI/GZOI2019]旧词](https://www.luogu.com.cn/problem/P5305)，[P4211 [LNOI2014]LCA](https://www.luogu.com.cn/problem/P4211)
- 树上两路径是否点相交：若点相交，其中一条路径的LCA一定在另一条路径上
- 树上两路径是否边相交：
	![](https://cdn.luogu.com.cn/upload/image_hosting/71qeoai1.png)
	如图，若$dis(u_1,u_2)+dis(v_1,v_2)=dis(u_1,v_2)+dis(v_1,u_2)$则无边相交

否则边相交，且交出的链长度为$\frac 12|dis(u_1,u_2)+dis(v_1,v_2)-dis(u_1,v_2)-dis(v_1,u_2)|$
- 树上两点集交的直径$d(S_1\cup S_2)\subseteq d(S_1)\cup d(S_2)$其中$d(S)$表示点集$S$直径的两端点，两个点集交的直径两端点一定是原两集合的端点$\binom{4}{2}$种组合其中之一
[P4775 [NOI2018] 情报中心](https://www.luogu.com.cn/problem/P4775)

- dfs序背包：在dfs到$u$时，$f_v$表示只考虑dfs序上在$u$前的点时$v$子树对应的dp值 [T261510 和谐社会（harmony）](https://www.luogu.com.cn/problem/T261510)

- 树上相邻交换： [AT3957 [AGC023F] 01 on Tree](https://www.luogu.com.cn/problem/AT3957)

- “连通块大小乘积之和”：两个dp数组$f,g$ [博物馆记忆之树（memory）](https://www.luogu.com.cn/problem/U172624)
	- $f_u$代表在$u$子树内所有联通块大小乘积之和
   - $g_u$代表在$u$子树内不包括$u$所在联通块的所有联通块大小乘积之和
   - 递推
		- 相连：$f'_u=f_u\cdot g_v+f_v\cdot g_u$，$g'_u=g_u\cdot g_v$
		- 不相连：$f'_u=f_u\cdot f_v$，$g'_u=g_u\cdot f_v$
	- ![](https://cdn.luogu.com.cn/upload/image_hosting/897v0bhy.png)
	- 如图$A(x+y)B=(Ax)B+A(yB)$

## 图论

- 有向图的边可以分类成：树边、前向边、返祖边、横叉边

- 无向图的边可以分类成：树边、前向边（返祖边）

- 一个点到其他点的所有最短路径组成一个DAG

- 差分约束：如果同时存在$x_i+x_j\leq d$和$x_i-x_j\leq d$两种限制，将所有$x$按照$x_i+x_j\leq d$的边黑白染色，若染黑则差分约束时记录其负值，染白则记录正值 [P7515 [省选联考 2021 A 卷] 矩阵游戏](https://www.luogu.com.cn/problem/P7515)

- 线段树优化建图、倍增优化建图、ST表优化建图、前缀和优化建图：字面意思 [CF786B Legacy](https://www.luogu.com.cn/problem/CF786B)

- $O(n^2)$支配树：

1. 枚举每个点，从根节点不经过这个点DFS，求出这个点支配的点集
    2. 类似拓扑排序，每一轮选择一个点当且仅当所有支配它的点已经遍历过了

[P7520 [省选联考 2021 A 卷] 支配](https://www.luogu.com.cn/problem/P7520)
    
- 圆方树：无向图，有诸如删点后是否可达的叙述，可以考虑在圆方树上搞

- 两点在圆方树路径上的圆点是这两个点在原图中路径的必经点 [P5058 [ZJOI2004]嗅探器](https://www.luogu.com.cn/problem/P5058) [P4082 [USACO17DEC]Push a Box P](https://www.luogu.com.cn/problem/P4082)

- 两点在圆方树路径上所有方点的相邻点是这两点所有简单路径可能经过的点 [P4630 [APIO2018] Duathlon 铁人两项
](https://www.luogu.com.cn/problem/P4630)

- 矩阵树定理可以求
	$$\sum_{T\text{是生成树}}\prod_{e\in T}w_e$$
	
	一般取$w_i=1$，必要时可以令$w$为一个多项式

令$w=ax+b$，乘法为$\bmod x^2$意义下的乘法，可以求出所有生成树的权值和 [P6624 [省选联考 2020 A 卷] 作业题](https://www.luogu.com.cn/problem/P6624)

## 计数

- 容斥
    - 第一次到达状态$S$的方案：到达$S$的方案减去之前到过但又回来的方案数 [U105245 随机游走3](https://www.luogu.com.cn/problem/U105245) [P8208 [THUPC2022 初赛] 骰子旅行](https://www.luogu.com.cn/problem/P8208)

- 本质不同子序列个数：$f_i=2f_{i-1}-f_{pre[i]-1}$，其中$f_i$表示前$i$个元素的不同子序列个数

钦定相同的子序列选取最后一个计数，每次决定第$i$个选不选，并且排除上一个选了和$i$同色的元素却没选$i$的情况，因为这样就会使统计的子序列不是最后一个，因为$f_{i-1}$满足所统计的子序列在前$i-1$中是最后一个，所以只可能是选了$pre[i]$没选$i$

选$i$的方案数：$f_{i-1}$，不选$i$的方案数：$f_{i-1}-f_{pre[i]-1}$

- 不同维度间相互独立（但是可能没有完全独立） [P5289[十二省联考 2019]皮配](https://www.luogu.com.cn/problem/P5289)

- 统计贡献的思想非常重要，考虑每个元素对答案所做出的贡献

- 如果要计数若干个相似问题的和，且问题可以用若干线性变换解决，可以考虑将初始向量直接相加，再做一遍原问题 [CF1810G The Maximum Prefix](https://www.luogu.com.cn/problem/CF1810G) [P3352 [ZJOI2016]线段树](https://www.luogu.com.cn/problem/P3352)

$\sum_i(\vec{v_i}\times A)=(\sum_i\vec{v_i})\times A$

## 字符串

- 一个长$n$的字符串的所有border可以分成$\log n$个等差数列

## 矩阵乘法

- 不满足交换律，注意乘法顺序

- 广义矩阵乘法需要满足的条件

定义广义矩乘为
    $$
    (A\times B)_{i,j}=\bigoplus\limits_{k=1}^{m}A_{i,k}\otimes B_{k,j}
    $$
    则其结合律、分配率依赖于
    $$
    \begin{cases}
    (a\oplus b)\otimes c=a\otimes c\oplus b\otimes c\\
    a\otimes(b\oplus c)=a\otimes b\oplus a\otimes c\\
    a\oplus b=b\oplus a\\
    (a\oplus b)\oplus c=a\oplus(b\oplus c)
    \end{cases}
    $$
    也就是$\otimes$和$\oplus$之间的分配率、$\oplus$的交换律和结合律

常见广义矩乘
    
    - $a\oplus b=\min(a,b),a\otimes b=a+b$ [P2886 [USACO07NOV]Cow Relays G](https://www.luogu.com.cn/problem/P2886)
    - $a\oplus b=a\operatorname{xor}b,a\otimes b=a\operatorname{and} b$ [P6569 [NOI Online #3 提高组] 魔法值](https://www.luogu.com.cn/problem/P6569)
    - $(a\oplus b)_{i,j}=a_{i,j}+b_{i,j},(a\otimes b)_{i,j}=\sum_{k=1}^ma_{i,k}\cdot b_{k,j}$（矩阵每个元素都是一个子矩阵）[P6772 [NOI2020] 美食家](https://www.luogu.com.cn/problem/P6772) [P5319 [BJOI2019]奥术神杖](https://www.luogu.com.cn/problem/P5319)

## 动态DP（DDP）

- 将DP的式子改成一个向量乘上一堆矩阵的形式，用数据结构维护 [CF1609E William The Oblivious](https://www.luogu.com.cn/problem/CF1609E)
- 树上DDP：$\vec{f}(u)=\vec{f}(hs(u))\times F_u$，其中$F_u$只与$u$的所有轻儿子有关 [P4719 【模板】"动态 DP"&动态树分治](https://www.luogu.com.cn/problem/P4719)

## 根号

- 根号分治
- 对于$q$个二元询问$(u,v)$，若满足$(u,v)$的答案等于$(v,u)$的答案，对于每个$u$，可以经过$f(u)$时间预处理后以$g(v)$时间回答询问$(u,v)$，则可以在$O(\sqrt q\sum_ig(i)+\sum_if(i))$时间回答所有询问 [共同好友乱搞解法](https://www.luogu.com.cn/blog/Guoyh/bao-li-chu-qi-ji)

## 网络流

- 限制点的流量：拆点，两点间连边的限制为点流量限制
- DAG最小路径覆盖：拆点，每个点的流量下限为1，跑有上下界最小流
- 有若干形如$a[b_1]+a[b_2]+\cdots+a[b_k]\in[L_i,R_i]$的限制，限制可分为两组，每个$a[i]$在同一组中只出现一次，且每个$a[i]$取值范围在$[l_i,r_i]$
    - 每个$a[i]$建两个点，中间的边按照它的取值范围设定上下界
    - 对于第一组中的限制，建点，从源点到这个点连一条$[L_i,R_i]$的边，从这个点向所有受限制的点连一条容量无限的边
    - 对于第二组中的限制，建点，从这个点到汇点连一条$[L_i,R_i]$的边，从每个受限制的点连到这个点一条容量无限的边
    - [P4486 [BJWC2018]Kakuro](https://www.luogu.com.cn/problem/P4486)
- 二分图相关：
    - 最小点覆盖=最大匹配（最小割）
    - 最小边覆盖=N-最大匹配（除了匹配，每条边覆盖一个点）
    - 最大独立集=N-最大匹配（除了最小点覆盖的点）
- 最大权闭合子图：有$n$个点，有$m$个限制$(u,v)$表示取点$u$就一定要取点$v$，每个点有一个权值$w_i$（可正可负），求一个满足限制的选点方案使选点权值和最大
    - 对每个限制$(u,v)$，连一条$(u,v,\infin)$的边，对每个$w_i\geq 0$的点，先给答案加上$w_i$，再连边$(S,i,w_i)$，若$w_i<0$，则连边$(i,T,|w_i|)$，最后答案减去最大流
    - 证明（感性）：最小割
    - [CF1146G Zoning Restrictions](https://www.luogu.com.cn/problem/CF1146G)
    - 正权点同时连向若干个点等价于这些点全选时权值增加
    - 对于两个点，通过上述方法拼上改变两点本身的权值，可以实现：
		|u\v| 0 | 1 |
		|:-:|:-:|:-:|
		| 0 | + | - |
		| 1 | - | + |
	- [P8215 [THUPC2022 初赛] 分组作业](https://www.luogu.com.cn/problem/P8215)
- 切糕模型
	- **upd**：切糕模型可以转化为最大权闭合子图
		- $(u,v)\to(u,v-1)$
		- 限制$x\ge y+k$：$(y,i)\to (x,i+k)$
		- 钦定选$(u,1)$：$S\to (u,1)$（dfs删点常数会更优一些）
		- $w'(u,v)=w(u,v)-w(u,v-1)$
   - 以下是经典做法：
	- ![](https://cdn.luogu.com.cn/upload/image_hosting/gnkt9wta.png) （盗题解图）
	- 对于每个变量，每种取值都开一个点
	- 连边：
    	- $S\to (x,1),flow=\infin$
    	- $(x,lim+1)\to T,flow=\infin$
    	- $(x,i)\to (x,i+1),flow=weight(x,i)$
    	- $(x,i+1)\to (x,i),flow=\infin$
    	- $\forall u\geq v+k,(v,i)\to (u,i+k),flow=\infin$
  	- 做最小割，显然每个变量$S$只可达一个前缀，只割一条边，若割$(x,i)\to(x,i+1)$，则代表$x$取值为$i$
	- [P3227 [HNOI2013]切糕](https://www.luogu.com.cn/problem/P3227)

- 平面图最小割转最短路：（如果原图是有向图，对偶图中的边只能全是从原图一条边的左边到右边或全是从右边到左边）[P4001 [ICPC-Beijing 2006]狼抓兔子](https://www.luogu.com.cn/problem/P4001?contestId=38905)

## 其他

- 所求答案数组单调且值域不大，二分每一个相同段的长度
	- [CF1039D You Are Given a Tree](https://www.luogu.com.cn/problem/CF1039D) 可以$O(n)$求出一个答案，根号分治，长度大于$B$的答案不超过$n/B$，二分每一段的长度，取$B=\sqrt{n\log n}$，总复杂度为$O(n\sqrt{n\log n})$

- $x=p_1^{a_1}\times p_2^{a_2}\cdots\times p_k^{a_k}$，可以将每个质因子视作一维，将$x$视作一个高维的点，坐标为$(a_1,a_2,\cdots,a_k)$ [U184638 仪式感 (sor)](https://www.luogu.com.cn/problem/U184638)，[P8255 [NOI Online 2022 入门组] 数学游戏](https://www.luogu.com.cn/problem/P8255)
    
- 高维前缀和：枚举每一维，做这一维的前缀和

可以处理子集权值和，约数权值和

二维的例子：

```cpp
    for (int i = 1; i <= n; i++){
        for (int j = 1; j <= m; j++){
            a[i][j] += a[i - 1][j];
    	}
    }
    for (int i = 1; i <= n; i++){
        for (int j = 1; j <= m; j++){
            a[i][j] += a[i][j - 1];
    	}
    }
    ```
    
- $a[1...n]$中$a_i\|a_j$最大值：对每个$a_i$，取其补集$U-a_i$，从大到小枚举补集的每一位，如果有元素为当前已选集合的超集的话就选

正在渲染内容...