第 0 章 考场基本功

本章定位：这一章不讲算法，讲的是怎么不把会做的题做丢。CSP-S 2026 的 T2 思路全对却只得 12 分，丢掉的 88 分全部出在本章的内容上（见 plan/诊断报告.md）。本章全部是【必会】，而且比后面任何一章都优先。

0.1 代码骨架 【必会】

一句话：每道题都从同一个骨架开始写，不临场发挥。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;                      // 有符号的 64 位整数。不要用 unsigned

const int N = 200005;                      // 数组大小 = 题面里的最大值 + 5
const ll INF = 0x3f3f3f3f3f3f3f3fLL;       // 64 位的“无穷大”，约 4.5e18

int n;
ll a[N];                                   // 大数组开在 main 外面：自动清零，也不会爆栈

int main() {
    freopen("road.in", "r", stdin);        // 文件名从题面复制，不要手敲
    freopen("road.out", "w", stdout);
    ios::sync_with_stdio(false);           // 这两行让 cin / cout 变快（0.4 节），每个程序都写
    cin.tie(nullptr);
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    ll ans = 0;
    for (int i = 1; i <= n; i++) ans += a[i];
    cout << ans << '\n';                   // 换行用 '\n'，不用 endl
    return 0;
}

易错点

• 提交的目录结构是 准考证号/题目名/题目名.cpp，全部小写。比如题目 crystal 的代码要放在 准考证号/crystal/crystal.cpp。放错位置或文件名错一个字母，这题就是 0 分。
• freopen 调试时被注释掉、交卷时忘了恢复，是最常见的“爆零”原因。本系统的做法是永远不注释它：样例复制成 road.in 再运行（见 0.9）。
• 大数组写在函数里面会爆栈（程序直接崩溃）。超过几万个元素的数组一律写在 main 外面。
• 规则不允许在代码里用 #pragma 改编译选项，不要写。

0.2 整数范围与溢出 【必会】

一句话：int 只能存到约 21 亿，超过就悄悄出错，不会报任何提示。

识别信号：看数据范围表，估一下答案和中间结果最大能到多少。

• “n 个不超过 10^9 的数求和”，n 到 10^5 → 和能到 10^14 → long long。
• “两个不超过 10^9 的数相乘” → 10^18 → long long，而且要在相乘之前就转换。
• 最短路里“边权到 10^9、点数到 10^5” → 距离能到 10^14 → long long。

易错点

• ll x = a * b;（a、b 是 int）是错的：右边先按 int 算完、溢出了，再赋给 x。要写 ll x = 1LL * a * b;。
• 上面这种错，自己编译运行不一定看得出来。有符号整数溢出的结果是“未定义”的，不同编译器表现不同：这台 Mac 自带的编译器在 -O2 下有时恰好按 64 位把乘积算对了（实测过），考场的 g++ 通常按 32 位算，答案就错了。本系统的评测（judge.py）用的是和考场同一代的 g++，这种错在评测里和在考场上表现一样；在 Mac 上用 tools/compile.py 手动编译时（0.8 节），脚本多加了一个选项 -fwrapv，让溢出老老实实截成 32 位，也能暴露出来。但这些都只是兜底：考场上没有评测机，跑样例也未必撞得上溢出。所以不能靠“跑出来是对的”来判断，只能靠习惯——两个 int 相乘之前先写 1LL *。
• 1 << 40 是错的，要写 1LL << 40。
• cout << a * b 也一样会错：溢出发生在相乘的那一刻，和怎么输出没有关系。要写 cout << 1LL * a * b。
• 不要 #define ll unsigned long long。无符号数做减法，3 − 5 得到的是一个 18×10^18 级别的巨大正数，if (a - b < 0) 永远不成立。
• 拿不准的时候：除了循环变量和数组下标，其他整数全部用 long long。代价只是多占一点内存。

练一练：本系统 E01（样例 2 专门暴露溢出）。

0.3 INF 怎么取 【必会】

一句话：INF 必须比所有可能出现的真实答案都大，同时两个 INF 相加不能溢出。

两种都可以用 memset(d, 0x3f, sizeof d) 一次性填满数组（它按字节填 0x3f，所以 int 数组和 long long 数组都对）。

易错点

• 类型和 INF 要配套。 CSP-S 的 T2 里，距离是 64 位的，INF 却用了 0x3f3f3f3f。边权能到 10^9，两段路加起来就超过了 INF，于是真实的最短路被当成了“不可达”。
• 动手前先算一下真实答案的上限。上限接近或超过 10^9，就不能用 int 的 INF。
• 判断“不可达”用 d[v] >= INF / 2，比 d[v] == INF 稳妥（有的写法会让 INF 被加上一点点东西）。
• 三个 INF 相加会溢出。转移式里出现 d[a] + d[b] + d[c] 时，先判断每一项是不是 INF。

