最近感觉学了好多东西，感觉人有点混乱了。今天下午暂时不做题了，写个总结吧。
思维框架
- 主动转化问题：
- 强化限制，给问题加上一些限制来简化问题模型。通俗地来讲就是枚举和分类讨论（P3438，拆 \(\min/\max\)）
- 弱化限制，在不影响答案的前提下减少决策量（ARC107F、CF1473E）
- 忽略限制，删去一些并不影响原问题的条件（P7737）
- 用已有的模型刻画问题（比如建图）
- 在已有问题中观察性质。
- 手玩一些实例，利用直觉将实例转化为抽象的规律。
- 打表（CF573D、P7962）
逃避问题不直接解决原问题，考虑原问题的简化问题或子问题，然后用上面的方法。
特定问题的处理技巧
- 临项交换技术：最优排列问题，要求满足特定权值函数 \(w(p)\) 最优的排列 \(p\)。使用条件：只关注排列整体的最优取值，两项交换的最优性只和这两项有关。（P2123，2022.10.20 多校 T1）
- 概率问题：概率问题的全集一定是 \(1\)，可以考虑不同情况之间的等价关系，把问题限定在求先决条件下的条件概率（ARC108E），或者使用容斥原理构造对象（P3239）
- 直径中心的性质（ARC108F、AGC001C）。
- 计数问题考虑将构造组合对象的过程分步（ARC147D，2022.10.16 联考 T3）
- 容斥计数：容斥在计数问题上的应用经常是通过平凡的方式构造出合法的解，再考虑解的贡献的构成，将其规范为 \(1\)，常见有处理整体贡献的 \(|V|-|E|\) 容斥（2022.10.16 联考 T4，链上情况 P8290），适用于一个合法情况的贡献为一个联通块（链上表现为区间）；处理单体贡献，钦定转恰好（ARC064F）。
- 数据结构的中的容斥：常见的套路是通过差分将 \(=x\) 的限制转化为 \(\leq x\) 的限制（CF1730E）。
- 等价数列的根号分治处理：公差 \(\geq B\) 的数列元素个数最多 \(\dfrac{n}{B}\) 个。（LOJ6681）
- 决策单调性的贡献函数 \(w(l,r)\) 计算：可以用类似莫队的算法，由于和保证两个端点都在当前分治区间移动，所以可以保证每层指针移动次数级别都是 \(\mathcal{O}(n)\) 的，这是二分栈算法没有的优势。（P5574）
- DP 模型：一般来说序列上是最简单的，一些比较复杂的模型可以尝试转化到序列上考虑优化（P5896）
- 一些问题如果没有比较好的性质或者优化思路，可以考虑均摊证明暴力复杂度正确（CF1582F2）。
- 计数问题一般只关注当前填的方案数，要注意 DP 状态都是为这个服务的（CF1152F2）。
- 经典算法在特定模型上的优化：分析经典算法的执行结构，通过执行结构在该问题中的特殊性来优化算法（P4156、band-matrix）