WA/RE/TLE/莫名爆零 的 n 种原因

· · 个人记录

由于老师要总结易错点所以被迫营业

平常没想着这回事。。。

顺序从最低级的错误到不那么低级的错误

  1. 文件名打错...

  2. 没打 freopen

  3. 调试没删

  4. 没仔细看空间限制乱开一堆数组然后 MLE

  5. 某些函数忘加返回值，这个一般情况下开 -Wall 就能查出来

  6. 读入顺序错了(例如有的数据结构题先读 n ,再读序列，再读 m, 而不是 n,m 一起)

  7. 多测不清空，爆零两行泪

  8. 数组没开够(尤其有些题数据范围比较复杂，一定要算好了再开，网络流之类的图论题边数点数和输入数据的级别不一样，无向图要开双倍，spfa 的队列要多开很多倍,SAM 也是两倍数组)

  9. 不开long long...所以一旦涉及到可能爆 int 的部分就要尽可能开 long long

  10. 把两个 long long 没取模直接乘了起来然后爆了

  11. 负数取模之后还是负数,所以应该是(x+mod)%mod,有些东西是隐藏的负数不容易发现，一定要注意，比如容斥系数，mu

  12. 没有考虑 0 之类的特殊情况，然后对拍也很难拍出来

  13. 复杂度假了，没有考虑一些可能引起死循环的地方

  14. 没有注意到负数，很多算法在有负数的时候不能用

  15. 贪心并不正确，这个一般可以拍出来

  16. dp 转移过程中没有考虑特殊情况从而转移出现环/访问负下标/访问越界

  17. dp初始化也要同时初始化前缀和之类的辅助数组

  18. 隐藏的多测: 虚树，网络流，分治...一定要记得清空

  19. 堆默认是大根堆，重载小根堆要把小于重载成大于

  20. 线段树一定不要访问不存在的区间( l>r ) 极有可能导致不断递归然后 RE,有些区间本身是合法的但是因为题目原因经过了 +1 , -1 之类的操作之后变成了不合法的

  21. 网络流不要忘了 num=1 ,不要忘了建反向边

  22. 字符串和 vector 下标从 0 开始

  23. SA 里各种数组要搞清楚

  24. 注意 trie 的空间问题，上限 O(26 \text {总串长})

  25. 线段树修改不要忘记 update

  26. 平衡树 pushdown,update 需要记住，splay 每次访问节点之后要 splay

  27. 用拓扑排序之前一定确定是有向无环图。。。有环可能不能这么做或者需要缩点

  28. 二分边界一定要是合法的，一定要确定二分的东西确实可以二分，wqs 二分之类的东西边界可能是负数，如果不会造成数组越界或者是访问到的东西影响答案一般上下界多开一点防止最终答案正好是上下界

  29. 打表发现规律却没发现规律的适用范围。。。

  30. 注意题面中不同于一般题目的特殊要求

  31. 树上差分之类的东西对于维护点和维护边是略有不同的，一个算LCA一个不算LCA,这个如果样例水甚至有可能查不出来。。。所以还是对拍好

  32. 值域的log与序列长度的log...数据结构题如果没分清楚直接爆炸

  33. 数据结构用的结构体里面要记录很多东西，所以算空间也要算多倍空间,vector之类的空间不要忘掉，只算一遍极可能MLE

  34. 计算几何之类需要大量实数运算的题应该要时刻记住实数判等

  35. 1<<32...或者一个int>>32,这个应该属于UB,不知道开O2之后能不能查出来

  36. 位运算的运算级甚至不如比较符号，不加括号就爆炸了。。。不过这个-Wall能查出来

  37. 对拍写挂浪费很多时间...很多题目中保证不出现的情况如果maker出现了很可能导致暴力和本来正确的正解出现不一样的结果

  38. multiset删数如果直接填删某个数会把所有相等的都删掉，正确写法是s.erase(s.find(x))