常见 Tricks
常见 Tricks
LCat90
·
2023-10-09 23:39:47
·
个人记录
Luogu
是时候总结一下 Trick 了，无论是考前复习还是日常巩固都相当重要。
这个帖子主要记录的是一些 idea，少部分是考试注意事项。
部分语言截取自之前的博客所以可能会有点突兀。
首先上一句真理：
见多识广。所以要多打比赛，多做题，也不要忘了总结。
\text{远古}
判断乘积是否大于一个值的时候，为了防止越界，可以将一个乘数移到另一边改为除法。（NOI 春测遗留技巧）
总结起来，从上界的局限性出发，这也不失为一种优化算法的新方法。
位运算的题 90% 都是拆位算变成 01 序列，10% 是单纯利用性质。
SPFA 的题记得加上 SLF 优化。
基环树的题有两种思路：枚举删除哪条边后转为树；变为环上+子树问题。环上的处理可以考虑单调队列/根据下标算距离/左右端点递推。
图论建模中，k 次的限制可以很容易用拆点解决。
对于值域小的区间问题，考虑枚举值域然后计算在区间中的下标等的贡献。(ABC 308E)
正解打不出来先试试暴力。说不定暴力就是你认为的正解。(LG Div3 3C)
请使用 swap 给 map 赋值，因为直接用等号赋值效率极低。(LG Div3 3C)
对于多限制且数据范围不大的问题，考虑站在流的角度思考&建模。
减少边数/带来不等关系的 \text{Hall} 定理：一个点的连边只要超过 n（n 为左部点的数量量），流就一定可以过 n。(ABC 320G & NKOI 2023)
位运算有性质（单调性）：a\&b\le a,b \ ,a \| b\ge a,b。(CF1878E)
很多传递关系的序列题可以转化成建边 (i,a_i) 然后图上处理。(CF1867D)
运用链式前向星存无向图的边的编号是连续的性质时，cnt 要从 1 开始。
对于无限操作的题目，注意思考是否操作一定次数过后就没必要再操作了。(LG Div3 5C)
\text{Weekly * Round}
换行最好 \n 和 \r 一起判。(R14 T2)
当 n=500 的时候，可能是区间 DP 但很不一定。
使用 DP 前应想清楚状态是否有后效性。
当一个范围内的元素要被反复遍历并且每个点只会遍历一次时，链表是个不错的选择。(R14 T3)
抓住题目中的奇妙设置，比如为什么 k=2 而不是 3 或者更多，可能这就是破题点。(R14 T4)
字符串模拟题注意：空格的数量 & 最后一行的输出。(R1 T1)
“第 k 小的数大于等于 x”可以转换为：最多有 k-1 个数小于 x。(R1 T3)
求区间问题，通常的解决方法就是 数学计数 或 一端点+另一点二分/数据结构。(R1 T3)
如果转移过程中，当前 dp 的值会被改变且重复利用，需要一个另外的数组暂时用来记录转移的答案，转移完后再复制给 dp。这样就解决了有后效性的问题。(R1 T6)
对于只有删除操作的题，常见的转化思路是倒着来，改删除为添加。(R2 T5)
对于坐标系中反弹的问题，可以翻转成一条直线。注意转换。(R3 T5)
状态转移中出现负数时考虑加一个极值使之变为正数。(R3 T3)
二维平面的问题注意是点还是边，下标怎么处理。(R4 T5)
对于只考虑大小关系的题，可以将大于视作 1，等于视作 0，小于视作 -1 后处理这个 3 元序列，比如前缀和。(R4 T5)
区间最大值最小值计数可以使用单调栈。(R5 T3)
对于一个点不能被多个人同时走到的情况，计算总时间可以设计 dp_i=\max\{a_i,dp_{i-1}+1\}，并且 a 从小到大排序。(R5 T5)
多线程工作并且这些线程有交集的时候，直接建边会被重边影响，需要拆点。（说人话，n 个点 m 条道路并且道路之间有重复部分，直接建边的话重边就无法计算了，需要将道路也当成虚点）(R5 T6)
值域太大无法用数组计算时考虑分治。(R6 T2)
A 和 B 在同一点相遇时，不要忘记考虑继续走到终点的方案。(R6 T4)
差分约束中注意对绝对值的判断处理。(R6 T5)
当一段区间的贡献可能重复计算时，考虑调整加入的顺序使之只被算上一次。(R7 T4)
$f(i) = \dfrac{f(i - 1) \times (4 \times i - 2)}{(i + 1)}$。(R8 T3)
平均值大于 k 可以将所有元素减去 k 转变为大于 0 的处理。(R8 T4)
树状数组下标不能为 0！(R8 T4)
区间越大答案越大的 DP 题可以考虑四边形不等式优化一个 n。(R8 T5)
在两种方法复杂度都正确的情况下，选择最不容易出错的那一种。(R9 T2)
通常情况下，DP 比贪心更好打。(R9 T3)
DP 的状态可以同时考虑 i 和 i+1。(R9 T3)
打贪心之前先想想是否应该是 DP。(R9 T4)
记录最大值和次大值判断是否是从子树进行转移是换根的常见套路。(R9 T6)
总结至 R10。
\text{10.6}
我觉得这么差的原因根本上是对难题的畏惧，看到这是提高组的题就想着应该做不出来，但实际上基本是在能力范围内的。所以自信很重要。当然不能过度自信，比如对拍还是需要的。
想了想最稳妥的考试策略应该是：先看完题并对每道题有大致的思考，然后做出最简单的题（不一定是 T1），马上去打其它题的暴力。打完之后看有没有明显可拿的部分分，如果实现难度低就直接拿。做完这一切之后就可以死磕一道题了，可以是 T2、T3，看自己擅长哪一道。不建议开 T4。
根据经验来讲，许多题的正解都是在暴力上进行优化，想到这个优化不就赚麻了。你说是吧，线段树。
\text{10.8}
样例水并且是结论题的时候，一定要打暴力对拍验证自己的代码。
需要计算多个方案（通常非常大）的答案和并且单次答案较小时，可以转变为计算答案为 x 对应多少个方案，最后相加。
\text{10.9}
越是简单的题越不能掉以轻心。检查数组大小，是否需要 long long，以及分类讨论是否完全。(普及模拟赛，差点挂分)
树上问题不一定是树形 DP，可能就是个简单贪心。(T3)
\text{10.12}
对于有限制的图上最短路问题，最好先把限制关系在跑最短路前就处理出来，避免麻烦。([ZJOI2006] 物流运输)
当初始化一个极大值时，注意转移的过程中这个值是否有可能加上另外一个值使越界成一个极小值。([ZJOI2006] 物流运输)
Dijkstra 中对 dis 的更新可以和状态转移基本一致，但是加入队列中就必须满足条件。本质上也是最短路和拓扑排序的结合。([SDOI2010] 大陆争霸)
（不知道算今天还是明天）转移涉及到一个点 i 对后面的 i+a_i 进行更新的 DP 更适合平推法（dp_i\to dp_{i+a_i}）。(CF1881E)
判断一个数是否具有整除和开方之类的性质可以根据值域质因数分解进行计算。(CF1881D)
\text{10.14}
求满足条件的方案数可以转化成总方案数减去不满足条件的方案数。(T1)
和上面差不多：如果正着来很痛苦，那么考虑容斥。(T1)
如果样例没有特殊性质，千万记得自己造一组数据检查输出等是否挂了。(下午 T3 k=1)
\text{10.16}
提供一种算程序空间的方法：
首先在程序开头定义一个 bool 变量 Flag，然后在主函数末尾定义一个 bool 变量 EndFlag。程序结束时输出 (&EndFlag - &Flag) / 1024.0 / 1024.0 即使程序占用空间（单位为 MB）。（注意不要开 O2）就像这样：
#include
using namespace std;
bool Flag;
/*
*/
signed main() {
/*
*/
bool EndFlag;
cout << (&EndFlag - &Flag) / 1024.0 / 1024.0;
return 0;
}
费马小定理求逆元，要求 b 是一个素数；而扩展欧几里得法只要求 \gcd(a, b) = 1（互质）。
10.17
请看清楚部分分设置。
有可能题目仅仅是举了个例子而已，那不是真的。
10.19
如果你在循环时更新了答案，注意你的特判中的 continue/break 语句是否会使更新被跳过。
注意答案是否会超过 long long。（例子：C_n^3，并且 n 是 10^6 级别）
10.20
函数内更新全局变量时，如果函数有递归，那么这个全局变量的值可能会改变，需要用一个临时变量存储。（主席树 update）
\text{CSP}
\text{策略}
如果你想考好提高组，不要参加普及。
一定先把题意读清楚再下手，就算过了样例也不代表题没读错。
该果断的时候果断一点。该放就放，该冲就冲。
一定要认真检查。
\text{Trick}
状态的定义可以是对应的值模一个数的值，使状态数减至模数级别。(J T4)
括号匹配+最大前驱的性质、(S T2)
树上贪心。(S T4)
10.26
当你在调试一个码量较大的抽象算法时，可以检查一下是不是最基本的东西打挂了。
10.28
虚树用于减去树形 DP 中不必要的遍历，核心在于在关键点上 DP。使得可以处理 m 个询问每个询问 k 个点，k\le10^5 的问题。虚树通常是树形 DP 的工具。
维护一个支持动态插入一个数并且找到前驱后继的数据结构，可以用更简便的 set 代替平衡树。并且，为了方便，通常需要提前插入两个无影响的最大值和最小值。
迭代器只能 ++/-- 操作。begin() 函数一般都是末位置加一。set 配有 lower_bound 函数。将迭代器转化为具体的值只需要加上 *。
树上从一个点出发经过所有点回来的最短路径等价于：按 dfn 排序后，第 i 个点走向 i+1 的路径和加上 1 到 n 的路径。
虚树上树形 DP 的过程中，注意只有原来的蓝点会对答案进行贡献，其它点只起继承信息的作用。
一个树的子树节点和树外节点两两连边的总边数为 siz_x\times(n-siz_x)。
即使是序列操作的题目，也可以转化成图论思考。考虑题目中的信息是否会产生一些奇妙的性质（保证关系构成一棵树？），从而转为图论与序列结合。优化时间/空间。(P5391，此处 2 种操作保证树关系，普通背包空间会炸。于是我们开 \log n 个状态，并且按照树链剖分的重链来开)
维护二元组问题的更新，可以类似 Dijkstra 的方式。(P4679)
\text{11.5}
注意答案是否可能为 0。(R15 T4)
哈希的题使用双哈希，比哈希难卡很多。(R15 T4)
觉得贪心复杂或不可做的题直接上 DP。(R15 T2)
\text{11.6}
Nim 游戏讲解。
\text{停课期间}
可行性判断时，可以考虑从结果状态出发进行推导。（ARC105E）
如果图上的点太多，我们可以考虑维护路径；对于多个修改（涉及改区间）并且只要最终的答案时，我们可以暂时留在原处最后统一传递。（P5513）
涉及到区间最大最小算贡献的，可以使用单调栈算出以 i 为 max/min 的左右区间。
棋盘关键点选非关键点问题，如果有重复我们当成连通块处理，并找到这个连通块具有的性质。eg.
树形 DP 的状态定义核心是 x 的状态（并且传到上面去没有影响），定义考虑子树的话就会很麻烦。eg.
注意不要混用 ifac[x] 和 inv(x)。
并查集可以解决序列 i 找最后面的 0/1 问题。
有几层循环不一定代表复杂度是几次（和枚举条件有关），复杂度分析可以考虑逆向分析。（ABC 328G 中，我们定区间 [l,r] 的 len，分析中间都是 0，通过区间位置的方案和得出了复杂度是 O(2^nn) 而不是 O(2^nn^2)）。
长度为 n 的字符串 [1,n] 的循环节长为 l 的充要条件是 [1,n - l]=[l+1,n]。
哈希将模数设成 1e18+3 并使用 __int128 基本不会错（不用双哈希）。
如果 x\le 10^7 并且要枚举 x 的因数时，不用 \sqrt x 枚举。可以做一遍质数筛预处理出分解质因数的过程。达到 O(\log x）.
环上 DP 有后效性时，可以考虑拓扑排序结合贪心进行无后效性的转移。eg.
如果线段树维护一个凹凸性的序列，断点不一定是区间中点。这和最大连续 01 序列不一样。
多个位置选/不选的容斥问题，可以强制要求位置 i 要选（以及前面都不算）。
多次操作只求最后的一个结果，我们可以将操作暂时保留下来，最后统一更新。
如果要用到的变量/状态太大，可以思考这个值的上限（大于哪个值就不影响了）。（eg1.，有直接压位高精的做法，但是我从上往下拓展，利用答案上界是 2D，超过直接停止；eg2.，定义 dp 过后发现第二维的增量 \Delta j 特别大，但是最终答案的 j=0，而 j 每次操作最多 -1，所以这里 \Delta j 的上限就变成了操作次数 k。再给几道：1 2）
平方可以考虑分开处理点对 (i,j) 的贡献 2a_ia_j 和单点的贡献 a_i^2。（eg.）
一道计数题的 O(n^2) 做法很可能是 dp，但也有可能是个 n^2 的式子（化简成 O(n)）。（eg. and solution/dp 做法）
分解质因数/枚举因数的计算可以利用积性函数来优化。分解成 log 个不相关联的问题乘起来即是答案。(eg.)
有时候，两种不同的暴力结合根号分治可能就是正解。(eg.)
有些树上操作不能默认 1 为根，如果允许就开 n 个根的树吧。(eg.)
树形背包第一层倒序枚举，第二层随便，就可以做到 O(n^2)。
前缀和放在转移后面不一定是对的，因为一些特殊条件会对答案造成影响。(eg.)
莫队中 mex 可以这样维护：
void add(int id) {
cnt[a[id]] ++;
while(cnt[mex + 1]) mex++;
}
void del(int id) {
cnt[a[id]] --;
if(!cnt[a[id]] and a[id] >= 0) mex = min(mex, a[id] - 1);
while(!cnt[mex] and mex >= 1) mex --;
}
计算点对之间的权值，转化为对于每条边，分别处理两个点的子树贡献。(eg.)
dp 遇到一堆相同的状态，可以维护它们的个数带来的贡献优化转移。(eg.)
注意对 a_i 相等情况的处理。不要重复计算了。(eg.)
所有区间的 mex 值的 mex 值可以为 x 可以转化为：所有 x 之间的区间的 mex 都不为 x。(
eg.)
\text{别人提供的 Trick}
先放上几篇其它大佬的 Trick。1 2
维护 4 个同类型信息可以分治成 2 个答案组合。(CSP2022S T2)
赛中看到模拟题不要多想，尽早动手最好。
随机赋权 Hash。(CSP2022S T3)
如果实际状态很多但是可行状态很少，可以建立映射关系或者用 map 或 unordered_map。
可以用 vector 作为 map 的哈希函数，100\% 正确。（树哈希）
有根树数量随点数增长得非常快，和阶乘差不多。
如果一个东西有一个伪的单调性，就是大体单调但是在最后的答案区间附近有波动，可以考虑先搞出来这个区间再暴力。
int 数组开到 10^7 占 \text{39MB} 空间，以此类推。
若 ab\ge V,a,b>0，则 \max(a,b)\ge \sqrt V；若 ab\le V,a,b>0，则 \min(a,b)\le \sqrt V。
当你想到一个做法，无法证明复杂度，那么请立即写出来，就算假了，对正解也是有帮助的，而且分也比暴力高，肯定划算。反正就是考场上大致想清楚一些事情之后，一定要行动，不然很容易造成想了很久，可以得到很多分甚至过掉，但是却没时间写完了。
当你定义了原始答案 res 并以此作为最终答案 ans 的初值时，记得要输出 ans，而不是 res。
注意认真比对你的答案和大样例，看上去一样不代表真的一样。（多看几眼不会爆炸）
遇到 \max 和 \min 推式子的时候可以讨论大小关系拆掉。
多测时，如果有你觉得不必要清空的数组没有清空，将它们清空试试。
线段树可以通过底层分块卡空间。
有多个需要取模的地方，最好将式子分开写方便调试和查错。
如果求解某个状态比较难搞，那么我们可以考虑证明这个状态不存在。
注意线段树维护的区间大小。
直接优化转移不方便时，可以优化转移的变化量。（eg.）
结构体里不能定义 const。
当你判断下标是否越界并且数组值是否满足条件的时候，先判下标避免 RE。
树的重心一定在重链上。
考场上写了特判，一定要记得去造这样类型的数据和暴力拍，不然很多时候大样例检查不出来。
遇到莫名其妙的挂分/错误先想想是不是要开 long long。
如果计数题组合容斥没有思路，可以想 dp。（感同身受）