练一练：本系统 E04（专门有“INF 取小”就会错的测试点）。

0.4 读写速度（fast IO） 【必会】

一句话：继续用 cin / cout，但每个程序的 main 开头都写上“关同步”的两行，换行用 '\n' 不用 endl。做到这两条，读写速度就不是问题；少了任何一条，读写量大的题会超时。

int main() {
    freopen("road.in", "r", stdin);
    freopen("road.out", "w", stdout);
    ios::sync_with_stdio(false);   // 让 cin / cout 不再和 scanf / printf 保持同步：读入快 3 倍
    cin.tie(nullptr);              // 让 cin 每次读之前不再先把 cout 的内容写出去
    cin >> n >> x;
    cout << ans << '\n';           // 换行用 '\n'。endl 每次都把缓冲区写进文件，非常慢
    return 0;
}

实测（和考场同一代的环境：Linux、g++ 9、-O2）

读 80 万个整数（输入约 8 MB）：

输出 100 万行（每行一个整数）：

• 写了那两行，cin 和 scanf 一样快，不需要改用 scanf。
• 真正危险的是 endl：输出 100 万行就超过 1 秒的时限了，而且关不关同步都一样慢。这个数字和输出文件放在什么盘上有关（换成内存盘实测是 0.27 秒），但怎么都比 '\n' 慢好几倍。
• 这两行写在 freopen 的前面还是后面都可以（两种顺序都实测过）。固定写在 freopen 后面，不容易忘。

关了同步以后有一条规矩：同一个程序里，cin / cout 不能再和 scanf / printf / puts / getchar 混着用。 它们各有各的缓冲区，混用以后读到的数会乱，输出的先后顺序也会乱。调试时临时打印东西用 cerr（0.11 节），不要顺手写一句 printf。

手写快读（常说的 fast IO 模板，也写作 fastio、快读）是另一种读法，读入量到 10^6 个数以上、时限又很紧的时候才用得上。一般的题，上面那两行就够了：

// 快读：用 fread 把输入一大块一大块地读进来，再自己从里面拼出整数。读入量超过 1e6 个数时值得用。
// 注意：用了它，同一个程序里就不能再用 scanf、cin、getchar 读输入了——它们各读各的缓冲区，会把数读乱。
// 本程序：读入 n 和 n 个整数，输出它们的和。
#include <bits/stdc++.h>
using namespace std;

char buf[1 << 16];  // 缓冲区：每次从输入里读进 65536 个字节
size_t buf_len = 0, buf_pos = 0;

int next_char() {  // 取下一个字符；输入读完了就返回 EOF
    if (buf_pos == buf_len) {
        buf_len = fread(buf, 1, sizeof(buf), stdin);
        buf_pos = 0;
        if (buf_len == 0) return EOF;
    }
    return (unsigned char)buf[buf_pos++];
}

long long read() {
    long long x = 0;
    int sign = 1, c = next_char();
    while (c != EOF && c != '-' && (c < '0' || c > '9')) c = next_char();  // 跳过空格和换行
    if (c == '-') {
        sign = -1;
        c = next_char();
    }
    while (c >= '0' && c <= '9') {
        x = x * 10 + (c - '0');
        c = next_char();
    }
    return x * sign;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n = read();
    long long sum = 0;
    for (int i = 1; i <= n; i++) sum += read();
    cout << sum << '\n';
    return 0;
}

易错点

• 忘了写那两行。它不会让答案出错，只会在大数据上变慢，样例测不出来。所以把它写进骨架，每个程序都写。
• 关了同步，又混用了 scanf / printf：样例可能恰好还是对的，换一组数据就乱。
• 用了快读，这个程序里就不能再用 cin 读输入（输出照常用 cout），否则会把数读乱。在终端里手敲输入调试时，敲完要按 Ctrl-D 表示输入结束，程序才会往下走。
• endl 每次都会把缓冲区写进文件，换行一律用 '\n'。
• 在这台 Mac 上直接运行自己编译的程序，cin 比上面的数字慢得多：同样读 80 万个整数要 2.3 秒，关不关同步都一样。苹果自带的编译器和考场的不是一回事。所以本系统的评测（judge.py）默认放在和考场同一代的 Linux 环境里跑，它报的用时才算数；手动运行时觉得读入慢，不用管。

0.5 数组与内存 【必会】

一句话：数组开小了会崩溃或者出现莫名其妙的错，开大了会超内存。

