您的位置: 首页  >  IT文章  >  OI 易犯错误整理

OI 易犯错误整理

分类: IT文章 • 2022-05-17 14:22:06

原帖出自 Nefelibata，不过他不想维护，所以就交给 Stardust 了awa。

前言

Nefelibata：因为笔者弱到无法形容，因此没有办法写出什么有意义的题解，所以本章的主要目的就是为了记录下笔者自己犯过的垃圾错误同时帮助和我一样的初学者（如果能帮到的话），减少因低级错误而浪费时间。（这当中的一部分可能您认为毫无意义，但都是笔者犯过或者调试了很久的）如果有大巨佬无意之中看见了本篇 blog，请留下自己在学习 OI 中的一些错误吧，这真的会对笔者这样的蒟蒻起到很大的借鉴意义。

Stardust：这篇 blog 讲真还挺有用的。每次考前考中回想一下自己整理过的一些错误能避免很多不应该的挂分。另外，这显然属于一篇互动帖，大家在帖上的回复如果看到了会陆续整理哦！祝考试不再无意义挂分！Nefelibata 回归 whk 了……祝好！

由于原帖主墙裂申请，从 2021.4.17 在帖末新开放 XSC062 的流芳百世遗臭万年系列。（雾

可能有些渲染 OJ 上无法实现，可以考虑移步至 link。

0x00 金句

C20230152luojuntong：

  • 如果感觉核心代码没错而且思路很清晰的话，就不要一直查核心代码，注意检查你以为不会错的地方，可能问题就解决了。

XSC062：

  • 不要乱取变量名。难查错。

  • 留 芳 百 世 遗 臭 万 年。

Nefelibata：

  • 真就人丑常数大呗。

  • 当你以为一道题是思维题时，不妨看一下数据范围，它有可能暴力就能过。

0x01 算法类

（包括 STL 之类的啦。

C20212104：

  • 左偏树 (dis_0 = -1) ，但有些题可以不加这句，于是写成习惯了。

Nefelibata：

  • 打树形背包的时候一定要注意各层循环之间的顺序，否则非 WA 即 TLE。

  • 分治，递归，搜索等算法时，边界未考虑清楚。当你的 exe 卡住时，记得检查。顺便给出笔者惯用的二分模板：

    int l, r, ans;
while(l <= r) {
    int mid = (l + r) >> 1;
    if(check(mid)) {
        ans = mid;
        ...
    }
    else
        ...
}
// ... 处根据具体情况填入：r = mid - 1; 或 l = mid + 1;

  • 不要据理臆断的打 RMQ，事实证明它很容易裂开。

  • 二分图单向存边注意方向。

  • 当二分图匹配题目给的点有可能是 (0) 的时候，千万不要把 match 的初值赋为 (0)。

C20230152luojuntong：

如果您的程序在某些测试点卡住了，请检查您 sort 的 cmp 函数有没有问题（一般来说是等号的问题）

Stardust：

  • 关于 DFS，有时 “每次枚举当前解的下一项” 这种思路打不出来的时候，不如试试 “给出数列下一项取或不取”（不然就持续裂开）。

  • 打线段树的时候本来应该调用该节点的左右边界，结果打成待查询的区间边界。当你的 exe 卡住时，记得检查。

ybwlx：

  • dfs序及树链剖分误计算叶子节点的out时间戳。

C202207xiaofang：

  • Floyd 记得去重边。

  • 打线段树，传 (l) 和 (r) 的时候，手残写反了。

  • 线段树记得传 (lazy)。

C20230152luojuntong：

  • 注意这个柿子：(A) && (B)

这个东西是先判断 (A) 再判断 (B) 的，所以，如果有一个条件是防止另一个条件 RE 的（比如 !s.empty() && s.top()=='('）注意让判断是否会 RE 的那个条件放在前面。

Kidulthood:

  • 父亲向儿子转移应放在 dfs 前，儿子向父亲转移应放在 dfs 后。如果您 WA 了不妨检查一下。

