实用小 trick

发表于 更新于

RP++

线段树维护矩阵

如果要维护的元素之间互相有影响，可以考虑用矩阵乘法来转移，不过要注意常数。

根号分治

如果一道题可以想出两种方法，各有优劣，比如一个爆空间，一个爆时间；一个 O(2n)O(2^n) ，一个 O(V2)O(V^2) ，那么不妨考虑根号分治。

记忆化搜索

什么？考场上想不出来 DP? 不妨试试记忆化搜索。凭借 CCF 的数据强度，就算不能拿满也不会挂多少。

组合数

如果直接算阶乘会溢出的话，记得 Ci,j=Ci−1,j+Ci−1,j−1C_{i,j}=C_{i-1,j}+C_{i-1,j-1}

贡献

DP 时可以设一个贡献函数 ww 来快速转移状态，而这个贡献函数可以预处理或者递推快速求出。

背包

如果背包容量很大但物品数 (或能装的物品数) 很小，那么就可以考虑根号分治，把小的部分用朴素的背包转移，剩下的直接暴力枚举选或不选即可。

二分答案

如果要你求一个最小/最大的值满足条件，不一定要用 DP，如果答案是具有单调性的，不要忘记二分答案。

离线

许多问题无法用在线做法想出来时，不妨考虑离线做法。

比如数据结构题，离线下来也许就可以用莫队乱搞过去，DP 离线下来也许可以把时间复杂降一维。