简介：这份资源是《算法竞赛入门经典（第二版）》例题答案与配套代码合集，面向准备ACM/ICPC等算法竞赛的初学者与进阶选手，帮助读者对照书中例题检验思路、补齐实现细节。压缩包共224个文件，以191个cpp源码为主体，另含12个in输入样例、10个ans标准答案及11个md说明文档，整体约208KB，体量轻便，便于按章节检索与本地调试。内容覆盖排序与搜索、动态规划、图论最短路径与最小生成树、KMP与Manacher等字符串算法、数论与组合数学、树与哈希表等数据结构，以及贪心、分治、模拟和快速IO等编码技巧，基本对应书中各章节的练习脉络。目前已有2003人学习下载，适合作为刷题时的参考实现与排错对照，也可用于系统梳理算法知识框架、提升竞赛实战与工程编码能力。

1. 算法竞赛入门经典（第二版）例题答案：为什么你照着题解敲还是过不了

很多人第一次翻开《算法竞赛入门经典（第二版）》时，都会产生一个错觉：例题答案看起来不过如此，代码不长，思路也直白，抄下来跑一遍就完事。可真到 OJ 上提交，结果往往是 WA、TLE、RE 轮着来，甚至本地样例都对，一交就挂。问题不在题解本身，而在于例题答案背后藏着大量“默认你会”的工程细节——输入格式的边界、数据范围对应的类型选择、多组数据的终止条件、浮点误差的处理方式。这些细节题解通常不展开，但恰恰是卡住新手最久的地方。

这篇笔记面向三类人：正在按这本书刷题但总在细节上翻车的初学者；想把这本教材当教学材料、需要一套可复现验证流程的带练者；以及已经能写题但想回头把基础题“一次写对”的进阶者。核心目标只有一个：把例题答案从“看得懂”变成“能复现、能验证、能改参数、能排错”。下面按“先建立验证环境 → 再拆典型题型 → 最后落到避坑和进阶技巧”的顺序展开，每一步都给可抄的命令和参数说明。

2. 把例题答案跑起来：本地验证环境与最小复现流程

2.1 为什么不能只在 OJ 上试答案

OJ 的反馈只有结果，没有中间过程。WA 了不知道是逻辑错还是格式错，TLE 了不知道是算法复杂度问题还是 I/O 太慢。常见做法是在本地建一个最小验证环境：一个源文件、一个输入文件、一个输出文件，再加一条编译运行命令。这样每次改完代码，先过本地样例，再对拍小数据，最后才提交。我一般会把每道例题单独放一个目录，目录名用题号，里面固定放sol.cpp、in.txt、out.txt、run.sh四个文件。这样做的好处是，同一道题改十遍也不会互相污染。

2.2 最小验证目录的搭建命令

# 以例题 3-1 为例，建立独立验证目录 mkdir -p examples/3-1 && cd examples/3-1 # 创建源文件、输入文件、期望输出文件 touch sol.cpp in.txt out.txt # 写一个固定编译运行脚本，避免每次手敲 cat > run.sh << 'EOF' #!/bin/bash # -O2 开启优化，-Wall 打开警告，-std=c++11 对齐书中标准 g++ -O2 -Wall -std=c++11 sol.cpp -o sol if [ $? -ne 0 ]; then echo "compile error" exit 1 fi ./sol < in.txt > out.txt echo "exit code: $?" EOF chmod +x run.sh

这段脚本做了三件事：编译时打开-Wall让隐式类型转换、未使用变量这类问题暴露出来；用-O2模拟 OJ 的优化级别，避免本地不优化、线上优化后行为不一致；把标准输入输出重定向到文件，方便反复对比。参数上，-std=c++11是这本书第二版例题的常见标准，如果你用的编译器默认标准更高，也建议显式指定，防止auto、范围 for 这类特性在不同标准下行为差异。

2.3 用对拍脚本验证答案的鲁棒性

本地样例过了不代表答案对。很多例题的边界数据在书上没给，比如输入为空、数字为 0、字符串长度为 1。常见做法是写一个暴力版本当“标准答案”，再写一个随机数据生成器，循环对拍。下面是一个通用对拍框架：

# brute.cpp 是暴力解法，sol.cpp 是例题答案 g++ -O2 -std=c++11 brute.cpp -o brute g++ -O2 -std=c++11 sol.cpp -o sol for i in $(seq 1 500); do python3 gen.py > in.txt # 生成随机输入 ./brute < in.txt > ans1.txt ./sol < in.txt > ans2.txt if ! diff -q ans1.txt ans2.txt > /dev/null; then echo "difference found at case $i" cat in.txt break fi done

对拍的关键是生成器要覆盖边界：最小值、最大值、重复值、特殊字符。参数上，循环次数 500 到 1000 次通常够用，太多会浪费时间。如果 500 次都没差异，基本可以认为答案在随机数据下是稳的。注意暴力解法本身也要写对，否则对拍会变成“两个错误互相印证”。

2.4 输入输出重定向的常见写法与坑