C20204518：

  • 二分的之后可以用一个 while 调精度，时间复杂度不会变，这样可以使二分的时候容错率更高，细节更少。

cqbz：

  • 不要没有证明出单调性就凭直觉瞎二分。（关于二分的好多a。 fad

Susct：

  • 后缀自动机二倍数组。

Lihan：

  • 树链剖分向上跳时的条件写成了 dep（深度），应该是 dfn（时间戳）。

  • 淦。 Tarjan 缩点后 scc 的顺序是 拓扑排序的逆序，用好这个可以少好多行代码。不得不说， Tarjan 先 (ye) 生 (ye) 的算法也真是精妙。

  • Tarjan 记得清除标记是否在栈中的标记。

  • vector push_back 后，原来的指针可能会失效

XSC062：

  • 写线段树动态开点，询问却不判当前节点建没建。当你的 exe 卡住时，记得检查。

  • 树链剖分写错了极有可能是线段树的锅哟 awa。

HatakeKakashi：

  • 不更新 size（子树大小），随缘选重儿子，直接 TLE 起飞。

0x02 语法类

Stardust：

  • 等号具有右结合性！

  • int 类型的函数，没有返回值会 RE。

  • 函数首字母要大写，推荐使用双驼峰命名。（ xf：有时候，你定义的函数和库函数重名，此时C++就会调用库函数

Lihan：

  • 输出加 &。当你输出的是一堆奇怪的数字时，记得检查。

  • 输入没加 &。当你的 exe 卡住时，记得检查。

  • 数字默认用 int 存储，如 (1 << 32) 就会爆炸。

Nutmeg：

  • 头文件打少了。打少的通常是 exit(0) 之类的比较少用的函数的头文件。当然也有人用惯了cin，cout，比赛时打 scanf ，结果忘打 #include < cstdio> 。

Fool_Fish：

  • CCF 的评测机是古董，尽量不用 c++ 11，__int128之类的东西。

HatakeKakashi：

  • 随时检查 STL 容器的指针。（空指针永远和 RE 相伴。

cqbz：

  • 用 memcpy 时要把两个数组开成一样大，不然就会像我一样 RE。

Nefelibata：

  • RE 调代码调了半天，结果是模了 (0)。

YBc202211YangJinXi1：

  • 树状数组更新时不能直接覆盖，否则会去掉原来的非当前修改元素的通过 lowbit 更迭到的元素造成的影响。

  • 用 Ctrl+f 替换时如果输出跟某个变量或函数重名要记得改正

C20230152luojuntong：

  • ! 优先级比 % 高。

TIANWEN：

  • vector 要从 (0) 开始遍历。

0x03 数据范围类

Walking_Dead：

  • 做组合数问题因为没有看到组合数可以用阶乘抵消掉而原地爆炸。

  • 底数相同用快速幂不用块速幂，结果机子太慢 6e7 跑不过 1s。

Nefelibata：

  • 定义常量时注意数据类型。

XSC062：

  • 当你需要算组合数并且需要取模并且你不会逆元时，请不要与它死磕，数据范围很小时，杨辉三角是个好东西。link。

  • 求和需要开 long long ( eq) 只有需要求和的地方才需要开 long long。

Stardust：

  • 数据炸 int。当出现不应该出现的负数时，记得检查。
  • 数据炸 long long。当出现不应该出现的负数时，记得检查。另外，long long 记得开全。
  • 各种数据结构的倍数空限忘开。

ybwlx：

  • 链式前向星没有开2倍空限。

C202201yuruilin：

  • 数组开的过大导致 TLE。

Susct：

  • 写题证一下复杂度。 /ee

Fool_Fish：

  • 仔细分析数组要开多大，不要想当然的开大，要不然会 MLE。同时注意 long long 的数据上限与 int 有区别。

kid_magic：

  • 不要乱开 long long 或 int。

0x04 其他

