| 整体二分 |
P3527 |
离线；每次询问可以二分 |
| CDQ分治三维偏序 |
P3810 |
二维平面转化为三维偏序 |
| 树哈希 |
P4323 |
需要判断树同构；合并子树哈希的方式稳定性高，但不方便维护 |
| 插头DP |
P5056 |
数据范围小；答案转移仅需要维护联通性 |
| BSGS |
P2485 |
高次同余方程 |
| 矩阵快速幂 |
P4159 |
转移式为一次；转移式和转移位置无关 |
| CDQ分治维护斜率优化 |
P4027 |
k 和 b 均不单调 |
| 高维树状数组 |
CF341D |
| Kruscal重构树 |
P4768 |
路径最大值最小；或满足边权范围的路径 |
| 对偶图最小割 |
P4001 |
注意平面图画在平面之后不一定连边都是直线 |
| 2-SAT |
P4171 |
同时满足多个每个由或连接的条件组 |
| 莫队 |
P1494 |
|
| Hall定理判断完美匹配 |
P3488 |
左边一个点匹配右边一个区间时，右边每个区间都成立即可 |
| 差分约束 |
P3275 |
仅一个集合中数之间的不等式组 |
| 双指针最小表示法 |
P1368 |
| 带权并查集 |
P1196 |
| Lucas定理 |
P3807 |
模数较小（质数） |
| CRT |
P1495 |
模数不是质数，但好分解；或线性同余方程组（互质） |
| exCRT |
P4777 |
|
| exLucas |
P4720 |
|
| 虚树 |
P2495 |
多次决策点树形DP；解决树上点编号区间时可虚树合并 |
| 上下界网络流 |
P5192 |
| 点分治 |
P3806 |
求树上路径有关信息；求距离和的容斥模型 P3241 |
| 线段树合并 |
P4556 |
可以优化数组的空间同时完成数组加；需要保留原始信息时可以可持久化；不能一棵树重复合并到其它位置 |
| 线段树优化建图 |
CF786B |
建图存在“区间” |
| 圆方树 |
CF487E |
无向图 |
| 换根DP |
CF337D |
问题与树上一个特殊点有关；特殊点性质方便转移 |
| 树上背包 |
P4362 |
另一种形式 P4516 |
| 矩阵树定理 |
P4111 |
生成树个数 |
| DLX（精确覆盖） |
P4929 |
|
| 序列分块 |
P2357 |
线段树不好做，强制在线等 |
| 二分图匹配 |
P2756 |
只跑一次匈牙利比 Dinic 慢，但匈牙利可以完成钦定匹配之类的操作 |
| AHU算法 |
P5043 |
把树双射成字符串的方法，其实可以被树哈希替代 |
| 杜教筛 |
P4213 |
需要求数论函数前缀和；可以找到方便求前缀和的函数卷成另一个方便求前缀和的函数 |
| 李超树 |
CF932F |
| 子集容斥 |
P4336 |
需要时可以把容斥系数乘进 DP 中 ARC101C |
| 二维凸包 |
P2742 |
| 线性基 |
P3812 |
有关子集中数字的异或和 |
| 卷积优化DP |
P3321 |
DP式中出现 f_j 与 f_{i-j}相乘等 |
| 二项式反演 |
P4859 |
题目要求一部分成立，一部分不成立；一部分成立容易求得 |
| 单位根反演 |
LOJ6485 |
求符合某些同余式的下标的点值和；同余转化为倍数 |
| 同余最短路 |
P3403 |
最优化的完全背包；某个物品大小的整余系非常小 |
| 长链剖分优化DP |
P3899 |
树上DP有一维为子树中链的深度 |
| 点分树 |
P3241 |
多次点分治 |
| 弦图染色（mcs算法） |
P3196 |
| Prufer序列 |
P2624 |
需要计算生成树个数 |
| 基环树DP |
P2081 |
| min-max容斥 |
P4707 |
大部分为期望；将全部发生的期望转化为某事第一次发生的期望 |
| 扩展欧拉定理 |
P4139 |
指数上含有指数；模数不为质数 |
| 动态树维护子树 |
P4219 |
| 树分块 |
P2137 |
需要维护连通性区域如子树 |
| K-D Tree |
P4148 |
维护k维偏序（不一定是大小比较）；查询对所有维度有单调性的条件 |
| 期望DP |
CF24D |
取模用高斯消元；精度小可以用多次dp |
| 模拟费用流 |
P5470 |
费用流可做但过不了；每条边有显著的优先级 |
| 闵可夫斯基和 |
P4557 |
|
| 辛普森积分 |
P4207 |
求平面面积 |
| 玄学退火 |
P4044 |
每个点的贡献之间影响不大 |
| dp套dp |
P4590 |
高维DP压缩状态 |
| 旋转卡壳 |
P3187 |
在凸包内；求直径这样两端点不会方向相反地移动的东西 |
| 动态DP |
P6021 |
DP带修改且可以递推解（神奇的是带min的DP式竟然也行） |
| 后缀数组LCP |
P4070 |
字符串大小比较/数量比较等；O(1) 求后缀LCP |
| 自然数幂和 |
P3270 |
| 最长公共子串 |
CF235C |
也不一定是最长，求一个串的某一位在一个/一些串中的位置 |
| 树上启发式合并 |
CF600E |
信息可继承；另一种启发式合并写法 CF1709E |
| MR与PR |
P4718 |
|
| 带悔贪心 |
P3620 |
|
| 前缀线性基 |
P3292 |
构造区间线性基；利用性质为线性基当中的数两两无关 |
| 虚树路径和 |
P3320 |
树上遍历全部关键点的距离、树上路径的并都是这个 |
| 最小树形图 |
P4716 |
|
| 朱刘定理 |
P3244 |
有向无环图生成树 |
| LCT维护最小生成树 |
P3366 |
|
| 高维前缀和 |
CF449D |
用来替代与或的FWT |
| 动态点分树 |
P3920 |
似乎只能操作加入新点 |
| 平面图 |
P4073 |
连边都是直线的才好做；这个题保证平面图联通可以这么做，不保证要每个连通块跑一遍 |
| 点值优化卷积 |
P4365 |
多项式次数较低 |
| 回滚莫队 |
ATJOI C |
只有加入操作，但常数是莫队的三倍左右的莫队 |
| 半平面交 |
P4196 |
|
| 三维凸包 |
P4724 |
三维计算几何不碰为好 |
| 模拟退火 |
UVA10228 |
函数连续且不单调（虽然这个题似乎是单调的） |
| 二次离线莫队 |
P4887 |
莫队无法做到 O(1) 更新答案，但可以拆贡献（比如贡献为区间内两个数产生） |
| min_25筛 |
P5325 |
积性函数前缀和；质数情况是关于这个质数的很低次多项式，只有一个因子情况好搞 |
| 洲阁筛 |
LOJ572 |
进行数论分块套min_25筛 |
| 伯努利数 |
P6271 |
|
| EGF |
P5339 |
|
| 鞅与停时定理 |
CF1025G |
终止状态不能继续转移 |
| 最小割树 |
P4897 |
|
| 摩尔投票 |
P3765 |
绝对众数 |
| 线段树分治 |
P3733 |
可离线；操作间存在关联同样可以维护（确定扫描顺序） |
| 完美三角剖分 |
SGU383 |
平面点的最小生成树的边都是DT里的 |
| 珂朵莉树 |
CF817F |
区间赋值；比较方便分析势能 |
| 阶梯博弈 |
ACW238 |
|
| DAG计数 |
P6295 |
|
| 根号分治 |
P3591 |
|
| 硬币博弈 |
CF494E |
按某些将某些01状态翻转，但需要保证最右边是0，则每个0格子为子游戏 |
| 最长反链 |
P5939 |
最长反链是最小链覆盖，这里偏序可以看作 DAG 上的可达性，求的就是最小路径覆盖 |
| 边分树合并 |
P4565 |
在边分树上可以拆成左右子树各选一个的贡献 |
| 最远点对 |
P4775 |
边权非负；形式为边权+两端点点权，点权可以为负数 |
| 支配点对 |
P7361 |
要求数区间内点对数量 |
| 拟阵交 |
CNNCT2 |
|
| 斯特林数幂和 |
P4827 |
这部分下降幂和指数幂的转化，以及自然数幂和；大概幂的某一维很小就想到斯特林数 |
| 二分图最大权完美匹配 |
P6577 |
KM 算法不依赖非负，可以加 -inf 的边转化为完美匹配 |
| 反比例函数贪心 |
P3236 |
两维相乘求最小值；求凸壳可以使用分治法，复杂度也许是 O(\sqrt{V}) |
| 二分图边染色 |
CF600F |
可以用来处理 k-正则二分图 问题，即找 k 组边不交的完美匹配 |
| EGF的 \exp |
P6295 |
组合意义是把 n 个球划分到若干个盒子里，盒子相同球不同 |