简介这份资源是《算法竞赛入门经典第二版》例题答案与配套代码合集面向准备ACM/ICPC等算法竞赛的初学者与进阶选手帮助读者对照书中例题检验思路、补齐实现细节。压缩包共224个文件以191个cpp源码为主体另含12个in输入样例、10个ans标准答案及11个md说明文档整体约208KB体量轻便便于按章节检索与本地调试。内容覆盖排序与搜索、动态规划、图论最短路与最小生成树、KMP与Manacher等字符串算法、数论与组合数学、链表树哈希等数据结构以及贪心、递归分治、快速IO与位运算等编码技巧并配有模拟类题目的实现参考。目前已有2003人学习下载适合希望系统刷题、复盘经典模型并提升问题解决能力的读者使用。1. 从 WA 到 AC 之间差的就是这本例题答案的拆解方式如果你正在刷《算法竞赛入门经典第二版》大概率经历过这种场景书上的例题思路看懂了代码也照着敲了一遍提交上去却 WA 得莫名其妙。不是逻辑错了是边界没兜住、输入格式没对齐、或者数组开小了。这本例题答案的价值不在于“给你抄”而在于它把每一道例题从思路到 AC 代码之间的完整链路摊开了——包括那些书上没写的初始化细节、循环边界和数据类型选择。适合正在系统刷算法题、准备 ACM 校赛或区域赛的在校生也适合已经工作但想补算法基本功的开发者。它解决的核心问题是让你在“看懂思路”和“写出能过的代码”之间少走弯路。2. 例题答案的代码结构从输入解析到输出格式的完整链路2.1 为什么同一道题书上代码能过而你写的不能《算法竞赛入门经典第二版》的例题覆盖了从基础模拟、枚举到动态规划、图论的完整梯度。书上的代码片段通常是“核心逻辑”但一道题从读入到输出中间还有大量工程细节被省略了。例题答案补的就是这些细节。以经典的“开灯问题”为例书上讲的是用数组模拟开关状态但实际提交时你会遇到几个问题数组要不要每次清零编号是从 1 开始还是从 0 开始输出时最后一个数字后面要不要跟空格这些在书上往往一笔带过但答案文件里会给出完整可提交的版本。常见做法是答案文件按章节组织每个例题一个独立文件文件名对应题号或题目关键词。文件内部的结构一般是// 例题 3-2 开灯问题 // 输入n 盏灯k 个人 // 输出最后开着的灯编号空格分隔 #include cstdio #include cstring const int MAXN 1010; int lamp[MAXN]; // 0 表示关1 表示开 int main() { int n, k; memset(lamp, 0, sizeof(lamp)); // 关键多组输入时必须每次清零 while (scanf(%d%d, n, k) 2) { for (int i 1; i k; i) { for (int j 1; j n; j) { if (j % i 0) lamp[j] !lamp[j]; } } int first 1; for (int i 1; i n; i) { if (lamp[i]) { if (!first) printf( ); printf(%d, i); first 0; } } printf(\n); } return 0; }这段代码里几个参数值得注意MAXN开到 1010 是因为题目 n 的上限通常是 1000多开 10 个位置防止越界memset放在while循环外面还是里面取决于题目是否有多组输入——如果有多组必须放在循环内部每次清零first标记用来控制空格输出这是 ACM 格式题最常见的坑之一。2.2 答案文件的组织方式与检索技巧拿到一份例题答案包第一件事不是从头开始看而是先搞清楚它的目录结构。常见的组织方式有两种按章节编号如ch03/、ch04/或按题目类型如dp/、graph/。如果答案包里有 README 或索引文件先扫一遍确认它对应的是第二版的哪些章节。检索时有个技巧用题目关键词而不是题号去搜。因为不同版本的题号可能有微调但题目名称和核心描述是稳定的。比如你想找“蛇形填数”直接搜文件名或文件内容里的“蛇形”比搜“3-3”更靠谱。# 在答案目录下按内容搜索关键词 grep -r 蛇形填数 ./ --include*.cpp -l # 按章节目录列出所有文件 ls -R ./ch03/ # 统计每个章节的例题数量 find ./ch03 -name *.cpp | wc -l这里grep -r的-l参数只输出文件名不输出匹配行内容适合快速定位--include*.cpp限定只搜 C 源文件避免被其他格式干扰。如果你不确定答案包用的是.cpp还是.c把 include 去掉或者改成--include*.c*即可。提示有些答案包会把输入输出样例单独放在.in和.out文件里配合源文件使用。这种结构更适合本地自测建议优先选择带样例文件的版本。3. 核心算法模块的答案拆解从枚举到动态规划的代码模式3.1 枚举与模拟类题目的答案特征枚举和模拟是《算法竞赛入门经典第二版》前几章的重点也是新手最容易“一看就会、一写就废”的题型。答案文件在这类题目上的价值在于它展示了如何把书上的伪代码翻译成实际可运行的循环结构。以“分数化小数”为例书上讲的是模拟除法过程但实际写的时候会遇到循环什么时候终止如何判断是否除尽保留几位小数答案文件里通常会给出一个带注释的完整版本// 例题 2-5 分数化小数 // 输入a, b, c输出 a/b 的 c 位小数 #include cstdio int main() { int a, b, c; while (scanf(%d%d%d, a, b, c) 3 (a || b || c)) { printf(%.*f\n, c, (double)a / b); // 利用 printf 的动态精度 } return 0; }这里的关键参数是%.*f中的*它允许精度由后面的参数c动态指定。很多新手会自己写循环去逐位计算小数结果在四舍五入和边界值上翻车。答案文件直接用了 C 标准库的能力这是更稳妥的做法。另一个常见坑是(a || b || c)这个终止条件——题目通常约定输入0 0 0时结束但如果你写成a ! 0 b ! 0 c ! 0就会漏掉某些合法输入。答案文件里的写法是经过验证的。3.2 动态规划与图论题目的答案阅读方法到了动态规划和图论章节答案文件的读法要变。不能再逐行抄代码而是要先看状态定义和转移方程再看代码实现。以“数字三角形”为例书上给出了递归和递推两种思路。答案文件里通常会同时保留两种版本并标注各自的适用场景// 例题 9-1 数字三角形递推版 // 输入三角形行数 n 及每行数字 // 输出从顶到底的最大路径和 #include cstdio #include algorithm using namespace std; const int MAXN 110; int a[MAXN][MAXN], dp[MAXN][MAXN]; int main() { int n; scanf(%d, n); for (int i 1; i n; i) for (int j 1; j i; j) scanf(%d, a[i][j]); // 从底层向上递推 for (int j 1; j n; j) dp[n][j] a[n][j]; for (int i n - 1; i 1; i--) for (int j 1; j i; j) dp[i][j] a[i][j] max(dp[i1][j], dp[i1][j1]); printf(%d\n, dp[1][1]); return 0; }这段代码的参数含义dp[i][j]表示从位置(i,j)到底部的最大路径和递推方向是从下往上因为底部的dp值就是数字本身max函数来自algorithm在竞赛中可以直接用。答案文件里一般还会附一个递归记忆化的版本方便对比理解。读这类答案时建议先自己写一遍再和答案对照。重点看三个地方状态数组的维度是否和你一致、初始化条件是否遗漏、循环方向是否正确。这三个地方是 DP 题目 WA 的高发区。4. 避坑与排查例题答案使用中的五个血泪教训4.1 现象本地能过提交 WA原因最常见的是输入格式没对齐。书上的例题描述和在线评测系统的实际输入可能有细微差别比如多组输入的终止条件、数字之间是空格还是换行、是否有多余的空行。解决先看答案文件里有没有附带.in和.out样例文件用重定向方式本地测试。如果没有手动构造几组边界输入特别是最小规模和最大规模的情况。# 用样例文件本地测试 ./solution sample.in my.out diff my.out sample.out4.2 现象数组越界导致 RE 或结果玄学原因书上的代码为了简洁有时会把数组开到刚好够用。但实际题目中下标可能从 1 开始或者需要多开几个位置做哨兵。解决在答案文件的基础上把数组大小统一放大 10 到 20 个元素。比如题目说 n ≤ 1000就开到 1010 或 1020。这个习惯在竞赛中能省下大量调试时间。4.3 现象多组输入时结果累加错误原因全局数组或变量没有在每组输入前重置。这是新手最常踩的坑之一而且因为本地测试往往只跑一组数据很难发现。解决养成习惯——只要题目提到“多组输入”或“输入包含多组数据”就把memset或手动初始化放在循环内部的第一行。4.4 现象浮点数输出精度不对原因用了float而不是double或者printf的格式控制符写错。竞赛题目对浮点数的精度要求通常是“保留 c 位小数”但四舍五入的行为可能因编译器而异。解决统一用double输出时用%.*f动态指定精度。如果题目要求“四舍五入”注意 C 的printf默认就是四舍五入但浮点误差可能导致边界情况出错必要时加一个极小值1e-9。4.5 现象答案文件里的代码编译不过原因答案包可能是在不同编译器或不同标准下写的。比如用了 C11 的特性但你的编译环境默认是 C98或者用了某些平台特有的头文件。解决先确认编译命令。常见做法是加上-stdc11或更高标准g -stdc11 -o solution solution.cpp如果还是报错看错误信息里缺失的头文件或函数对照答案文件的注释说明确认它依赖的库或环境。5. 把例题答案变成自己的东西一个验证驱动的刷题习惯答案文件最大的风险是“看懂了”的错觉。我的做法是每看完一道例题的答案关掉文件自己从头写一遍然后做三件事。第一用题目描述里的样例数据跑一遍确认输出一致。第二构造一组边界数据——比如 n1、nmax、全相同、全不同——再跑一遍。第三如果时间允许把代码里的关键参数改一改观察结果变化确认自己理解每个变量的作用。// 自测模板在答案代码基础上加边界测试 // 以“开灯问题”为例测试 n1, k1 和 n1000, k1000 // 运行方式编译后手动输入或重定向这个习惯看起来慢但能帮你把答案里的“死代码”变成自己的“活知识”。从那以后我每次刷题都强制走一遍“样例→边界→改参数”的流程WA 率明显下降。另外建议把答案文件按自己的理解重新组织一遍。比如按算法类型建目录把同一类题目的答案放在一起旁边用注释写上“这题的关键是状态定义”或“这题的坑在输入终止条件”。这样积累下来考前复习时翻自己的注释比翻答案本身更有效。希望帮到你。本文还有配套的精品资源点击获取 
长河君 · 2026/10/17 12:55:21 · 阅读 1.2k 算法竞赛入门经典例题答案拆解：从WA到AC的完整链路与避坑指南
简介这份资源是《算法竞赛入门经典第二版》例题答案与配套代码合集面向准备ACM/ICPC等算法竞赛的初学者与进阶选手帮助读者对照书中例题检验思路、补齐实现细节。压缩包共224个文件以191个cpp源码为主体另含12个in输入样例、10个ans标准答案及11个md说明文档整体约208KB体量轻便便于按章节检索与本地调试。内容覆盖排序与搜索、动态规划、图论最短路与最小生成树、KMP与Manacher等字符串算法、数论与组合数学、链表树哈希等数据结构以及贪心、递归分治、快速IO与位运算等编码技巧并配有模拟类题目的实现参考。目前已有2003人学习下载适合希望系统刷题、复盘经典模型并提升问题解决能力的读者使用。1. 从 WA 到 AC 之间差的就是这本例题答案的拆解方式如果你正在刷《算法竞赛入门经典第二版》大概率经历过这种场景书上的例题思路看懂了代码也照着敲了一遍提交上去却 WA 得莫名其妙。不是逻辑错了是边界没兜住、输入格式没对齐、或者数组开小了。这本例题答案的价值不在于“给你抄”而在于它把每一道例题从思路到 AC 代码之间的完整链路摊开了——包括那些书上没写的初始化细节、循环边界和数据类型选择。适合正在系统刷算法题、准备 ACM 校赛或区域赛的在校生也适合已经工作但想补算法基本功的开发者。它解决的核心问题是让你在“看懂思路”和“写出能过的代码”之间少走弯路。2. 例题答案的代码结构从输入解析到输出格式的完整链路2.1 为什么同一道题书上代码能过而你写的不能《算法竞赛入门经典第二版》的例题覆盖了从基础模拟、枚举到动态规划、图论的完整梯度。书上的代码片段通常是“核心逻辑”但一道题从读入到输出中间还有大量工程细节被省略了。例题答案补的就是这些细节。以经典的“开灯问题”为例书上讲的是用数组模拟开关状态但实际提交时你会遇到几个问题数组要不要每次清零编号是从 1 开始还是从 0 开始输出时最后一个数字后面要不要跟空格这些在书上往往一笔带过但答案文件里会给出完整可提交的版本。常见做法是答案文件按章节组织每个例题一个独立文件文件名对应题号或题目关键词。文件内部的结构一般是// 例题 3-2 开灯问题 // 输入n 盏灯k 个人 // 输出最后开着的灯编号空格分隔 #include cstdio #include cstring const int MAXN 1010; int lamp[MAXN]; // 0 表示关1 表示开 int main() { int n, k; memset(lamp, 0, sizeof(lamp)); // 关键多组输入时必须每次清零 while (scanf(%d%d, n, k) 2) { for (int i 1; i k; i) { for (int j 1; j n; j) { if (j % i 0) lamp[j] !lamp[j]; } } int first 1; for (int i 1; i n; i) { if (lamp[i]) { if (!first) printf( ); printf(%d, i); first 0; } } printf(\n); } return 0; }这段代码里几个参数值得注意MAXN开到 1010 是因为题目 n 的上限通常是 1000多开 10 个位置防止越界memset放在while循环外面还是里面取决于题目是否有多组输入——如果有多组必须放在循环内部每次清零first标记用来控制空格输出这是 ACM 格式题最常见的坑之一。2.2 答案文件的组织方式与检索技巧拿到一份例题答案包第一件事不是从头开始看而是先搞清楚它的目录结构。常见的组织方式有两种按章节编号如ch03/、ch04/或按题目类型如dp/、graph/。如果答案包里有 README 或索引文件先扫一遍确认它对应的是第二版的哪些章节。检索时有个技巧用题目关键词而不是题号去搜。因为不同版本的题号可能有微调但题目名称和核心描述是稳定的。比如你想找“蛇形填数”直接搜文件名或文件内容里的“蛇形”比搜“3-3”更靠谱。# 在答案目录下按内容搜索关键词 grep -r 蛇形填数 ./ --include*.cpp -l # 按章节目录列出所有文件 ls -R ./ch03/ # 统计每个章节的例题数量 find ./ch03 -name *.cpp | wc -l这里grep -r的-l参数只输出文件名不输出匹配行内容适合快速定位--include*.cpp限定只搜 C 源文件避免被其他格式干扰。如果你不确定答案包用的是.cpp还是.c把 include 去掉或者改成--include*.c*即可。提示有些答案包会把输入输出样例单独放在.in和.out文件里配合源文件使用。这种结构更适合本地自测建议优先选择带样例文件的版本。3. 核心算法模块的答案拆解从枚举到动态规划的代码模式3.1 枚举与模拟类题目的答案特征枚举和模拟是《算法竞赛入门经典第二版》前几章的重点也是新手最容易“一看就会、一写就废”的题型。答案文件在这类题目上的价值在于它展示了如何把书上的伪代码翻译成实际可运行的循环结构。以“分数化小数”为例书上讲的是模拟除法过程但实际写的时候会遇到循环什么时候终止如何判断是否除尽保留几位小数答案文件里通常会给出一个带注释的完整版本// 例题 2-5 分数化小数 // 输入a, b, c输出 a/b 的 c 位小数 #include cstdio int main() { int a, b, c; while (scanf(%d%d%d, a, b, c) 3 (a || b || c)) { printf(%.*f\n, c, (double)a / b); // 利用 printf 的动态精度 } return 0; }这里的关键参数是%.*f中的*它允许精度由后面的参数c动态指定。很多新手会自己写循环去逐位计算小数结果在四舍五入和边界值上翻车。答案文件直接用了 C 标准库的能力这是更稳妥的做法。另一个常见坑是(a || b || c)这个终止条件——题目通常约定输入0 0 0时结束但如果你写成a ! 0 b ! 0 c ! 0就会漏掉某些合法输入。答案文件里的写法是经过验证的。3.2 动态规划与图论题目的答案阅读方法到了动态规划和图论章节答案文件的读法要变。不能再逐行抄代码而是要先看状态定义和转移方程再看代码实现。以“数字三角形”为例书上给出了递归和递推两种思路。答案文件里通常会同时保留两种版本并标注各自的适用场景// 例题 9-1 数字三角形递推版 // 输入三角形行数 n 及每行数字 // 输出从顶到底的最大路径和 #include cstdio #include algorithm using namespace std; const int MAXN 110; int a[MAXN][MAXN], dp[MAXN][MAXN]; int main() { int n; scanf(%d, n); for (int i 1; i n; i) for (int j 1; j i; j) scanf(%d, a[i][j]); // 从底层向上递推 for (int j 1; j n; j) dp[n][j] a[n][j]; for (int i n - 1; i 1; i--) for (int j 1; j i; j) dp[i][j] a[i][j] max(dp[i1][j], dp[i1][j1]); printf(%d\n, dp[1][1]); return 0; }这段代码的参数含义dp[i][j]表示从位置(i,j)到底部的最大路径和递推方向是从下往上因为底部的dp值就是数字本身max函数来自algorithm在竞赛中可以直接用。答案文件里一般还会附一个递归记忆化的版本方便对比理解。读这类答案时建议先自己写一遍再和答案对照。重点看三个地方状态数组的维度是否和你一致、初始化条件是否遗漏、循环方向是否正确。这三个地方是 DP 题目 WA 的高发区。4. 避坑与排查例题答案使用中的五个血泪教训4.1 现象本地能过提交 WA原因最常见的是输入格式没对齐。书上的例题描述和在线评测系统的实际输入可能有细微差别比如多组输入的终止条件、数字之间是空格还是换行、是否有多余的空行。解决先看答案文件里有没有附带.in和.out样例文件用重定向方式本地测试。如果没有手动构造几组边界输入特别是最小规模和最大规模的情况。# 用样例文件本地测试 ./solution sample.in my.out diff my.out sample.out4.2 现象数组越界导致 RE 或结果玄学原因书上的代码为了简洁有时会把数组开到刚好够用。但实际题目中下标可能从 1 开始或者需要多开几个位置做哨兵。解决在答案文件的基础上把数组大小统一放大 10 到 20 个元素。比如题目说 n ≤ 1000就开到 1010 或 1020。这个习惯在竞赛中能省下大量调试时间。4.3 现象多组输入时结果累加错误原因全局数组或变量没有在每组输入前重置。这是新手最常踩的坑之一而且因为本地测试往往只跑一组数据很难发现。解决养成习惯——只要题目提到“多组输入”或“输入包含多组数据”就把memset或手动初始化放在循环内部的第一行。4.4 现象浮点数输出精度不对原因用了float而不是double或者printf的格式控制符写错。竞赛题目对浮点数的精度要求通常是“保留 c 位小数”但四舍五入的行为可能因编译器而异。解决统一用double输出时用%.*f动态指定精度。如果题目要求“四舍五入”注意 C 的printf默认就是四舍五入但浮点误差可能导致边界情况出错必要时加一个极小值1e-9。4.5 现象答案文件里的代码编译不过原因答案包可能是在不同编译器或不同标准下写的。比如用了 C11 的特性但你的编译环境默认是 C98或者用了某些平台特有的头文件。解决先确认编译命令。常见做法是加上-stdc11或更高标准g -stdc11 -o solution solution.cpp如果还是报错看错误信息里缺失的头文件或函数对照答案文件的注释说明确认它依赖的库或环境。5. 把例题答案变成自己的东西一个验证驱动的刷题习惯答案文件最大的风险是“看懂了”的错觉。我的做法是每看完一道例题的答案关掉文件自己从头写一遍然后做三件事。第一用题目描述里的样例数据跑一遍确认输出一致。第二构造一组边界数据——比如 n1、nmax、全相同、全不同——再跑一遍。第三如果时间允许把代码里的关键参数改一改观察结果变化确认自己理解每个变量的作用。// 自测模板在答案代码基础上加边界测试 // 以“开灯问题”为例测试 n1, k1 和 n1000, k1000 // 运行方式编译后手动输入或重定向这个习惯看起来慢但能帮你把答案里的“死代码”变成自己的“活知识”。从那以后我每次刷题都强制走一遍“样例→边界→改参数”的流程WA 率明显下降。另外建议把答案文件按自己的理解重新组织一遍。比如按算法类型建目录把同一类题目的答案放在一起旁边用注释写上“这题的关键是状态定义”或“这题的坑在输入终止条件”。这样积累下来考前复习时翻自己的注释比翻答案本身更有效。希望帮到你。本文还有配套的精品资源点击获取