Stardust：

  • 打表打漏了。

  • 内外循环变量混用。

    例如这样的情况：外层循环：

    for(int i = 0; i < mp[u].size(); i++)

    内层循环：

    for(int j = 1; i <= 20; i++)
    fa[v][j] = fa[fa[v][j - 1]][j - 1];

  • 找某个给定天以后的特殊的一天时，不要忘记给定的这一月，这一年。

  • 注意乘法的常数。

C20230154wangweihan：

  • 不要把求最小值看成了求最大值。

  • 代码比较复杂的时候检查一下是不是把条件打漏了。

Nutmeg：

  • 取模取爆了。当出现不应该出现的负数时，记得检查。

x6wangxiye：

  • 写函数没调用。如各种建树（线段树，并查集等），建图（各种图论），初始化的函数。

Lihan：

  • 变量到底是 (dfn) 序还是节点编号一定要记清楚，之后想改的话就要改完。。。。

  • 不确定思路是否正确，是否简洁就开打，结果代码打上 (300^+) 或发现过不了样例回头重构。

  • 看似 3 的幂次比 2 的幂次小了很多，可是 3 的次方远远大于 2 的次方。

  • 宏定义和函数有差别，函数传参如果是式子，则会先计算出式子结果再传入，而宏定义却是直接替代掉了。 （（Time Limit Exceeded的罪魁祸首
    比如：

    #define r(x) (Min (x * Size - 1, n))

    int r (int x) { return Min (x * Size - 1, n); }

    第一份代码的 (f (a + b)) 的返回值为: Min (a + b * Size - 1, n)
    第二份代码的 (f (a + b)) 的返回值为: Min ((a + b) * Size - 1, n)

  • 注意您的下标，负数或零可能会起飞。

Reanap：

  • 有些时候 WA 本质上是因为 RE 了。

Flower_Dream：

  • 不看题（包括题面，题意，输入输出格式）。。。
  • 代码不复制全。

cqbz：

  • 不对拍，过完样例就走人。

Walking_Dead：

  • 把 YES/NO 打成 Yes/No。 （习惯问题。
  • freopen 把 .in 打成 .out （其实是因为考试的时候调试留下的问题。

C20204429

XSC062：

  • 多组数据记得输出换行。

  • 把语句放在 return 后面。

  • while 后面打分号。

  • 如果题目有输入编号之类的东西然后查询，一定要看清楚题目要求的编号要求是 还是 啊QwQ

    不要以为自己可以驾驭 ，最好通过一些处理将其转换为熟悉的 。

  • 把 a[p].sum = -a[p].sum 写成 a[p].sum - a[p].sum 不会警告，辣鸡 g++。

    然而并不能怪 g++。

  • #ifndef ONLINE_JUDGE 调试专用写错了能算嘛。。。

    顺便推荐一下这个好用的防调试忘删代码。

    inline void Debug(void){
    #ifndef ONLINE_JUDGE
    //Your Debug Code
    #endif
    return;
}
int main(){
    //如果未检测到线上评测环境，也就是本地评测
    #ifndef ONLINE_JUDGE
    freopen("Fuck.in","r",stdin);
    #endif
    //...
    Debug();
}

C20230239zhangfuxiang

  • 计数器不赋值 0。

Kidulthood：

  • 清数组不清完，调了几个小时。

ybC202312xiebohao：

  • 考试时，文件开太多，结果交错了。

C2022dongjie：

  • 赋值写反。

C20230152luojuntong：

  • 输入输出本来是二维数组但是数组后面只跟了一个中括号。

Susct：

  • 检查你的快读读不读得了负数。

Nefelibata：

  • 对于 next 是 C++11 中的关键字表示无语。

C20231111jiangjunhong：

  • 两个变量相互影响，一个更改了，另一个就改错了。

C202201ChenJiage：

  • 《论一个漂亮的 init 的重要性》

0x05 遗臭万年

多图警告。不需要查看此系列的请直接跳过。

  • 2021.3.31

