常见错误一览

Piggy343288 · 2023-02-08 18:11:41 · 个人记录

摘要：这一部分错误可能是 OI 生涯中陆陆续续的遇到的，当调试以后 CE/WA/TLE/MLE...... 的时候，不妨先看一看这篇 blog。可以在下方留言你想要询问/补充/灌水的内容。对于想要补充的，本人会酌情补充并附上补充者的洛谷昵称。

在这之前，请让我~~无耻的给自己打一波广告~~

Part 1.输出答案

请注意模数写的是否和题目一样，有过模数故意写错的出题人。
请注意输出的是 YESNO 还是 YesNo 还是 YE5N0
请注意 cout 有没有换行

你检查的不仅是 cout 有没有换行，还有题目要没要求换行！蒟蒻因此扔了很多分数！
请注意是否删干净了调试信息……
如果第二行 freopen 是复制了第一行，可能会写成 freopen("xx.out","w",stdin) 的情况。

freopen 每年都会造成大量惨案，望周知。所以你可以使用 fin。
请注意输出边界条件是不是和标答一样（蒟蒻有一次模拟因此痛失 100pts ）。更准确的，Windows 下的 fc 和 Linux 下的 diff 都可以帮你比较文件，如果遇到空格等问题，自己写一个 Python 程序并不费事。
请仔细观察每道题的输入/输出/源程序的名字，千万不要想当然。

NOI 会给建好目录。
无解输出的是 -1 还是别的什么东西？

Part 2.读入

请注意读入顺序。有人因为这个没有拿到 45pts 总司令。
请注意，如果 #define int long long，scanf 必须要 %lld 而非 %d。因此建议不要 #define int long long ——即使你必须要用，也要注意你用的是不是 scanf。本人喜欢 #define int long long + cin/ 快读
注意你开的数组会不会导致越界。如果你只是打暴力分，不要开数据范围同大小的数组，要根据暴力分的范围开数组。
结构体复赋值可以用形如 object = {}，也可以直接形如 cin >> Node.to >> Node.val;。
快读名为快读，但是可以被卡，Ynoi 的一道题中，刻意的卡了快读，原理可能是getchar了很多空格。如果遇到毒瘤出题人，还是直接关 cin 同步流或 scanf 比较好。
链式前向星建树，且不是给定父节点读入的，需要将数组开至二倍（idea：@2018ljw）。
Windows 的换行符是 \r\n，不是 \n.做字符串题要格外注意。
cin 读入大数据奇慢无比。可以关流。

Part 3.STL 的锅

> upd：因为底层使用容器相同，所以都会炸。可以尝试使用list。（upd：@fangzichang）
cmp 要求返回偏序关系。即：cmp(a,a)=0，因为 a<a 不成立。
有过丧心病狂的卡 map 的出题人。但同时，也有丧心病狂卡 umap 的出题人、
当你使用万能头的时候，有可能会因为万能头中的某一个变量而导致CE，且 Linux 和 Windows 在这个事情上略有差异。

e.g.：hash 函数
你需要注意 string 和 char[] 不能总是混用。而且，string 加减易锅。
你是否保证您读取的 vector 的下标在 [0,size) 范围内？如果不能保证，会直接 RE，甚至不会 ub。

Part 4.如果你本地洛谷运行不同

检查代码中的 UB。在 Linux 下，你可以使用编译选项 -fsanitize=undefined 来检查出绝大部分 ub。
检查本地运行的真的和标答一样吗？（检查 Part 1 部分）
若你 CE/RE，考虑 Linux 系统的不同。（一般这样都会 CE 的吧？）
检查你的栈空间，可能本地 RE 洛谷 AC。（idea：@Velvet）
在一个需要 return 的函数没有 return，Windows 不会报错，Linux 会爆“总线错误”。

Part 5.一些小错误点

当你进行数组操作的时候，应该时刻想想你数组下标是从哪里开始的，尤其是 0 转 1 更要注意。
如非必要，尽量写 cmp 而不重载运算符。之前本蒟蒻曾为此（莫名其妙就）保龄了。
如果你是其他语言（比如 Py）转 C++er，请一定要注意 C++ 无负数下标！
函数内的变量会赋随机初值，要手动赋 0 或定义在全局。
op(cnt++) 等价于 op(cnt);cnt++;,而 op(++cnt) 等价于cnt++;op(cnt);
位运算的两边都要加上括号，因为位运算优先级很低（idea：@Irssi）

