OI免爆零指南

【搬迁于 2026.4.26】【原文发布于 2024-07-11】

OI爆零指南

1. 检查文件输入输出（freopen）

2. 调试输出内容是否已经注释/删除

3. 不开long long见祖宗

4. 空间会不会爆

5. 能用char读入就不要用int读入（更快）

6. 浮点数小心使用，多调试（原因不明，例如多乘了1.0就会RE，上取整/下取整/printf有误差），二分时多留几位

double有误差，例如8.2-3.2=4.99999999，强转int结果为4

注意：floor(i/j)在负数情况和(int)i/j是不一样的，例如：i/j=-1.2，(int)i/j=-1, floor(i/j)=-2,这是因为(int)i/j仅保留整数位

浮点数二分小模版：

double l = 0,r = 2000000000.0,mid;
while(r - l >= 1e-6){mid = (l + r) / 2.0;if(check(mid)){l = mid;}else{r = mid;}
}

浮点数取等判断：

if(fabs(x - y) < 1e-7)

7. 保险起见最好对拍
8. 位运算注意运算符优先级，保险起见加括号

例如：
(k & b[i - 1]) != k 与 k & b[i - 1] != k 是不同的
(1 << m) - 1 与 1 << m - 1是不同的
(ans ^ f[i]) > ans 与 ans ^ f[i] > ans 是不同的

9. 考虑极端情况，例如：初始化第一行数据，若数据只有一行是否需要特殊处理？（eg. [NOI2001] 炮兵阵地，这里的第一行第二行都需要特殊考虑一下）

区间处理问题形如solve(r)-solve(l-1)时，是否需要处理一些特殊的solve值？（尤其是l-1）

10. 某些题目需要排序的别忘了

11. 取模数看清楚，数清楚几个0，防止离谱取模数 （例如1e8）

12. 文件输入输出看清楚文件后缀，常见：.in .out .ans

13. 多组数据记得换行

14. unique使用前记得sort

15. 树状数组的循环范围看清楚，应该循环到n还是最大值,注意下标大小不能 $\le 0$ 否则死循环。真要用到 $0$ 下标记得特判。

16. set的使用：调用时注意边界（begin与end），set内容变化时有些查询要更新（例：[ABC370D] Cross Explosion）

17. 初始化！！！初始化！！！

• 若用char数组读入，输入前char数组可能需要初始化（实测：若读入的字符串长度为 $len$，字符串只会覆盖 $len+1$ 位（即字符串最后一位的下一位也被覆盖为空））
• 多组数据时，尽量使用init函数一次性初始化，无论内容是否会被输入内容覆盖，保险起见全部清0

18. 由于linux和windows系统差异，如果应该有返回值的函数没有返回值，windows不会报错，但linux会

19. 不要把负数开平方根！！

20. 除数与模数都不能是0！

21. 调用vecter，queue，priority_queue,stack等先判是否为空

22. 线段树的空间要开至少4倍

23. 不该取模的地方不要取模！！！不要想当然取模！！！不要想当然取模！！！

• eg.https://www.xmoj.tech/problem.php?cid=8218&pid=5 ，题目里只要求乘积取模没要求求和时取模！！！

24. 考虑爆long long的时候要用高精度，但是注意

• 涉及乘除法的时候综合空间、时间 （高精数的长度） 和题目条件，选择 高精/低精 还是 高精/高精
• 除法的时候是倒着除的
• 每次运算完要调整数字长度的记录，特判0
• 记得初始化

25. 取模时，如果有减法运算记得先+mod再取模

26. 循环从0开始还是1开始？（数位dp，字符串）

27. 数位dp：前导0是否考虑？