在函数传参时，如果要传一个巨大的结构体（比如结构体里套一个 (100 imes 100) 的数组之类的），请加上引用，否则在 C++ 17 (Clang) 或 C++ 11 (Clang) 上会 CE（没错，不是 TLE，是 CE）

OI 易犯错误整理

链式前向星连续改了三次手残打错了三次我也是醉了。在做图论题 Debug 时如果遇到了奇奇怪怪的遍历顺序就可以查链式前向星哦 awa。

  • 2021.4.3

比如你有一道题，它 RE 了。

然后你把数组开大了十倍它还是 RE。

记得检查一下它是不是文件输入输出。

  • 2021.4.11
void Toposort(Something) {
    //Do something...
    for(int i = 0; i < g[x].size(); ++i) { // 标准的邻接表
        int v = to[i];                // 标准的链式前向星
        if(v == fa)
            continue;
        Toposort(v, x);
    }
    return;
}

int main() {
    //Do something...
    read(x), read(y);
    g[x][y] = g[y][x] = 1;              // 标准的邻接矩阵
    Toposort(Something);
    //Do something...
}

然后这个 laoer 就改这个改了一下午。

（主要是各位仔细看，因为分别用邻接表和链式前向星存了两张图，这代码不会 CE，并且过了样例，很神奇地不会 RE）

  • 2021.4.12

如果你有一道题，在某些 OJ 上 AC 了，在另外某些 OJ 上 A 不了。

请注意题目是否需要无限输入 （洛谷的数据也太水了。

  • 2021.4.15

如果需要复制某些图论板子。

检查一下题目要求存边是单向还是双向。

然后你的板子是单向还是双向。

  • 2021.4.17

我，一道题，数组开小了，在不同的大数据（顶满数据范围造的数据）中同时取得了 AC、WA、RE、MLE（?）、TLE 的好成绩。

也就是说，如果你 MLE 了，请检查你是否 RE。（这也太草了吧

OI 易犯错误整理

  • 2021.4.23

请注意因默认构造函数所带来的 MLE。

请注意因构造函数所造成的 MLE 带来的 WA。(?)

  • 2021.4.24

道理我都懂，but 为毛不管多不多组，数据范围大不大，图密不密，开不开 O2，邻接表都比链式前向星快啊！（悲）

欸不对我好像是邻接表党来着？那没事了，用个 p 的链式前向星。

  • Ex-2021.4.24

如果你的全局数组（默认全部为 (0) ）中，还没有赋值的元素突然莫名其妙有了一个奇怪的值。。。

不妨检查一下你的数组是不是开小了 /dk

有时候这个值很特殊，刚好和你程序中某个变量的值相同，那是因为分配给你程序的内存是连续的，然后就刚好从数组越界到那个值去了。。。

  • 2021.5.4

注意区分你的计算范围是数的下标还是数的值域（文明人

  • 2021.5.5

咕了很久的 每日一个遗臭万年小技巧：

inline int Sum(int k) {
    int res = 0;
    for(int i = 0; i; i -= lowbit(i))
        res += Bit[i];
    return res;
}

请注意循环变量的初值。

  • 2021.5.15

树形 DP 时不要只顾着想怎么转移状态而忘了加 dfs(v,u)。

  • 2021.6.1

From trymyedge & Nutmeg.

我可能是唯一一个今天才知道 负数整除 (2) 的时候是向 (0) 取整而非向下取整 的人

所以强烈建议使用 >> 1 而不是 / 2

  • 2021.6.6

我想了半天，为什么我的 T4 暴力分没拿啊，我好像写了来着？难不成写挂了？

赛后 6h 发现自己的文件夹里多出来了一个文件，一看，原来我 T4 的 cpp 名下意识地起成了题目中文名啊，检查代码的时候以为自己没打，所以就少拿了 (20) 分哦。

  • 2021.7.8
0.01 * 3 = 0.029999999...

今天因为这个我 WA 了 (1e9 + 7) 次。

相关推荐