书中例题大量使用freopen做重定向，这在本地调试很方便，但提交到 OJ 时如果忘记注释掉，就会直接 RE 或 WA。我一般会用一个宏来控制：

#include <cstdio> int main() { #ifdef LOCAL freopen("in.txt", "r", stdin); freopen("out.txt", "w", stdout); #endif // 主逻辑 return 0; }

编译时加-DLOCAL才启用重定向，提交时去掉这个宏即可。参数说明："r"是只读打开，"w"是覆盖写入。如果输入文件不存在，freopen会返回空指针，程序继续跑就会读到错误数据，所以严格来说还应该检查返回值，但竞赛代码里通常省略。

3. 按题型拆例题答案：从循环到递归的四个必调参数

3.1 循环与数组题：下标从 0 还是从 1 开始

这本书的例题答案里，数组下标有的从 0 开始，有的从 1 开始，这不是随意写的。涉及前缀和、差分、树状数组的题，从 1 开始能省掉大量边界判断；纯遍历、排序的题，从 0 开始更符合 C 语言习惯。我一般会先看题目有没有“第 i 个”这种自然语言描述，如果有，就从 1 开始，避免翻译时反复减一。下面是一个典型的前缀和例题写法：

#include <cstdio> const int MAXN = 100005; int a[MAXN], sum[MAXN]; int main() { int n, q; scanf("%d%d", &n, &q); for (int i = 1; i <= n; i++) { scanf("%d", &a[i]); sum[i] = sum[i-1] + a[i]; // 从 1 开始，sum[0] 天然为 0 } while (q--) { int l, r; scanf("%d%d", &l, &r); printf("%d\n", sum[r] - sum[l-1]); } return 0; }

参数说明：MAXN要比题目最大数据范围大 5 到 10，防止越界。sum[0]不赋值就是全局变量的默认 0，这是从 1 开始的核心优势。如果从 0 开始，查询[0, r]时就要特判l-1为 -1 的情况，容易漏。注意scanf的返回值在竞赛里通常不检查，但如果你在本地调试时发现读入异常，可以临时改成if (scanf(...) != 2) return 0;来定位。

3.2 字符串处理题：字符数组与 string 的选型

书中例题答案在字符串题上混用char[]和std::string。选型依据很简单：需要频繁拼接、查找子串、比较，用string；需要按字符下标随机访问且数据量极大，用char[]。但string的cin读入遇到空格会停，这是新手翻车最多的地方。常见做法是：整行读入用getline(cin, s)，但要注意前面如果有cin >> n，会留下换行符，必须先getchar()或cin.ignore()。

#include <iostream> #include <string> using namespace std; int main() { int n; cin >> n; cin.ignore(); // 吃掉换行符，否则 getline 会读到空行 while (n--) { string s; getline(cin, s); int cnt = 0; for (char c : s) { if (c >= '0' && c <= '9') cnt++; } cout << cnt << endl; } return 0; }

参数说明：cin.ignore()默认忽略一个字符，就是换行符。如果输入格式更复杂，可以写cin.ignore(1024, '\n')忽略到行尾。范围 for 里的char c不要写成char& c，除非你要修改原字符串。这个例题的答案如果直接抄，很容易漏掉ignore，导致第一个字符串读成空行，输出少一行。

3.3 递归与回溯题：全局变量和传参的取舍

递归例题的答案里，状态数组通常开成全局变量，这样不用在函数参数里传一长串。但全局变量在回溯时忘记恢复现场，是 WA 的重灾区。我一般会在递归函数开头做选择，递归调用后立刻恢复，形成固定模板：

#include <cstdio> const int MAXN = 20; int n, ans; int vis[MAXN]; void dfs(int step) { if (step > n) { ans++; return; } for (int i = 1; i <= n; i++) { if (!vis[i]) { vis[i] = 1; // 做选择 dfs(step + 1); vis[i] = 0; // 恢复现场，这一步漏了必错 } } } int main() { scanf("%d", &n); dfs(1); printf("%d\n", ans); return 0; }

参数说明：step表示当前填到第几个位置，从 1 开始。vis[i]标记数字 i 是否用过。恢复现场必须紧跟在递归调用之后，不能放到循环外面，否则会多恢复。如果题目数据范围到 15 以上，这个 O(n!) 的写法会超时，需要改成状压或剪枝，但那是进阶内容，先把基础模板写对。

3.4 浮点与精度题：eps 取多少、什么时候用 double

书中浮点例题的答案常用const double eps = 1e-8;，但 eps 不是固定值。判断两个浮点数相等时，eps 取 1e-8 到 1e-6 都常见；如果数据本身量级很大，比如 1e9，eps 要相应放大到 1e-6 甚至 1e-4。我一般会先看题目要求的输出精度，如果要求保留 6 位小数，eps 至少要比 1e-6 小两个数量级，取 1e-8 比较稳。

#include <cstdio> #include <cmath> const double eps = 1e-8; int main() { double a, b; scanf("%lf%lf", &a, &b); if (fabs(a - b) < eps) { printf("equal\n"); } else { printf("not equal\n"); } return 0; }

