常见错误一览

这一部分错误可能是 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 的锅

• \(5\times10^5\) deque/queue 都可能 MLE。目前没有看到 stack MLE 的前例，但鉴于deque/queue都炸了，stack也建议手写。蒟蒻认为这三个手写甚至更方便。

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）

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\) 分！

• 对什么东西进行奇怪的定义扩充的时候，要注意你写的符不符合预期！

\(F_{-n}\) 写错怒调 7h！

• 复杂度是均摊出来的数据结构，不能用于可持久化。容易被卡到复杂度飞起！

• 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\)。

• 倍增的上界要卡好，能少一轮是一轮。

• 空间卡着开可以快一点点，真的就一点点。