9.21~9.27

分类 dp

当状态分为几类，而且降维时每一类要降的维不一样，我们可以对每一类分别开 dp，用不同的状态设计达到优化目的。

CF2143D2 Inversion Graph Coloring (Hard Version) - 洛谷

构造交换器

在序列转换问题（即给定一些操作，让你把 \(A\) 序列变成 \(B\)）中，我们可以考虑如何构造交换器来解决问题。

AT_arc183_b [ARC183B] Near Assignment - 洛谷

构造：从极值调整

面对一些构造权值（题目有定义）为指定值的序列/树/图的题，可以先考虑权值最大或最小是什么情况，再慢慢调整到指定的权值。

CF2107E Ain and Apple Tree - 洛谷

拆贡献+枚举 last 操作

给你很多操作序列，让你求一个点在进行完每个操作序列后的最终位置和（每个操作序列后算一次答案）。

此时考虑枚举最终位置 \(pos\)，有多少个操作序列能到达 \(pos\)。

我们考虑枚举最后一次能到达 \(pos\) 的操作，然后把前后的操作一填就行。

CF2138D Antiamuny and Slider Movement - 洛谷

带权并查集维护基环树森林（有局限）

再次强调：有局限

把每个基环树的环随便断掉一条边，其他的放进带权并查集。

此时我们仅可以维护环长与加删边（可能需要线段树分治）。

CF2104G Modulo 3 - 洛谷

分段 dp

当最优解有明显的一段一段的时，可以直接从上一个断尾转移到下一个断尾。

CF2107F2 Cycling (Hard Version) - 洛谷

两数之积的欧拉函数

\[\phi(ij) = \frac{\phi(i)\phi(j)\gcd(i, j)}{\phi(\gcd(i, j))} \]

CF809E Surprise me! - 洛谷

杜教筛的另一用途

注：大写字母为前缀和函数，小写字母为原函数。

因为 \(H(n) = \sum_{d = 1}^{n} g(d)F(\lfloor n / d \rfloor)\)

所以当遇到形如右边的东西时就可以考虑此式子，可以直接把 \(O(10^k)\) 降到 \(O(k)\)（高精度开销）。

#6241. 性能优化 I - 题目 - LibreOJ

一个猜结论的方法与证明

当要构造一个序列时，我们可以猜相同的数在一起。

如何证明：如果 \(a_i, = a_j, i < j, \forall k \in (i, j), a_k \neq a_i\)，每个 \(k\) 放到外面都不劣，则结论成立。

按种类顺序操作

如果先一直执行一个操作，然后再一直执行第二个操作可以得到最优解，则这样做。

P13995 【MX-X19-T4】「FeOI Round 4.5」Supernova - 洛谷
AT_arc195_d [ARC195D] Swap and Erase - 洛谷

又一个猜结论的方法与证明

当做一下让你进行操作然后求最小操作数的问题，可以考虑一个操作是否只能进行有限次（一般 \(1\) 次）。

如何证明：如果做更多次一定不更优，则这样做。

P13995 【MX-X19-T4】「FeOI Round 4.5」Supernova - 洛谷
AT_arc195_d [ARC195D] Swap and Erase - 洛谷

树状数组优化数学

当式子中出现 \([f(x) \leqslant k]\)（\(k\) 为给定常数），且要对多个 \(k\) 求答案，此时我们可以对 \(k\) 排序，\(k\) 增加时，做一系列单点修改，查询时就是区间查询，直接用树状数组。

P3312 [SDOI2014] 数表 - 洛谷

\(\sum_{now \in a_i}\) 之类的式子

两种方法：

1. 求出每个数的出现次数 \(c_i\) 然后改为枚举值域，中间乘一个 \(c_i\) 即可。
2. 正常推，遇到一些限制时改为枚举集合，预处理出左右可能被枚举的集合即可。

P3911 最小公倍数之和 - 洛谷

\(\sum\) 与 \(\prod\) 的换位

\[\sum_{x_1 = 1}^{m} \sum_{x_2 = 1}^{m} \dots \sum_{x_n = 1}^{m} \prod_{i = 1}^{n} f(x_i) \\ = \prod_{i = 1}^{n} \sum_{x_i = 1}^{m} f(x_i) \]

P4152 [WC2014] 时空穿梭 - 洛谷