实用小 trick

发表于 2024-12-11 更新于 2025-03-27

RP++

省选 D1T2 正解是操作分块+乱搞 bitset ，无敌了。

类比序列分块，序列分块的实质是控制大部分贡献都可以被快速统计到，剩下小部分直接跑暴力。

那么操作分块也是一样的，把操作进行分块，把每一块的操作的贡献合并起来。

操作分块的主要策略是：对于每一个询问，先处理其所在的块之前所有块的贡献，对于块内直接 $O(B)$ 枚举，最后把算完贡献的询问加到块中。

~~这样说还是太抽象了~~

所以不妨看几道题。

有两种形式的暴力：

对每个询问点，都和在其之前所有的红色点求 LCA 并计算出距离，再取最小值。
对每个被修改为红色点的点，都在树上 BFS 并更新所有点到红色点的最小值。
这两个暴力各有优劣，如何把它们的优劣点综合起来？

最常用的操作就是分块。

考虑对操作序列分块。

如何回答询问？

首先对于在这个询问所属块之前的那些整块而言，每块都把所有的修改丢到队列里多源 BFS 一遍

与这个询问在同一个块内的修改点，直接暴力求 LCA 并更新答案即可。

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

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

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

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

~~这种东西应该只有我会搞忘吧~~

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

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

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

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

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

可以通过两个数的二进制位一定有至少一个不同来枚举每一位，那么必定存在一组，使得每两个不相同的数在不同的组。

你可以给图上某些点加特殊限制然后求最优策略时也许可以考虑分层图。