参数说明：fabs是浮点绝对值，不要用abs，后者对整数才可靠。scanf读 double 必须用%lf，printf输出 double 用%f即可，这是 C 语言的历史遗留，写错会读到垃圾值。如果题目涉及大量浮点运算，尽量把中间结果存成 double，不要用 float，float 只有 7 位有效数字，累加几百次后误差会肉眼可见。

4. 例题答案的避坑与排查：五条血泪经验

4.1 样例过了但 WA：先查输入终止条件

现象：本地样例输出和答案一模一样，提交后 WA 在第一个测试点。原因：多组数据的终止条件写错。书中例题常见“输入包含多组数据，每组第一行是 n，n=0 时结束”，但答案里可能用while (scanf("%d", &n) == 1 && n)，如果你抄成while (scanf("%d", &n))，n=0 时还会继续处理，导致多输出一组。解决：把终止条件单独写一行，用if (n == 0) break;明确退出，不要依赖scanf返回值做复合判断。

4.2 TLE 但复杂度明明对：检查 I/O 和容器

现象：算法复杂度 O(n log n)，n 只有 1e5，却超时。原因：用了cin/cout且没关同步，或者用了vector频繁扩容。解决：在main开头加ios::sync_with_stdio(false); cin.tie(0);，或者直接换scanf/printf。如果是vector，提前reserve(n)。参数上，sync_with_stdio(false)之后不能再混用 C 和 C++ 的 I/O，否则输出顺序会乱。

4.3 RE 在本地不出现：数组开小或递归太深

现象：本地小数据正常，提交后 RE。原因：数组开得刚好等于题目最大 n，但题目实际数据可能多 1 到 2 个；或者递归深度超过默认栈大小。解决：数组统一多开 5 到 10 个元素；递归深度预计超过 1e5 时，改成迭代或手动开大栈。注意 OJ 的栈大小通常只有 1MB 到 8MB，本地可能更大，所以本地不崩不代表线上不崩。

4.4 输出格式错误：多一个空格、少一个换行

现象：答案完全正确，但 PE 或 WA。原因：行末多空格、最后一组数据后多空行、printf里\n写成\\n。解决：用diff对比本地输出和期望输出时，加-Z忽略行末空格，但提交前必须去掉。我一般会在run.sh里加一句sed -i 's/[[:space:]]*$//' out.txt来清理行末空格，但注意这会影响需要保留空格的题目。

4.5 改了参数结果全变：全局变量未初始化

现象：同一份代码，加了一行无关的printf调试，结果就变了。原因：全局变量默认初始化为 0，但局部变量和动态分配的数组不会。如果你把状态数组从全局改成局部，又忘了memset，就会读到随机值。解决：所有需要初始化的数组，无论全局还是局部，统一用memset(arr, 0, sizeof(arr))，或者用vector<int> arr(n, 0)。参数上，memset只能设 0 或 -1，设其他值要用fill。

5. 从例题答案到独立解题：一个可复用的验证习惯

5.1 把每道例题的答案当成“待验证假设”

我现在的习惯是，看完例题答案不直接抄，而是先自己写一遍，然后和答案对拍。对拍通过后，再改三个参数：把数据范围扩大 10 倍、把输入顺序打乱、把边界值换成 0 和最大值。如果这三轮都过，这道题才算真正吃透。这个习惯看起来慢，但比反复提交等结果快得多，因为本地对拍一次只要几秒，而 OJ 排队可能几分钟。

5.2 用表格记录每道题的“参数指纹”

下面是我用来记录例题关键参数的表格模板，每道题填一行，复习时一眼就能看到易错点：

这张表不需要写得多漂亮，关键是填的时候逼自己想清楚每个参数为什么这么选。填完十道题，你会发现翻车的点高度重复，基本集中在输入终止、数组越界、恢复现场、精度判断这四类。

5.3 一个具体技巧：用断言把隐含假设显式化

例题答案里很多假设是隐含的，比如“输入保证 n 是正数”“字符串只含小写字母”。我一般会在代码开头加几行assert，把这些假设写出来：

#include <cassert> int main() { int n; scanf("%d", &n); assert(n > 0 && n <= 10000); // 显式声明数据范围假设 // 后续逻辑 return 0; }

参数说明：assert在NDEBUG宏定义时会被忽略，所以提交前可以加-DNDEBUG关掉，不影响性能。本地调试时保留，一旦输入违反假设，程序会直接报错并指出行号，比 WA 后猜原因快得多。这个技巧我从例题答案里学来后，几乎每道题都会写两三条，尤其是涉及下标和除法的题。

5.4 最后的习惯：每道题留一个“最小反例”

每道例题做完，我会在in.txt旁边再存一个bad.txt，里面放一个能让错误答案翻车的最小输入。比如前缀和题，bad.txt里放1 1和1，查询1 1，如果答案忘了处理l=1时l-1=0的情况，就会输出错误。这个文件不提交，只用来复习。下次再遇到同类题，先跑bad.txt，三秒就能判断自己有没有犯老毛病。希望帮到你。

本文还有配套的精品资源，点击获取