工程工具：Linux、编译、调试与对拍

---

工程工具：Linux、编译、调试与对拍 (Toolchain)

教学目标：

1. 在复赛 Linux 环境下能独立编译、运行、喂样例、计时。
2. 会用 freopen 做文件输入输出（很多复赛题要求读写文件）。
3. 会用 -fsanitize 和 GDB 定位 RE / 越界。
4. 掌握对拍：用随机小数据让正解与暴力对跑，自动抓反例。

前置：会写能编译的 C++ 程序、11.文件操作与异常处理（freopen）。
完整速查见 GDB 命令速查；对拍全套示例见 对拍模板。

---

一、Linux 最小命令集

复赛在 Linux 下进行，先会这几条就能干活：

任务	命令
我在哪 / 列文件	pwd / `ls -l
进目录 / 回上级	cd 文件夹 / cd ..
新建目录	mkdir work

文本编辑器最小操作

比赛环境不一定提供熟悉的 IDE，至少要会用一种终端编辑器完成“打开—修改—保存—退出”。

操作	nano	vim
打开文件	nano main.cpp	vim main.cpp
开始输入	直接输入	按 i 进入插入模式
保存	Ctrl+O，回车	Esc 后输入 :w
退出	Ctrl+X	Esc 后输入 :q
保存并退出	Ctrl+O、回车、Ctrl+X	Esc 后输入 :wq
放弃修改	Ctrl+X 后选否	Esc 后输入 :q!

现场要求

不要求熟练使用大量快捷键，但必须能在没有图形 IDE 时修改一行代码、保存、重新编译。课上分别用 nano 和 vim 完成一次 main.cpp 修改。
| 复制 / 改名 / 删除 | cp a b / mv a b / rm a |

复赛通常在 NOI Linux 下用 GUI 也能操作，但命令行更快，至少要会上面这些。

---

二、编译与运行

g++ main.cpp -o main -std=c++14 -O2 -Wall
./main                       # 直接运行
./main < in.txt > out.txt    # 从 in.txt 读、写到 out.txt

参数	作用
-o main	可执行文件名
-std=c++14	C++ 标准（按比赛要求，常见 c++14）
-O2	竞赛常用优化
-Wall	打开常见警告（能提前发现 bug）

计时：time ./main < in.txt > out.txt，看 real。本机小数据就慢，大数据多半 TLE。

---

三、文件输入输出：freopen

很多复赛题要求从 题名.in 读、写到 题名.out。最省事的写法：在 main 开头加两行 freopen，其余 cin/cout（或 scanf/printf）原样不动。

int main() {
    freopen("milk.in", "r", stdin);    // 之后所有 cin/scanf 都从 milk.in 读
    freopen("milk.out", "w", stdout);  // 之后所有 cout/printf 都写到 milk.out
    // ... 正常的读入、计算、输出 ...
    return 0;
}

⚠️ 复赛最常见的 0 分原因之一就是文件名写错（多空格、大小写、.in/.out 写反）。提交前务必照题面逐字符核对文件名。本地调试时可把这两行注释掉用键盘输入。

---

四、调试：sanitizer 与 GDB

调试编译先去掉 -O2、加 -g；要抓越界 / 未定义行为，加 sanitizer：

g++ main.cpp -o main -std=c++14 -g -Wall -fsanitize=address,undefined

跑一遍，越界 / 空指针 / 整型溢出会直接报出在哪一行，比盯代码快得多。（提交时别带 sanitizer。）

GDB 最常用的一招——程序 RE 后定位崩在哪：

gdb ./main
(gdb) run < in.txt
(gdb) backtrace      # 崩溃后看调用栈，最上面就是出事的那一行

更多断点 / 单步命令见 命令速查。

---

五、对拍：自动抓反例

对拍专治”样例过了、提交却 WA、又不知道错哪”。思想：正解和好写但慢的暴力同时跑大量随机小数据，输出一不同就抓到反例。

最容易记的一句话

造、跑、跑、比：生成一组输入，跑正解，跑暴力，比较输出。

我在检查题解时通常会用 Python 负责“造数据 + 计算参考答案 + 调用 C++ 程序”。例如，P1576 用最大乘积 Floyd 作参考，P1396 用最小瓶颈 Floyd 作参考。比赛现场为了容易重写，推荐下面这套纯 C++ + Bash 版本。

四个文件配一个脚本：

文件	作用
std.cpp	准备提交的正解
brute.cpp	慢但容易写对的暴力（如枚举所有子集）
gen.cpp	随机数据生成器（数据要小，保证暴力能跑完；用固定 seed 便于复现）
check.sh	反复”生成→两边各跑→diff”，不同就停下打印反例

NOI Linux 最小可用版本

第一步：准备三个 C++ 程序

• std.cpp：准备提交的正解。
• bf.cpp：只处理小数据、但尽量明显正确的暴力。
• gen.cpp：按照题目输入格式输出随机小数据。

生成器只需背下面这个外壳。argv[1] 接收本轮编号，把它作为随机种子；同一个编号永远生成同一组数据，发现错误后可以复现。

#include <bits/stdc++.h>
using namespace std;
 
int main(int argc, char *argv[]) {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
 
    if (argc < 2) return 0;
    int seed = atoi(argv[1]);
    srand(seed);
 
    int n = rand() % 8 + 1;  // 小数据，让暴力跑得动
    cout << n << '\n';
    for (int i = 1; i <= n; i++) {
        cout << rand() % 20 + 1 << (i == n ? '\n' : ' ');
    }
    return 0;
}

真正使用时，只修改“输出数据”的部分，使它符合当前题目的输入格式。若题目要求图连通，生成器也必须保证连通；若题目要求没有重复元素，也必须遵守。

第二步：背下这一份 check.sh

g++ std.cpp -o std -std=c++14 -O2
g++ bf.cpp  -o bf  -std=c++14 -O2
g++ gen.cpp -o gen -std=c++14 -O2
 
for i in $(seq 1 1000); do
  ./gen "$i" > in.txt
  ./std < in.txt > std.txt
  ./bf  < in.txt > bf.txt
 
  if ! diff -w std.txt bf.txt >/dev/null; then
    echo "WA on test $i"
    cat in.txt
    echo "std:"
    cat std.txt
    echo "bf:"
    cat bf.txt
    exit 1
  fi
done
 
echo "1000 tests passed"

在终端运行：

bash check.sh

如果第 37 组出错，可以单独复现：

./gen 37 > in.txt
./std < in.txt
./bf < in.txt

现场记忆法

循环中永远只有四句核心命令：
gen > in → std < in > out1 → bf < in > out2 → diff out1 out2。

diff -w 中的 -w 表示忽略空格、制表符等空白宽度差异，减少只因输出排版不同而误报。

暴力怎样才可靠

对拍最重要的不是脚本，而是 bf.cpp。暴力应当与正解思路尽量不同，并且代码越直接越好：正解用 DP，暴力就枚举所有方案；正解用 Dijkstra，小图暴力可以用 Floyd；正解用线段树，暴力就直接修改、扫描数组。

暴力的真正含义

暴力不是某一种固定算法，而是一个虽然慢，但逻辑直接、容易确认正确，能够充当答案裁判的程序。

不同正解通常要配不同的参考程序：

正解类型	小数据暴力 / 参考程序
前缀和、差分、线段树、树状数组	普通数组逐个修改、逐个统计
二分答案	从小到大直接枚举答案
贪心、动态规划	枚举排列、子集，或 DFS 搜索所有方案
Dijkstra 等最短路优化	小图使用 Floyd 或 Bellman-Ford
并查集维护连通性	每次询问重新 BFS / DFS
字符串哈希	substr 或逐字符比较
单调栈、单调队列	双重循环直接寻找答案
最小生成树	极小图枚举边集，检查是否构成生成树

例如：P1576 的大根堆 Dijkstra 可以用最大乘积 Floyd 对拍；P1396 的最小瓶颈 Dijkstra 可以用最小瓶颈 Floyd 对拍；P4568 的分层 Dijkstra 可以在极小状态图上用 Bellman-Ford 或 Floyd 对拍。

选择暴力时检查三个标准：

1. 从题目定义出发：允许慢，但过程应当直接、容易检查。
2. 尽量不同于正解：避免两个程序使用同一思路、犯同一个错误。
3. 只负责小数据：$O(n^4)$、$O(2^n)$ 都可以，只要生成器把规模控制住。

随机数据必须足够小，让暴力快速结束；但要主动覆盖 n=1、最小值、最大值、重复值、链、星形图、不连通图等边界。对拍只能帮助寻找反例，不能代替正确性证明。

文件输入输出

若 std.cpp 中启用了 freopen("题名.in", ...)，./std < in.txt 的重定向不会按预期工作。对拍时先注释 freopen，让正解和暴力统一使用标准输入输出。

完整的 std/brute/gen/check.sh（以 P1048 采药为例）见 对拍模板。

适合对拍：有明显暴力但会 TLE；正解是 DP/贪心/数据结构、细节易错。
不适合：暴力也难写对、答案不唯一（不能直接 diff）、浮点有误差。

最后记住

对拍脚本基本不变，真正随题目变化的是 gen.cpp 和 bf.cpp：生成器负责覆盖合法小数据，暴力负责按题意给出可信答案。

---

小结

• 编译：g++ x.cpp -o x -std=c++14 -O2 -Wall；运行重定向 ./x < in > out；计时 time。
• 文件题用 freopen("x.in","r",stdin) / ("x.out","w",stdout)，文件名逐字符核对。
• 查 RE：-fsanitize=address,undefined 或 GDB 的 run + backtrace。
• 对拍 = 正解 vs 暴力跑随机小数据，diff 抓反例；固定 seed 可复现。

课后动手

• 在本机建一个文件夹，按”四、“流程编译运行 3 道做过的题。
• 照 对拍模板 把 P1048 采药跑通一次对拍，并故意把 0-1 背包内层写成正序，看对拍能否抓到反例。

配套：11.文件操作与异常处理（freopen 细节）、命令速查、对拍模板。