常见套路总结

图论

1. 树上一个点集的LCA为这个点集中DFS序最大点和最小点的LCA。CF1062E
2. 最小生成树上，任意两点之间唯一路径上边权最大值，一定是整张图上，这两点之间任意路径上边权最大值的最小值。P4768
3. 修改任意一条边求最短路，其修改后的最短路径最多不经过原图最短路树上的一条边。CF1163F
4. 如果看到描述点与点之间关系的题，果断考虑建图求解。
5. 如果遇到dp题，转移时下标设计取模（有后效性），可以考虑用同余最短路求解。P2371 AT_arc084_b
6. CF97E
7. 对于树上前缀问题，可以先考虑是一条链的情况怎么做（dp之类的），然后考虑把树上前缀看作若干条链合并起来看能不能做。P5658
8. 重构图。（例如最短路问题）考虑拆点/拆边、边化点点转边。P1613 AT_abc164_e P6822 CF1163F
9. 

字符串

1. 名言：提高组看到字符串，几乎无脑建Trie，然后转化为树上问题（dp、重构树等等）AT_arc201_c

平均数

1. 平均数问题可以尽量考虑将其转化为判定性问题。
2. 常见策略是把整个数列都减掉平均数。序列可以转化为01序列之类的（和平均数相等的元素都是0）。P9509

01分数规划

1. 有若干个(a[i],b[i])，要选出若干个使得$\dfrac{\sum a}{\sum b}$最大/最小。

题解以最大为例：
设Σv[i]/Σc[i]>=x，则Σv[i]>=Σc[i]*x，Σv[i]-Σc[i]*x>=0，Σ(v[i]-c[i]*x)>=0
发现x具有单调性
考虑二分最大的满足条件的x，check时把所有v[i]-c[i]*x放进数组里，然后取最大的m个求和，若总和大于等于零，则该方案可行

并查集

1. 快速找下一个合法位置。考虑用类似链表的写法，每个元素都指向其下一个合法位置，考虑用并查集的路径压缩天然性质优化。P8686
2. 无向图连通性一般选择用并查集维护，可以记录连通块个数。eg:积水问题

动态规划

1. 对于一些问题可以尝试通过贪心等方法找出一些确定更优的操作方案，从而优化dp决策，减少转移的状态数。CF1882D P10156
2. 树形dp常见状态是设f[i][...]表示以i为根的子树...。如果某个节点的转移是其所有子节点的并，可以考虑换根。
3. 移项合并下标：如果出现比较复杂且和下标有关的转移式，可以尝试把相同下标的项合并，看看能否用数据结构维护。
4. 遇到类似操作(i,j)的贡献为w[i]+w[j]，考虑根据题目性质能否把i,j独立考虑操作，这样位置x每次操作的代价为w[x]，可以考虑dp。P10715 P10156
5. 遇到表示信息不全的题，考虑先加一维状态，不行再删。
6. 转移一定不能有后效性！！！（修正方案：倒序修改、修改转移的前一个点位置等）P11188 P11232
7. 矩阵快速幂优化：对于线性递推式，且转移系数是常数，考虑构造矩阵加速转移（矩阵乘满足结合律）。转移式系数差多少矩阵就构造多大。P1962 P1939
8. 选若干元素满足 sum<=T，考虑背包。
9. 如果涉及可拼接合法序列的问题，优先考虑类似LIS的dp（S组23T2,24T3）或区间dp（S组21T2），可以用预处理最大合法下标、分类设置状态等方式优化。P9753 P11233 P7914

数据结构

1. Ynoi紫题以下可以做（因为黑题上不封顶）
2. 发现操作次数的上限很少，考虑直接暴力维护，判断当前区间内的数是否都操作完了即可（如开方、取对数、数字位数）
3. 移项合并下标：如果出现比较复杂且和下标有关的转移式，可以尝试把相同下标的项合并，看看能否用数据结构维护。P10381 P11157
4. 离线处理 / 扫描线 P1972
5. 难维护，但个数较少的，适时考虑状态压缩。P1558

线段树

1. 维护区间最大子段和：

转化题意，题目要求一个区间里的最大子段和，且带修改操作
不难想到线段树来维护
但这道题难的不是pushdown，而是如何去pushup，即合并两个子区间的答案

考虑这样一条被分成两段的线段，它的最大子段和rt.maxv如何转移：
  |__________________|
    /            \
|_________| |__________|