C++运算级从高到低分别为：
() [] -> .
! ~ ++ -- typename * &（这里不是位与）
+ - * / %
<< >>
< <= > >= != ==
& ^ |
&& ||
?:
= += -= *= /= %= >>= <<= &= ^= |=
,
形如 pair<int,pair<int,int>> 会收获一个 CE，不是因为 pair 不能嵌套，而是因为 >> 型的写法不被允许。正确的写法是 pair<int,pair<int,int> >（upd：在 C++11 以后此问题不再出现 @南门阳德)。
请仔细计算你开的数组的空间，可能存在 ProblemMemoryLimit \le VirtualMemory \le SystemMemoryLimit。
行和列不要写反！
你的代码不应该有任何警告！如果有，你也该清楚他们是什么导致的，会导致什么。其中，比较常见的是 unsigned 和 signed 的比较，虽然一般情况下它运行比较良好，但你也可以把 unsigned 强转 int 来解决这个 warning。常见的 warning 可以在这里查看。（idea：@eggegg185，补充：@Piggy424008）
你的清空/初始化适当吗？具体的，在 CF 使用 memset(arr, val, sizeof arr) 是很危险的行为，因为 CF 可以用 \sum n 组 n=1 的数据把你硬生生卡到 O(n^2)，不仅如此，当你清空不到位的时候，你的程序可能会产生一些意料之外的事情，笔者曾因为这件事调了一个小时的 DP。
注意同名变量。由于 GCC 即使开 -Wextra 也不会爆警告，建议一并开上 -Wshadow，此时同名变量会爆警告。（idea：@Eznibuil）
数组开的太大了（超过内存限制）会报 CE。(idea：@ouxiyao)

Part 6.关于结构体与pair

结构体的值不能设为自身。下面的代码是不正确的：
```
struct Tree{
Tree lson, rson;
};
```
但当然，你可以牺牲部分性能写指针。
结构体可以运算符重载，用法形如 type operator op(type x)。
很多时候并不是必须要使用结构体。对于某些 n 元组，写一个 pair 要比结构体更方便。至于为什么是 n 元组不是二元组，是因为形如 pair<int,pair<int,int> > 的格式是被允许的,（idea：@PDOI）虽然此时不如写一个 tuple.（idea:@南门阳德）
您需要注意的是，形如 this_is_a_pair->first 是不被允许的。相对应的，iter_from_some_stl.first 也不被允许。（idea：@PDOI）
形如 priority_queue 在使用 greater<type> 的时候，必须重载 > 运算符。只重载 < 运算符是不可以的。或者也可以把 < 重载为 >，形如
```
bool operator <(const node&u)const{
return val>u.val;
}
```

Part7.关于数字计算

使用 unsigned long long 可以自然溢出。相对应的，long long 的溢出是 UB。但你不能指望 ull 解决一切问题，在某些特定的问题下，不能使用 ull 而必须边计算边取模。
如果对小数精度要求很高，慎用 double/float 而投入高精小数的怀抱，例如国王饮水记。这是因为存储大部分小数都会造成误差，最经典的 0.1+0.2\not =0.3即属于此类。
当 #define int long long，不仅要注意 scanf 的问题，还要注意数组空间可能“恰好”炸掉。
有些毒瘤数据会卡掉 mid = (l + r) >> 1 的写法，正确的是 mid = l + ((r - l) >> 1);（fix：@Irssi ）
对于有乘除的数字，尽量先除后乘。对于 int * int，本人经常 int ans = 1ll * a * b % p;，这样使得不会溢出，否则即使是 p 为 int 也很可能会溢出。同时，取模不要等到这个式子算完了再取模。例如 ans = a[i] * b[i] * c[i] * d[i] % mod 是很危险的，但你可以 ans=a[i] * b[i] % mod * c[i] % mod * d[i] % mod。
注意你可能需要对负数取模！对负数取模是一件比较奇怪的事情，你要结合题目自行判断“需要什么样子的取模”。
int 的运算比其他的整数类型都快。因此能 int 就 int，别 short 或 longlong(idea: @ISU152_YYDS,upd: @Piggy424008)
理论上 long double 比 double 精度高，但是掉精反而更加严重！

纠正一下”理论上 long double 比 double 精度高“：在 MSVC 的实现上，long double 与 double 一样都是 64 位（大笑），但是鉴于大家都用 GCC，所以也不用纠正。（@Eznibuil）

Part 8.关于骗分

注：暴力不仅可以骗分，有的时候朴素的暴力可以用来对拍。

暴力的正确性也需要检验，虽然一般来说很好弄。（但是，一些麻烦的暴力也很难调试！）
在很多时候，复杂度和边数有关。即使有一个 n\le 1e7 的超大规模数据，如果 m\le 1e7 的话“看上去 O(n^2)”的算法并不是一定不能通过。

为防止歧义，做一点说明：如果这个算法是完全图上 O(n^2) 上的，在稀疏图上复杂度可能显著降低直到 O(n)。
有输出 rand() 的时间，你大可以打一点暴力。
要有信仰。如果只会暴力，那可以把数据范围开满，万一就过了呢？（idea：南门阳德）

