分类 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) - 洛谷
两数之积的欧拉函数
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}\) 之类的式子
两种方法:
- 求出每个数的出现次数 \(c_i\) 然后改为枚举值域,中间乘一个 \(c_i\) 即可。
- 正常推,遇到一些限制时改为枚举集合,预处理出左右可能被枚举的集合即可。
P3911 最小公倍数之和 - 洛谷
\(\sum\) 与 \(\prod\) 的换位
P4152 [WC2014] 时空穿梭 - 洛谷