由于前期的学习太过于散乱，笔者决定将所有重要的东西整理一下，放在这篇博客里，也算是一个系统的归纳和复习。

图论

建模

• 遇到支配关系，例如要么选 $x$ 要么选 $y$ 来支配一个东西时，考虑建边 $(x,y)$，那么可以转化为图的定向，将问题转化在基环树上。eg. [ARC083F] Collecting Balls。
• 对于 $a$ 必须在 $b$ 之前的类似钦定，可以考虑将 $a,b$ 建有向边，如果发现是 $\text{Dag}$，那么可以把问题转化为拓扑序计数。eg. [ARC083F] Collecting Balls。

杂项

• $m-n$ 比较小的时候，可以考虑将非搜索树上的点建出虚树来排除冗余状态从而降低复杂度。eg. [ABC419G] Count Simple Paths 2。

动态规划

杂项

• 面对区间限制序列的问题，可以去往 DP 方面思考，如果序列太大，除了离散化区间限制，也可以考虑直接在给定的 $m$ 个区间上进行 DP，而不是在 $n$ 的序列上 DP。eg. [ARC085F] NRE。
• 面对 $01%$ 的贡献问题，考虑用 $1,-1$ 来体现一次操作的贡献。eg. [ARC085F] NRE。

DP 优化方面

• 多维 DP 可能会向多个方向转移，但是我们可以通过一定的规划让这些转移方向具有规律或者单调性，然后根据题目条件，从而来省略一些冗余状态。eg. [ARC204A] Use Udon Coupon。
• 面对很类似偏序限制的转移，或许可以考虑使用 CDQ 优化？eg. [ARC085F] NRE。

树论

杂项

• 面对树同构（甚至是一些点的同构时)，可以考虑使用重心（对于一堆点也就是费马点)，来实现对于同构树的去重（或者是计数)。eg. [POI 2005] PUN-Points，CF724F Uniformly Branched Trees。
• 如果从父亲 $\to$ 儿子比较困难，但是儿子 $\to$ 父亲比较简单，而那些叶子啊深度较深的点之间又有一些联系，可以考虑一个类拓扑状物来方便计算，而不是正常递归。eg. CF1919D 01 Tree。

贪心

• 很经典的，选 $i$ 个到选 $i+1%$ 个的过程，如果不是能直接再选一个最优的就能到达，但是修改的不会特别多，考虑反悔贪心（有些时候有一点背包的感觉)。eg. GYM105789H Horrible Restaurants。

数学

杂项

• 面对大二进制数的运算（例如 $2^{4000}$ 的二进制数的异或) 时，你可以把这个数看作一个模 $2$ 意义下的多项式运算，来方便思考或者运算。(可以发现 $\times 2$ 就是在多项式中 $\times x$。）eg. [ARC084F] XorShift。
• 如果你要看多个多项式互相减法最终能得到哪些东西，其实你可以把 $\text{gcd}(a_1,a_2,...,a_n)$ 当作基底，可以发现所有的能减出来一定是他的倍数。（其实就是看到减法可以往 $\text{gcd}$ 这个方面想就对了。)eg. [ARC084F] XorShift。

计数

• 有很多类似 $n=a+b+c+d+..$ 填入多种颜色的东西，你会发现，如果你确定了除开最后一种颜色的其他颜色，就自动得到了最后一种颜色的填入方案，那么你就可以考虑少一种颜色去刻画问题。eg. 联赛测试 Round 12 装饰。
• 对于矩阵计数子矩阵问题，可以考虑一整行/一整列进行考虑，通过维护相关的辅助与列/行有关的数组，然后转化为在数组上进行求答案。eg. [ABC420F] kirinuki。

其他技巧

• 学会去关注问题的上下界，这个其实有非常多的例子。eg. [ARC156C] Tree and LCS。
• 看到 $2,\frac{1}{2}$ 的上下界，学会去分析每次都要减半/扩增，来保证操作次数在 $\log$ 级别。eg. CF1804F Approximate Diameter。