禁止废话
时空
时间复杂度的计算一定要注意有没有什么 \(\sum\) 的限制，有没有隐含的条件（如自然根号）。
空间不够用的情况下可以考虑分批处理独立的部分。常见于各种 ds 题。
DP
状态值域互换是很常见的技巧。
某些题目中转移可能是比较奇怪的偏序集，扯清转移顺序很重要：JOI2012 kangaroo，UR#13 Ernd。
费 用 提 前 计 算。
CF1810G The Maximum Prefix：最大/小前缀和的刻画方式；反向贡献；对相似的转移通过转化一起转移。
背包 dp
大多数背包 dp 是 \((\min/\max,+)\) 状物，统计方案的是 \((\times,+)\) 状物。
插入一个元素相当于和二项式做卷积 \(O(m)\)，合并相当于卷积。\((\times,+)\) 存在逆运算，可以支持删除。注意查两个背包合并后的单点是 \(O(m)\) 的。
\((\min/\max,+)\) 背包实际上是维护半群运算，所以会有双栈维护队列（JZOJ6358 小ω的仙人掌）、DSU on tree（即流传的 dfs 序优化）优化树上背包、点分治做路径背包（旅行）、挂到猫树上等技巧。
对于容量 \(m\leq n\) 的树上背包可以做到 \(O(nm)\)；通过重剖继承重儿子的思想空间可以做到 \(O(m\log n)\)。
概率期望 dp
如果带环转移不取模，在时限足够的情况下可以多次迭代，期望如果存在一定是收敛的。
期望线性性质 \(E(x+y)=E(x)+E(y)\)，独立的可以拆开算：BZOJ4318 OSU!，ARC165E Random Isolation，CF1864H Asterism Stream。
dp 优化
斜率优化具体情况具体分析，抓住 \(x,y,k\) 的单调性。
wqs 不只是求单点。如果求一个凸包上多点最值，可以先找到整个凸包最值，向左向右找到第一个在给定集合内的横坐标求两次单点即可：CF2125F Timofey and Docker。
决策单调性分治可以在外面套 CDQ 实现半在线。另外看到了个单 log 做法。
不好优化（如没有决策单调、没有凸性等常见性质）的半在线可以先 CDQ 变成离线。
通过重定义矩阵乘法可以用矩阵快速幂优化每轮转移一样的 dp：CF461E Appleman and a Game。
连续段 dp
转移顺序很重要。常见于排列计数、类似排列的偏序集计数。
在钦定转移顺序后，可以将状态简化为若干形态类似的段，能快速求出新建一段、合并两段、接在一段开头或末尾的贡献。在插入难做时可以考虑。
例题引用。
数据结构
信息维护
注意到 \(\gcd\) 做差分，异或做异或差分等不会对答案有整体影响。
放宽限制可能答案不变但更好维护。
并查集
可撤销带权并查集由于不能路径压缩，每次查询一个点的权值要老老实实算一遍：CF2104G Modulo 3。
树上问题
不要忘了括号序列。括号序的一个应用：左括号加一，右括号减一，则一条根链转化为一段前缀。
毛毛虫剖分，改变标号方式来取得一些连续的性质：「GLR-R3」谷雨，数据结构。
一类树上贪心问题：QOJ7588 Monster Hunter，[Ynoi2006] spxmcq。
计数
组合意义天地灭，代数推导保平安。
常用方法：通过构造单射，钦定一个好做的计数结构。
对贡献不相关的部分分阶段计算贡献：[COTS 2025] 数好图 / Promet。
考虑可能的系数合并或抵消。
容斥
底层逻辑：某个（实际）方案在某个算法下会被某个（钦定）方案算多少次。
两个方向的类似限制可以容斥成一个方向。
dp
考虑：如何划分阶段，计算贡献需要什么，是否可以分开计算贡献。
图计数
划分阶段是底层逻辑。
有标号 DAG 计数考虑容斥，钦定入/出度为 \(0\) 的部分。[省选联考 2024] 重塑时光，[清华集训 2014] 主旋律。
最小生成树，考虑 Kruskal 的过程：省选联考 2025 岁月，JSOI2008 最小生成树计数。
集合幂级数
集合幂级数 \(\exp\) 的组合意义：划分为若干个非空集合的带权方案数。逆运算 \(\ln\)，如连通性生成子图计数。
占位多项式的应用：CF2070F Friends and Pizza。
形式幂级数
OGF 组合意义：\(\sum\limits_{i=0}^{\infty}F^i=\dfrac{1}{1-F}\)。
EGF 组合意义：\(\sum\limits_{i=0}^{\infty}\dfrac{F^i}{i!}=e^F\)。
对于 \(h_k=\sum\limits_{i+j=k}f_ig_j2^{ij}\) 状物，可以拆成 \(\frac{(\sqrt 2)^{k^2}}{(\sqrt 2)^{i^2}(\sqrt 2)^{j^2}}\)。更优美的做法是 \(\dfrac{2^{\binom{k}{2}}}{2^{\binom{i}{2}}2^{\binom{j}{2}}}\)，不需要二次剩余。
排列计数
一些问题中，某些变量在对当前状态无影响但是对后面状态有影响时可以延迟钦定。
对排列的划分计数，常用单射钦定技巧确定计数结构。
字符串
EXKMP 刻画后缀与原串的 LCP，SA 刻画所有后缀 LCP，刻画了 LCP 相当于刻画了相对大小关系。
KMP 自动机：指鹿为马。
能用 Trie 不要用 ACAM，能用 SA/KMP/EXKMP 不要用 SAM。
图论
Hall 定理（PKUSC2022 撸猫，某模拟赛 T4）。
Dilworth 定理：偏序集内部最小链划分数等于最长反链大小，最长链大小等于最小反链划分数。
区间图是弦图，弦图的最小染色数等于最大团。
最小割模型上边 \((u,v,w)\) 的意义：若 \(u\in S,v\in T\)，则有 \(w\) 的代价。
二分图博弈，先手获胜当且仅当起始点是最大匹配的关键点。二分图最大匹配关键点满足在一个最大匹配中，不存在从未匹配点出发到达该顶点的偶数长度的交错路。
最小生成树
Boruvka 每次求的是每个连通块向外连出来的最小边权而非每个点。
杂项
求 \(\dfrac{a}{b}\) 对 \(p\) 取模时，如果 \(b\) 不存在逆元但是比较小，可以求 \(a\) 对 \(p\times b\) 取模的结果，最后再除以 \(b\) 规避模数域下的除法。
随机赋值+和哈希/异或哈希有奇效（[PA 2017] 商旅 / Osady i warownie，[CSP-S 2022] 星战）。
某些 \(\max/\min\) 还有绝对值该拆就拆。\(\max\{|x-y|\}\) 状物是假的，绝对值可以直接扔掉，但是 \(\min\{|x-y|\}\) 不行。
注意可能的自然根号 / log。
复杂序列 mex 问题考虑极小 mex 区间。
凸优化：反悔贪心，费用流，wqs 二分，闵可夫斯基和。
浙公网安备 33010602011771号