int cal(int pos,bool lm,bool ld,int ls,int lss,bool meng){if(pos == 0)return (meng ? 1 : 0);if(!lm && !ld && f[pos][ls][lss][meng] >= 0){//f数组未记录的标记是0还是负数？return f[pos][ls][lss][meng];}int u = (lm ? a[pos] : 9);int ans = 0;for(int i = 0; i <= u; i++){......}if(!lm && !ld)f[pos][ls][lss][meng] = ans;//记得记录答案，否则喜提TLEreturn ans;
}
int solve(int x){.....if(tot == 1)return 0;//特判了吗memset(f,-0x3f3f3f3f,sizeof(f));//数组初始化了吗，初始化是0还是负数return cal(tot,true,true,10,10,false);
}

29. 无解或特殊情况的处理，在数组或变量中标记是0还是-1还是负数？已经处理或有解的情况是正数还是非负数？

if(f[n])
if(f[n] < 0)
if(f[n] == -1)

29. 哈希的使用：（eg：abc403E - Forbidden Prefix）

正确用法：
k = k * b + s[i] - 'a' + 1;
错误用法：
k = k * b + s[i] - 'a';
因为在错误用法中，"ab"和"b"的哈希值都为2，然而两个字符串又不等

30. 并查集如果要在路径压缩的时候更新什么值，务必检查顺序，包括路径压缩是否要先更新父节点再更新子节点，并查集合并的时候是否要避免调用查询根节点的函数（因为若合并时值还没有更新完全就调用，可能会出现错误）(eg.xmoj1830: 叠箱子/HDU Building Block)

31. 有些算法更新值是为了优化减小复杂度，如果在程序中落写更新可能测样例是正确的，但是提交后会出现TLE情况，尽量特别检查下或测一组大数据（目前遇到的：manacher 的已处理最右端点，数位dp，最短路 vis 标记）

32. 用一个数组储存一个数时，注意第一位是最高位还是最低位。

33. 有时候开了long long也不一定不会爆，该用高精度的时候用高精度。求gcd和lcm很容易爆。还有很多时候即使可能爆，如果爆出去的数据没有用也可以用特殊办法处理。（eg.2025.5xmoj月赛 E: 只被一个数整除 m只在x/m的时候对答案有贡献，x的值不超过int，所以当m超过x的值时x/m一定为0，直接特殊标记掉）

34. 你的线段树如果使用懒标记，在下传懒标记给儿子的时候原节点的懒标记清零了没，懒标记是否忘记往下传，懒标记到底是覆盖型的还是要加减乘除之类的。

35. 如果涉及取模，最好读入后立刻将应该取模的数据取模。
    eg.P3384 【模板】重链剖分/树链剖分

36. 1 << i 在i过大时，请使用 1LL << i，否则运算时可能爆int

37. 矩阵乘法没有交换律

38. 做图论题的时候考虑：连通性是否保证（特别是 tarjan）？自环？重边？如果无向，标记边是是否需要同样标记反边？环/负环？回溯时处理还是dfs到的时候就处理？2-SAT点开两倍了吗？树根是否需要特殊考虑（eg.割点）？树/森林？

39. sort排序写cmp/operator重载时不要加等号，正确性不变但是速度明显变慢会T

40. hash在1v1比较时碰撞概率较低，但是如果是丢进map里（如找是否出现过同样的字符串），碰撞概率较高，应该使用双hash

41. 【被删除了】

42. 图论题如果图不保证连通，dfs等搜索时要for枚举连通块

43. 用链式前向星成对存正反边时初始tot=1而不是tot=0，因为2与3一对，4与5一对，以此类推，1号点没用

44. 链式前向星存图时，节点编号不能为0

45. vector常数巨大（对比vector版和链式前向星版），图小可以用vector，图大要卡常的话最好用链式前向星

46. 链式前向星存无向图空间开边数的2倍

47. st表判是否越界

for(int j = 1; j <= 20; j++){for(int i = 1; i <= n; i++){if(i + (1 << (j - 1)) <= 500005){st[i][j] = mgcd(st[i + (1 << (j - 1))][j - 1],st[i][j - 1]);}}}

注意第三行

48. 线段树的懒标记覆盖优先级顺序有时要分类讨论 eg.P2572 [SCOI2010] 序列操作
49. 循环中少定义临时变量，多次需定义的应定义全局变量，否则运行很慢。（eg.500*500的循环中临时定义挪到全局后，2000msTLE -> 338msAC）
50. 处理区间的时候，是否存在 $l > r$ 的非法情况？每个处理都要明晰操作/查询范围！！
51. $1e15+0$ 是 $xey+z$ 格式的大约上限，超过这个数会出现问题，（如 $1e18+31$ 可能变为 $1e18$），原因是 double 精度有限。数过大时应该手打赋值。（如 $1e18+31 \rightarrow 1000000000000000031$）
52. 在luogu可能出现的编译器bug：P5854 【模板】笛卡尔树/警示后人：编译器 Bug，但不用担心，noi系列比赛不会发生
53. noi系列比赛可用__int128，但abs(__int128)/sqrt(__int128) 会 CE，建议手写
54. 应该有返回值的函数要有返回值
55. 不要用for(int i=64;i>=v.size();--i)

• v.size() 是 size_t 类型，无符号整数，当 v.size() 为 $0$ 时若 $i$ 为 $−1$，比较时会变成 $4294967295$ 或 $18446744073709551615$，这个时候是 $>0$ 的，就会死循环。

56. 考场使用编译指令：-std=c++14 -O2 -Wl,--stack=10000000 -Wall

• 分别是：c++14，吸氧，开大栈空间（不要太大避免死机，不要太小避免本地测大样例爆炸），开警告（有效规避一些错误）

57. vector 远古屎山，容易 bug。
58. 不要开百万 stack / queue / deque。

• 一个 deque 80 字节，你想想百万 deque 能浪费多少空间。而且 deque 拓展会浪费更多空间。其实这些stl都可以数组手敲。

59. 不要把set.lower_bound(x) 写成 lower_bound(set.begin(),set.end(),x)。前者 $O(logn)$，后者 $O(nlogn)$。
60. 区分 multiset.erase(x) 和 multiset.erase(multiset.find(x)) 。
    前者删全部（数），后者只删一个（地址）。
61. vector 在 clear 之后不会释放空间，需要 shrink_to_fit 才能够成功释放。(暂未试验)
62. 写分块时建块：

void build(){int now = 1,len = sqrt(n);while(now <= n){tot++;lp[tot] = now;rp[tot] = min(now + len - 1,n);now = rp[tot] + 1;for(int i = lp[tot]; i <= rp[tot]; i++){id[i] = tot,sum[tot] += a[i];}}
}

不要把rp[tot] = min(now + len - 1,n);写成rp[tot] = now + len - 1;，即最后一个块长不一定是len。否则RE。

63. 建圆方树要开 $2$ 倍空间
64. AC 自动机（ACAM）初始 tot = 1
65. 多测特判记得先读完再 return/continue，否则这组数据没读完会误读为下一组的数据
66. 整数除法：正数除以正数是下取整，负数除以正数是上取整。形如计算 $t \le \frac{a}{b}$ ，$t$ 为整数时要考虑正负问题。
67. for(ull i = 63; i >= 0; i--) 这是错的，unsigned 情况下 i = 0 以后再减 1 会变成极大值，陷入死循环。应该在循环最后加 if(!i)break; 判一下。
68. \ , ^ , & 等位运算混在一起时是没有交换律的，但是有结合律。