• 大小 = 题面最大值 + 5，下标从 1 开始用。
• 无向图每条边要存两次，边数组开 2 倍；线段树开 4 倍；倍增数组第二维开 20（2^20 > 10^6）。
• 内存估算：10^6 个 int 是 4 MB，10^6 个 long long 是 8 MB。ll f[5005][5005] 是 200 MB，超过多数题的限制。

易错点

• 数组越界通常不报错，而是悄悄改掉了旁边变量的值，表现为“某个变量自己变了”。遇到解释不了的结果，先查数组大小。
• 二维数组的两维别写反：f[N][20] 和 f[20][N] 占的内存一样，但下标用反了就越界。

0.6 多组数据 【必会】

一句话：题面出现“本题有多组数据”，每一组开始前要把上一组留下的东西清干净。

易错点

• 最稳妥的办法：把变量定义在每组数据的循环里面，自然就是新的。
• 用了全局数组、vector、邻接表、计数器，就在每组开头逐个清空。
• 不要每组都 memset 整个大数组。如果有 10^5 组数据、数组有 10^6 个元素，光清空就是 10^11 次操作。只清本组用到的那一段：for (int i = 1; i <= n; i++) a[i] = 0;。
• 提前 break 或 return 跳出读入循环，会把这组没读完的数留给下一组。一定要先把一组数据读完，再判断。

练一练：本系统 E01。

0.7 复杂度估算 【必会】

一句话：1 秒大约能做 10^8 次简单运算。写之前先算一下，避免写完才发现超时。

这张表更重要的用法是反着读：数据范围表里某一档写着 n ≤ 20，出题人就是在告诉你“这一档用子集枚举”；写着 n ≤ 500，就是“这一档 O(n^3) 能过”。部分分怎么拿，表里已经写明了（详见第 9 章）。

0.8 编译 【必会】

考场和评测机用的是：

g++ -std=c++14 -O2 -o road road.cpp

调试时可以多加几个选项，让编译器帮忙找错：

g++ -std=c++14 -O2 -Wall -Wextra -o road road.cpp                 # 提示未初始化的变量、类型不匹配的比较等
g++ -std=c++14 -g -fsanitize=address,undefined -o road road.cpp   # 数组越界、溢出时直接报出是哪一行

在这台 Mac 上，上面的命令会报错 fatal error: 'bits/stdc++.h' file not found：苹果自带的编译器没有这个头文件（考场的 Linux 上有）。在这里手动编译，用本系统的脚本，它补上了这个头文件，编译选项和考场一样（另外多加了 0.2 节说的 -fwrapv）：

# 可执行文件生成在源文件旁边，这里是 work/exec/supply/supply
python3 tools/compile.py work/exec/supply/supply.cpp
python3 tools/compile.py work/exec/supply/supply.cpp --debug   # 调试版，相当于上面带 -fsanitize 的那一条；跑得慢，只用来找错

脚本会把编译器的警告一并显示出来（相当于加了 -Wall）。有警告先看警告：没赋初值就用的变量、函数漏写 return、拿 int 和 v.size() 比大小，编译器都会直接指出是哪一行，比对着错误的答案猜要快得多。考场上想看警告，在命令里自己加 -Wall。

这个脚本编译出来的是 Mac 上的程序，用来查对错、看警告、对拍。用时不要以它为准（0.4 节最后一条），用时看 judge.py 报的。

只是想跑样例的话不用手动编译，python3 judge.py exec supply --samples 会替你编译并比对（0.9 节）。

易错点

• 交卷前一定用第一条命令（官方选项）重新编译一次，确认没有编译错误。编译不过的代码是 0 分。
• 评测用 C++14。auto [a, b] = … 这类 C++17 的写法在自己电脑上可能能编译，到评测机上编译失败。
• 全局变量别和标准库里的东西重名。 用了 #include <bits/stdc++.h> 和 using namespace std; 之后，下面这些名字拿来当全局变量，在和考场同一代的编译器上实测全部编译失败：y1、y0、j1、next、prev、hash、rank、count、time、index、left、right、begin、end、distance、exp、log、clock。哪些名字会出错，各个系统不完全一样——自己电脑上能编译，不代表考场上也能。稳妥的办法是全局变量一律用缩写：nxt、pre、hsh、rnk、cnt、tim、idx、lef、rig、dis。

0.9 用样例自测 【必会】

一句话：考场上没有评测机，样例是唯一的反馈。所有样例都要跑，包括题目文件夹里下发的大样例。

cp road1.in road.in        # 把样例复制成程序要读的文件名
./road                     # 程序读 road.in，写 road.out
diff road.out road1.ans    # 没有任何输出，说明完全一致
time ./road                # 大样例要看用时

在本系统里对应的是：