首先显然可以从左右两边选一边较大的子段和转移：rt.maxv=max(ls.maxv, rs.maxv)

同时，还可能从两条线段中间扣一块，连起来选：（.的部分）
  |__________________|
    /            \
|_________| |__________|
       ............

我们考虑如何计算，发现#号部分是ls的后缀，@号部分是rs的前缀：
   |__________________|
     /            \
|_________| |__________|
       ###  @@@@@@@

所以我们只要额外维护一个前缀最大值lmax，一个后缀最大值rmax即可

这样我们就得到了合并操作：
rt.maxv = max({ls.maxv, rs.maxv, ls.rmax+rs.lmax});

然后按照题目要求，再维护一个区间和即可
修改是单点修改，不用懒标记，很简单

补充：这道题要是不是单点修改的话没法做，因为不知道怎么去维护

位运算

1. 看到位运算几乎可以直接拆分数位，按位考虑（大部分时候是贪心）。
2. 拆位之后有一些好的性质，例如只有01两种取值之类的，可以简化判定条件（eg:区间和不为0<=>最小值为1）或方案数计算。
3. 考虑把所有位的满足条件联立成线性方程组（例如异或），高斯消元。P3917

组合数学

1. 二项式定理！！！第一考虑逆用，第二看到2^i次方和组合数相乘考虑能否转换。
2. 可以用杨辉三角来推组合数
   • 递推式：C[i][j]=C[i-1][j-1]+C[i-1][j]
   • 杨辉三角每一层上的和为2的幂次：C(n,0)+...+C(n,n)=2^n
   • 第二层是自然数列：C(n,1)=n
   • 第三层是三角数列，依次为自然数之和（1,3,6,10,15,21,...）：C(n,2)=n(n-1)/2=1+2+...+(n-1)
   • （左对齐）左下-右上每条斜线上之和是斐波那契数
3. 分组问题无脑插板法。如果要求每个集合不为空可以考虑初始时往每个集合里都放一个元素，最后再减掉就行。

min/max

1. 考虑根据参数的大小关系分类讨论，可以预处理。CF1407D

贪心

1. 线段最优覆盖问题：
   • 对线段的端点考虑，考虑贪心的选取最靠右的端点，覆盖得一定更多 P11232
2. 线段重叠限制问题：
   • 对数轴上的每个点单独考虑，用优先队列把限制和点存在一块（点应该在限制之前）。（根据题目条件调整）先删靠左的点一定更优（右边可能会浪费限制条件）P11453
3. 对于构造/操作类题目，考虑抽象出不同的操作模型，然后考虑如何决策最优。P10059 P10134 P12505
4. 建立集合S, 使当前剩余最大值一定存在于S中，且使得将最大值排除后，集合性质不变。 先找到最大值，然后删掉最大值，继续找剩下值中的最大值就可以了.（考虑把初始时的大状态都放到堆中，然后每次取出最大的，并将其 “分裂” 成若干个小的放回堆中）P2048 P4370
5. 排序不等式：交换相邻两项不影响其他贡献的 顺序有关、多重限制问题，考虑用排序不等式贪心（推式子，交换两数的代价比较 => 化简不等式）

数学（推导 计数）

1. 遇到乘除法大小比较要转换为加减法，考虑取对数（log or ln），因为log满足大小单调性。P4370 P4926
2. 先隔离，再总计：由若干个互不相干的子问题的方案数乘起来，得到总方案数。P11362 AT_arc180_a
3. 方案数和概率本质等价。遇到某一个不好求的情况可以考虑转化为另一个 AT_agc030_d

模拟

1. 遇到“把序列的最后一个元素移到最前”之类的：考虑循环移位。
2. 记录时间戳。

其他

1. 思考方式：原题面 => 特殊情况 => 启发正解
2. 注意特殊的数据范围，一定有用！（没用喷出题人）
3. 建立一些算法直觉，考虑类似“迭代加深搜索”的方式，尝试思考一下，不行就及时止损换一个。
4. 正难则反。例如满足条件方案数=总方案数-不满足条件方案数。
5. 考虑从限制最严格的情况下手推导，这样求剩下的可能会更容易。P8366 P1350

Ad-hoc

1. “本题极大地考察了和出题人心意相通的能力，它或许不能在茫茫人海中选出水平最高的选手，但一定能选出最适合当出题人 npy 的选手。”
2. 有可能打个暴力上去就A了（复杂度经过分析发现有效操作次数有限）P11244