简介这份资源是《算法竞赛入门经典第二版》例题答案与配套代码合集面向准备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 打开警告-stdc11 对齐书中标准 g -O2 -Wall -stdc11 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 的优化级别避免本地不优化、线上优化后行为不一致把标准输入输出重定向到文件方便反复对比。参数上-stdc11是这本书第二版例题的常见标准如果你用的编译器默认标准更高也建议显式指定防止auto、范围 for 这类特性在不同标准下行为差异。2.3 用对拍脚本验证答案的鲁棒性本地样例过了不代表答案对。很多例题的边界数据在书上没给比如输入为空、数字为 0、字符串长度为 1。常见做法是写一个暴力版本当“标准答案”再写一个随机数据生成器循环对拍。下面是一个通用对拍框架# brute.cpp 是暴力解法sol.cpp 是例题答案 g -O2 -stdc11 brute.cpp -o brute g -O2 -stdc11 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 都常见如果数据本身量级很大比如 1e9eps 要相应放大到 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 必须用%lfprintf输出 double 用%f即可这是 C 语言的历史遗留写错会读到垃圾值。如果题目涉及大量浮点运算尽量把中间结果存成 double不要用 floatfloat 只有 7 位有效数字累加几百次后误差会肉眼可见。4. 例题答案的避坑与排查五条血泪经验4.1 样例过了但 WA先查输入终止条件现象本地样例输出和答案一模一样提交后 WA 在第一个测试点。原因多组数据的终止条件写错。书中例题常见“输入包含多组数据每组第一行是 nn0 时结束”但答案里可能用while (scanf(%d, n) 1 n)如果你抄成while (scanf(%d, n))n0 时还会继续处理导致多输出一组。解决把终止条件单独写一行用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))或者用vectorint arr(n, 0)。参数上memset只能设 0 或 -1设其他值要用fill。5. 从例题答案到独立解题一个可复用的验证习惯5.1 把每道例题的答案当成“待验证假设”我现在的习惯是看完例题答案不直接抄而是先自己写一遍然后和答案对拍。对拍通过后再改三个参数把数据范围扩大 10 倍、把输入顺序打乱、把边界值换成 0 和最大值。如果这三轮都过这道题才算真正吃透。这个习惯看起来慢但比反复提交等结果快得多因为本地对拍一次只要几秒而 OJ 排队可能几分钟。5.2 用表格记录每道题的“参数指纹”下面是我用来记录例题关键参数的表格模板每道题填一行复习时一眼就能看到易错点题号数据范围关键类型边界条件易错点3-1n≤10000intn0 终止多组数据漏读3-2字符串长度≤100char[]空串getline 前未 ignore3-3n≤10intn1恢复现场位置错3-4浮点 1e-8double相等判断eps 取太大这张表不需要写得多漂亮关键是填的时候逼自己想清楚每个参数为什么这么选。填完十道题你会发现翻车的点高度重复基本集中在输入终止、数组越界、恢复现场、精度判断这四类。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如果答案忘了处理l1时l-10的情况就会输出错误。这个文件不提交只用来复习。下次再遇到同类题先跑bad.txt三秒就能判断自己有没有犯老毛病。希望帮到你。本文还有配套的精品资源点击获取