错题+trick 集
错题 \(+trick\) 集
想写这个很久了，一直都没下决心，但最近挂分太严重了，决心写一下。
错题
统计自 \(2025.11.1\ CSP-S\ 2025\) 开始，直至本人退役。
- 喜欢写
int类型快读快写的小朋友。 - 喜欢不管时空写
#define int long long的小朋友。 - 喜欢不想清楚怎么特判的小朋友。
- 喜欢敲错字母的小朋友。
- 喜欢多次询问清空不彻底，甚至不清空的小朋友。
- 喜欢不计算空间复杂度的小朋友。
- 喜欢检查找环时不注意头尾是否连接的小朋友。
- 喜欢读错题的小朋友。
- 喜欢不认真阅读数据范围（信息学没有互文）。
trick
统计自 \(2025.11.1\ CSP-S\ 2025\) 开始，直至本人退役。
- 将特殊段用特殊字符标出。
- \(Rounding\ Box\)，将平面图上所有点先用矩形括起来，再找性质。
- 用 \(a=k\) 的正方形括点，\((x,y)\to(2nx+i,2ny+i),k\to 2nk+n\)。
- 对于一个三元操作 \((u,v,w)\) ，连接这种边，然后直接大力网络流/二分图/生成树/生成基环树/dp……。
- 假如要优化枚举子集的状压 \(dp\) 时间复杂度，可以考虑单次加一个元素，但是统计最后一个成型集合的一些信息用以去重。
- 可以将组合数转化为多项式。
- 区间染色问题可以考虑倒着做。
- 对于后缀数组，当 \(rk_i>rk_j\) 时，\(s_i\ge s_j\)，取等条件为 \(rk_{i+1}>rk_{j+1}\)（\(s\) 为原字符串）。
- 环上贪心可以转两圈解决。
- 某些情况下，可以把方阵看成邻接矩阵。
- 若要求一张图不能有环和长为 \(k\) 的链，可以考虑分成 \(k\) 层，层内不连层间连。
- 和同近积大。
- 可以通过建立原图（最大/最小）生成树的方式，将某些边的合法性判定以及答案贡献转化成生成树上一条链。
- ——父亲，为什么我不会这道题？
——孩子，怎么了？
——父亲，这道题根本不像人能做的 \(ds\)！
——孩子，你知道莫队是什么吗？
致考场上想不到莫队的 \(white\_tiger\)（不想删除可以回滚）。 - 假如出现需要我们选择的情况，且假如不需要选择，可以用状态较少的 \(dp\) 解决，考虑 \(dp\) 套 \(dp\)。
- 可以考虑做局部状态压缩，保留近几位的信息。
- ——父亲，这个数论好难！
——孩子，这题要设状态。
致考场上做数学题不喜欢想能不能设状态的 \(white\_tiger\)。 - 正难则反是个好东西（更多用于简化问题），容斥是个好东西（更多用于推导公式）。
- \(xy\to\log x+\log y,\frac xy\to\log x-log y\)
- 超级源汇点是个好东西。
- 看到不等式想差分约束。
- 最短路不仅有眼前的 \(dij\)，还有脑后的 \(bfs\)。
- 离线有图，线段树分治。
- 对于 \(\sum_{i=0}^n\sum_{j=0}^n\binom{i+j}{j}\times f(i,j)\) 一类，可以将 \(i+j\le n\) 和 \(i+j>n\) 的情况分类。
- \(\sum i\times c(=i)=\sum c(\ge i)\)
- 交互图论题可以考虑先建出生成树。用处有：找到可能左右部点（二分图）……
- 遇到对于所有 \((x-i,x+i)\) 类点对连边问题，可以考虑反向 ST 表 + 并查集（又名倍增并查集）。
浙公网安备 33010602011771号