python3 judge.py exec supply --samples    # 只跑样例
python3 judge.py exec supply              # 全部测试点（相当于考后出成绩）

judge.py 会把代码放进和考场同一代的 Linux 环境里编译、运行（用之前要先打开 OrbStack），所以它报的用时和得分可以当真。

练习时的规矩：先跑样例，样例过了才正式评测，而且每道题只正式评测一次再看题解。评测记录都在 results/history.csv 里，目标是“一次评测的得分”越来越接近“最终得分”。

0.10 对拍 【必会】

一句话：写一个肯定正确的暴力，再写一个随机造数据的小程序，让正解和暴力在几百组随机小数据上比答案。T1、T2 写完后花 10 分钟对拍，能发现绝大多数隐藏的错。

需要三个程序和一个脚本（下面以题目名 road 为例，全部在本机测试过）。三个程序在这台 Mac 上都用 0.8 节的脚本编译，在题目文件夹里运行：python3 ../../../tools/compile.py gen.cpp brute.cpp road.cpp。

1. road.cpp：你的正解，照常 freopen("road.in") 和 freopen("road.out")，不用改任何东西。
2. brute.cpp：暴力，读同一个 road.in，但输出写到 road.ans。
3. gen.cpp：数据生成器，随机种子从命令行传入。

// gen.cpp：同一个种子永远生成同一组数据，出错时能复现
#include <bits/stdc++.h>
using namespace std;

mt19937 rng;

int rnd(int l, int r) {  // [l, r] 里的随机整数
    return (int)(rng() % (unsigned)(r - l + 1)) + l;
}

int main(int argc, char* argv[]) {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    rng.seed(atoi(argv[1]));
    int n = rnd(1, 6);   // 数据要小：n 小、值域小，才容易撞出错，出错后也看得懂
    cout << n << '\n';
    for (int i = 1; i <= n; i++) cout << rnd(-5, 5) << ' ';
    cout << '\n';
    return 0;
}

#!/bin/bash
# check.sh：用 bash check.sh 运行
for i in $(seq 1 500); do
    ./gen $i > road.in
    ./road
    ./brute
    if ! diff -q road.out road.ans > /dev/null; then
        echo "第 $i 组不一致，输入留在 road.in"
        exit 1
    fi
done
echo "500 组全部一致"

易错点

• 对拍数据要小。n ≤ 6、数值在 ±5 以内，比 n = 1000 的随机数据更容易撞出边界情况（相等的值、0、负数、n = 1）。
• 暴力必须用最笨的办法写，不能和正解共用同一个思路，否则两个程序会错得一模一样。
• 对拍通过只说明“小数据上答案对”，不说明不会超时。大数据还要单独造一组最大规模的，用 time 看用时。
• 对拍用的三个文件不要放在要提交的目录里，或者交卷前删掉。

0.11 出错了怎么查 【必会】

调试输出写到标准错误流：cerr << "i=" << i << " ans=" << ans << '\n';。它显示在屏幕上，不会进输出文件，忘了删也不影响得分（但会拖慢速度，交卷前还是要删）。

T3 的死循环就属于第四行：while (uu < n) { uu = ft[uu]; }，当 ft[uu] == uu 时原地不动。写每个 while 时都问一句：循环变量一定会变吗？

0.12 交卷前检查清单 【必会】

最后 15 分钟不写新代码，只做这张表。每道题过一遍：

• 目录名、文件名、两个 freopen 里的文件名，与题面逐字一致，全部小写
• freopen 没有被注释掉；调试输出已删除
• main 开头有关同步的两行；换行用的是 '\n'，没有 endl；没有混用 scanf / printf
• 用官方选项 g++ -std=c++14 -O2 重新编译，无错误；再加上 -Wall 编译一次，把警告逐条看过
• 所有样例（包括大样例）输出一致，大样例用时在时限内
• 答案和中间量会不会超过 int；乘法前有没有 1LL *
• INF 的类型和大小与距离配套
• 数组大小够不够：无向边 2 倍、线段树 4 倍
• 多组数据：每组开头都清空了
• main 最后有 return 0;

本章必会清单

• 不看资料写出 0.1 的骨架，文件读写一次写对
• 看到数据范围，能说出答案的上限、该用 int 还是 long long
• 能说出 int 和 long long 各自的 INF，以及什么时候必须用后者
• 每个程序开头都写关同步的两行，换行用 '\n'；说得出 endl 输出 100 万行大约要多久
• 能对照 0.7 的表，说出数据范围表每一档对应的复杂度
• 独立搭起一次对拍（正解、暴力、生成器、脚本），并用它找出过一个错
• 背下 0.12 的检查清单