前言
记录一下有用的trick
统计
- 有上下界， 并且答案和每个数位有关的不一定是数位 dp ， 还可以考虑在某个地方后面的数变自由， 也就是可以随便选， 经常用在二进制中
- 如果是区间维护的问题， 并且这个区间会进行比较复杂的操作， 那么就可以考虑用矩阵来表示操作。
- 分数的操作其实可以考虑矩阵， 见[NOI2021] 密码箱
- 均摊的基础在于势能的变化， 所以做题时观察一些有上限并且每次操作会被改变， 且只减或增加的势能是常数的量， 如Adam and Tree就有量点向上跑的最大颜色数 \(\leq \log{n}\)
- 将 \(b\) 分配给 \(a\) 求最值的问题可以考虑网络流， 网络流可以和最小割相互转化， 并且其实， 最小割一般来说更容易有简单计算的方法， 如 Four Suits
- 二分图匹配问提可以用hall定理减少边数
- 如果要统计任意两点间有通过有约束（这里特指数量约束）条边的最值（长度的最大最小）或数量， 可以考虑矩阵， 如旅游路线
- 位运算的题一定要考虑分成一位一位能不能优化
- 平方数可以表示为质因数分解后每个质数的系数为偶数， 所以乘积为平方数的关系是有传递性的， 即 \(a \times b = x^2, b \times c = y^2 \Rightarrow a \times c = z^2 (a, b, c, x, y, z \in Z)\)
- 如果某一个量他的和是一个约小于 \(1\times10^5\) 的量， 那么可以考虑根号分治
- 对于某些实在只会比较暴力做法的题， 可以多想几个时间复杂度无法通过但时间复杂度表达式不同的做法， 也许可以通过根号分治平衡复杂度。
- 一道题如果是有编号的点建树（或者树形结构）， 那么就要想到prufer序列
- 有些时候贪心策略无法满足需求的原因是贪心策略只是当前类别抉择的最优， 而不是题目限制下的最优（如背包问题， 贪心的抉择得到的结果是当前贪心出来的物体总体积的最优， 而不是 \(m\) 体积限制下的最优）， 那么有时候限制很大的时候， 贪心在大部分情况下最优， 只有最后的小部分无法达到最优， 就可以先考虑贪心缩小范围， 再进行 dp ， 如Topcoder 13859 ClassicProblem
- 如果一个问题是问的进行一种操作， 问在进行某轮（一般较大）操作后的结果， 这种题不是通式就是在某一步后有循环， 如[CCO2021] Through Another Maze Darkly
- 一个问题如果和 \(\gcd()\) 有关， 且可以转化成 \([gcd() = k]\) 的式子， 那么就要想到莫比乌斯反演， 核心式子是 \(\sum\limits_{i | x} \mu(i) = [x == 1]\) ， 一般来说用到的是 \([gcd(x, y) = 1] = \sum\limits_{i | x, y} \mu(i)\)
- 有时候 dp 的状态数很多， 那么不要急着考虑优化状态， 可以想一想能否将一些状态合成一个， 这些状态可能有通式或相同的值， 如CF1894 H Asterism Stream
- 树上点对的最长距离有几种方法， 如树分治（可能是点分也可能是边分）， 建虚树然后对每个点考虑其为 \(lca\) 时的答案， 合并两个点集（总点集的最长链的两端点只可能是两个点集中最长链的两端点四选二得来）等。 有一些恶心的题， 需要这些方法嵌套， 如 [WC2018] 通道Twin Binary Trees