Part.9 关于特值判断

请注意你设的特殊初值是 inf 还是 -1 还是 0，而且也要注意你开的 inf 够不够大。
常见的边界主要有 0，1 等.

Part 10.几个比较trivial的trick

数组不要给 10^6 就 int num[1000000]，要 int num[1000000+10] 或者什么的才好，这样就避免了什么 n+1 等下标的麻烦，反正多开了几个.（fix：@2018ljw）

但是有人认为卡着开是极致的优雅。因人而异。
vector 存边的常数大概在5倍左右，和链式前向星的常数差的不多。(idea：@2018ljw)
高精度能写压位高精就写压位高精，现在卡朴素高精的题目越来越多了（idea：@66xyyd ）
写数组大小的时候可以使用形如 const int maxN=1e5+10;int a[maxN]; 的形式来避免数 0 的问题（idea：@MnZn）。

Part 11.RE返回值

3221225477 (0xC0000005): 访问越界，一般是读或写了野指针指向的内存。
3221225725 (0xC00000FD): 堆栈溢出，一般是无穷递归造成的。
3221225620 (0xC0000094): 除0错误，一般发生在整型数据除了0的时候。
Received signal 11: Segmentation fault with invalid memory reference.: 可能是数组越界
Received signal 6:Aborted/IOT trap.: 检查 assert(false) 的情况。
SIGFPE：除0错误，一般发生在整型数据除了0的时候。

Part 12.关于吸氧

吸氧有时会展开数组，造成可执行文件过大。（idea：@fangzichang）
吸氧会让一些不明显的 ub 出现奇奇怪怪的 bug。
吸氧让变量倒着存。

Part 13.部分特定算法需要注意的点

线段树 pushdown 的时候，左右儿子应该怎么写？

在 NOI 2023 联合省选 Day1T1 中，我使用了 sum[rson] += sum[p] * (r - mid + 1)，效果拔群，小图灵狂砍 40 分！
对什么东西进行奇怪的定义扩充的时候，要注意你写的符不符合预期！
复杂度是均摊出来的数据结构，不能用于可持久化。容易被卡到复杂度飞起！
Floyd 的奇怪特性是，你必须先枚举转移点，否则会出问题。与此同时，如果你写了错误的 Floyd，多跑几遍就对了。

笔者记得是两遍，但同机房神仙记得是三遍。

遍历一张图千万别忘了，在遍历一个点的时候遍历过的点别再搜了！

void dfs(int u, int fa) {
vis[u] = 1;
for(int i: edges[u]) {
    if(vis[i]) continue;
    // blablabla...
}
}

背包滚动数组优化时，要倒着枚举花费。
其实有的时候主席树是不需要 build 的。
线段树 2 的 mul 标记要赋初值。
树上背包的复杂度是 O(nm) 的，其中 m 是背包最大大小。但是，需要注意背包的上下界。
采用树 dp 时，可以考虑 dp 数组的状态设计倒着来设计。换言之，可以把子树树根视作子树的一个子节点。

Part 14.卡常小寄巧

更详细的，更有效的卡常方法之前已有日报提过，这里说的是一些好写的卡常优化。

内存访问连续。例如你 dp 数组形如 dp[i][j]，按照 i:1\rightarrow n( j:1\rightarrow n) 的顺序转移，那么 dp[j][i] 的写法会使得常数飞起，而 dp[i][j] 则没有这个问题。因为在后者转移的时候，内存地址只变化了一个元素。

inline 关键字的使用。inline 吸氧负优化几乎已经不可能，如果会引起负优化的话编译器会不执行 inline 操作。而且即使是吸氧的时候，有些函数也不会帮你 inline，因此可以选择把频繁调用的函数手动加上来优化常数。

取模的问题。取模奇慢无比，而对固定数取模则快一些。而更快的可能是下面的两个函数，从根本上解决了取模问题：

inline int& add(int& a, int b) { return a = (a + b >= mod ? a + b - mod : a + b); }
inline int& sub(int& a, int b) { return a = (a > b ? a - b : a + mod - b); }

fread 快读应该是理论上最快（几乎最快）的了？
善用 inline。即使有人指出，inline 在现代 C++ 中是无用的，但实测会更快，而且跑的飞快。
善用三目运算符。三目运算符要求两个可能的值类型要统一，这样会更快一些。依此，可以手写 std::abs, std::min，后者在对一个列表取 \min 时优化明显。小 if 可以使用三目运算符加速。
善用小科技。例如你可以使用 O(n\log n)-O(1) 的 LCA 来减小一个 \log。
倍增的上界要卡好，能少一轮是一轮。
空间卡着开可以快一点点，真的就一点点。