简介：这份算法竞赛入门经典（第二版）例题答案包，对应刘汝佳《算法竞赛入门经典（第二版）》一书，专为ACM竞赛初学者和算法自学者设计，覆盖排序搜索、动态规划、图论、字符串处理、数学、数据结构、贪心、递归分治等核心算法知识点，可帮助读者对照书内习题快速验证解法、理解实现细节。压缩包共224个文件，以191个cpp源代码为主，配合12个in输入样例、10个ans输出答案及11个md说明文档，整体仅208KB，轻量但结构完整，便于按章节查找和对比测试。这份资料并非简单贴代码，而是通过完整可运行的解答与测试用例，让读者在动手调试中掌握算法思路与编码技巧，提升竞赛实战能力。目前已有2003人学习使用，适合准备ACM、蓝桥杯等算法竞赛的入门者系统练习与查漏补缺。
1. 例题答案怎么用，决定了你是在刷题还是在抄题
《算法竞赛入门经典（第二版）》的例题答案，是很多自学算法的人电脑里都存过一份的东西。但同样一份答案，有人刷完进了省队，有人刷完还是连动态规划的状态转移都写不利索。差别不在于谁更聪明，而在于拿到答案之后怎么用。
这本书的例题安排很有讲究：每道例题对应一个算法主题，从枚举、贪心到DP、图论层层递进。第二版相比第一版，题目和章节都做了调整，网上流传的答案版本也比较杂，有的是PDF手写笔记，有的是GitHub上的代码仓库，还有的是博客里零散贴的片段。我的建议是：你需要的不是「一份答案」，而是一套能辅助你完成「思考—实现—验证」闭环的参考实现。
这篇笔记不会替你把整本书的答案抄一遍——那没有任何意义。我会告诉你这套例题答案到底包含哪些东西、每一章该怎么刷、代码怎么写才能直接跑通、常见的坑都埋在哪里，以及如何用最短的时间把「看答案」变成「长自己的能力」。
2. 先搭出能跑例题的 C 语言环境：别让环境问题消耗你的耐心
2.1 Windows / macOS / Linux 三平台的编译器选型
刷这本书的例题，主流语言是 C/C++，因为绝大多数例题题解都是用 C 写的，第二版书里的代码也以 C 为主。你需要一个能编译 C11（甚至 C99 就够）的编译器，外加一个不那么折磨人的编辑方式。
我见过太多初学者把时间浪费在 IDE 配置上——VS 装了个组件结果不知道选哪个工作负载，Code::Blocks 下载了个带编译器的版本结果路径带中文名编译不了。我的建议是分情况处理：
- Windows 用户：直接装 MinGW-w64（注意选 posix 线程模型版本，不要选 win32 线程模型版本），装完把
bin目录加进系统 PATH。或者更省事一点，用 WSL 里的 gcc。 - macOS 用户：装 Xcode Command Line Tools，
xcode-select --install一行搞定，然后直接用clang，语法上兼容 GNU C 的大部分特性，刷题没问题。 - Linux 用户：
sudo apt install gcc build-essential（Debian/Ubuntu），或者sudo dnf install gcc-c++（Fedora）。
装完之后打开终端，敲gcc --version，能看到版本信息就说明环境通了一半。接下来你还需要一个趁手的编辑器，我个人推荐 VS Code 加 C/C++ 扩展，配置好tasks.json之后按Ctrl+Shift+B就能编译——但这段配置本身也可能成为一个坑，常见的坑是cwd设置不对导致找不到源文件，解决办法是把"cwd"设为${fileDirname}。
提示：如果你完全不想碰编辑器配置，直接用带终端的环境（比如 macOS 的 Terminal + vim，或者 Windows 的 Windows Terminal + nano）也完全可以。这本书的例题以单文件为主，不需要工程化管理。
2.2 最小验证命令：编译一个能读入输出的模板
环境装好之后，先别急着找例题答案。写一个只包含标准输入输出的最小程序，把「编译—运行」这条链路先跑通。这是后面所有例题验证的基础。
#include <stdio.h> int main() { int n; while (scanf("%d", &n) == 1) { printf("%d\n", n * 2); } return 0; }编译并运行：
gcc test.c -o test -std=c11 -Wall ./test然后输入5，按回车，看是否输出10。这里解释两个细节：scanf的返回值判断是在刷题时非常重要的习惯，它返回成功匹配的变量数，== 1表示成功读入了一个整数；while循环配合这个判断，可以处理输入中多组数据的情况——书里很多例题的输入格式都是「多组测试数据」，但你并不知道具体有多少组，所以这个模式是通用模板。
-std=c11指定语言标准，例题代码基本不需要 C11 特有功能，但加上能避免一些老的编译器默认标准导致的兼容性怪问题。-Wall会打开常见警告，刷题时警告往往意味着潜在 bug，比如scanf格式串写错、变量未初始化等。- 编译成功后如果出现
warning: implicit declaration of function，说明你调用了函数但没有包含对应头文件——这是初学阶段最常见的编译错误之一，先检查头文件。
2.3 虚拟 Judge 环境与本地测试的差异
这本书的例题答案在网上流传的代码，很多是直接在 OJ 上提交过的版本。但你在本地跑和提交到 OJ 上跑，有几个差异必须提前知道，否则会出现「本地跑得好好的，交上去就 WA」的诡异情况。
第一个差异是输入输出格式。本地你可以随意加printf("请输入n:")这类提示，但 OJ 是逐字符比对输出结果的，多一个空格、多一个换行、多一行提示文字，就是 Wrong Answer。所以例题答案里的代码，全都是「只输出规定内容」的写法，你在本地测试时千万不要顺手加调试输出——要么用注释包起来，要么用fprintf(stderr, ...)输出到标准错误流，OJ 不比对 stderr 的内容。
第二个差异是运行环境。本地 Windows 的scanf和 Linux 上的scanf在处理\r换行符时行为稍有不同，但只要你用的是scanf/printf族函数（而不是gets这类行输入函数），一般不会遇到。老版本编译器会把gets移除（C11 标准里已经删掉了），如果例题答案代码里用了gets，把它替换成fgets再测试。
第三是栈空间和内存限制。递归深度很大的题（比如某些 DFS 例题），在本地默认栈大小下能跑完，但 OJ 上可能直接 Segment Fault。遇到这种情况，常见做法是改成显式栈的非递归写法，而不是在本地调大栈——因为 OJ 的环境你控制不了。
#include <stdio.h> #include <string.h> int main() { char s[100]; fgets(s, sizeof(s), stdin); s[strcspn(s, "\n")] = 0; // 去掉末尾换行符 printf("[%s]\n", s); return 0; }注意fgets会把换行符也读进来，strcspn(s, "\n")找到换行符的位置并替换成\0，这是替代gets的标准写法，第二版例题答案的代码里一旦出现行输入，我一般就改成这个写法。
3. 例题答案的打开方式：从「看答案」到「和答案对话」
3.1 先想 30 分钟再打开答案
这是整篇笔记里最重要的一条方法论。这本书的例题和普通习题不同，每道题背后都是一个经典的算法模型——枚举、贪心、DP、图论、数论。如果你连题目都没读完就直接打开答案，那你得到的是一次「阅读理解」，而不是一次「算法训练」。
我见过一个做法非常有效，来自某位学长：每道例题先自己独立想 15 分钟，写不出来就再想 15 分钟，然后才允许自己看答案。注意这里有个限定条件：「允许自己看答案」不等于「从头到尾把代码读完」。正确的打开方式是——先看答案的解题思路部分（如果这份答案有注释），没看懂再看代码。
第二步是「跟着代码走一遍样例」。把答案代码抄进编辑器，编译运行，输入题目给的样例数据，验证输出是否和题目一致。这一步看起来机械，实际上非常重要，因为你在抄的过程中会注意到许多细节：数组开多大、循环边界在哪、状态怎么初始化。抄一遍，胜过读十遍。
第三步是关掉答案，自己重新实现一遍。这是检验「你真懂了」的唯一标准。如果你能不看任何参考，独立写出一个能通过样例的版本，那这道例题才算过。很多同学偷懒跳过这一步，结果就是「好像都会，一写就废」。
3.2 第三章「数组和字符串」的例题答案长什么样
第三章在第二版里是很多人的第一个坎。这一章的例题开始出现像样的算法思路了，不再是前两章的语法练习。比如例题 3-1（TeX 中的引号）和例题 3-2（WERTYU），这两道题都是「字符映射」类的题目，不涉及复杂算法，但特别考验你对输入输出的控制力。
以 WERTYU 这道题为例，核心思路是构造一个「键盘错位映射表」，然后逐个字符查表转换。网上流传的答案基本都长这样：
#include <stdio.h> #include <string.h> char s[] = "1234567890-=QWERTYUIOP[]\\ASDFGHJKL;'ZXCVBNM,./"; int main() { int c, i; while ((c = getchar()) != EOF) { for (i = 0; s[i] && s[i] != c; i++); if (s[i]) { putchar(s[i - 1]); // 找到错位前一个字符输出 } else { putchar(c); // 不在表里的字符（如空格）原样输出 } } return 0; }这里有几个细节值得注意。for循环结束后s[i]的值有两种可能：\0（说明没找到）或者等于c（说明找到了）。这个写法省去了一个found标志变量，是典型的 C 语言简洁风格。putchar每次输出一个字符，缓冲区由标准库管理，性能完全够用。s[i - 1]之所以是答案，是因为题目里说输入的字符是「按错一个键之后」打出来的，所以你输入的是错位后的字符，要找的是它左边那个正确字符。
我在这个阶段遇到过的一个常见问题是：为什么getchar()返回值要存在int类型而不是char类型？答案很简单——EOF的值通常是-1，而char可能是无符号类型，存不下负值。把int c写成char c，读到文件结尾时会死循环或者直接崩掉。这是 C 语言面试题级别的经典考点，也是做题时最容易翻车的地方。
3.3 第六章「数据结构基础」的例题答案：图论与树的实现细节
第六章是全书的分水岭。二叉树的递归定义、图的双连通分量、拓扑排序、最短路……这些内容的例题答案，网上版本质量差距很大，有的代码能跑，但逻辑绕；有的代码风格非常学院派，你照着抄会陷入大量指针操作的泥潭。我的建议是：这个阶段看答案的重点放在「数据结构的存储方式」上，而不是拼命抠算法细节。
以二叉树为例，第二版里有一个很经典的例题——小球下落（例题 6-6）。这道题的核心是模拟一个小球在一棵满二叉树上按开关值左右下落的过程。网上最常见的答案有两种：一种是直接开一个巨大的布尔数组模拟开关状态（toggle[left] = !toggle[left]），另一种是用位运算优化一整层。初学者先实现第一种就好：
#include <stdio.h> #include <string.h> #define MAXN 1 << 20 int tree[1 << 20]; // 开关状态，0 表示关，1 表示开 int main() { int depth, n; while (scanf("%d %d", &depth, &n) == 2) { memset(tree, 0, sizeof(tree)); int last = 1; for (int i = 0; i < n; i++) { int k = 1; for (int j = 0; j < depth - 1; j++) { if (tree[k] == 0) { tree[k] = 1; k = k * 2; // 向左走 } else { tree[k] = 0; k = k * 2 + 1; // 向右走 } } last = k; } printf("%d\n", last); } return 0; }这里tree数组的下标代表节点编号，根节点是 1，左子节点是k * 2，右子节点是k * 2 + 1。memset(tree, 0, sizeof(tree))每次重置状态数组，注意sizeof(tree)是整个数组的字节数，不是元素个数——这是新手特别容易搞混的地方。
这道题有个经典优化：当n特别大时，上面的逐个模拟会超时（因为每颗小球要下落深度层，总复杂度是n * depth）。优化的办法是观察每层开关的翻转规律，利用奇偶性直接判断最后一颗球落到哪个子节点——这就是所谓「找规律法」。很多答案里给的最后一版代码都是这种优化过的，但我的建议是：先把暴力模拟版本跑通，再去理解优化版本，两个版本对照着看，你才能理解「有时候算法题不是考察你会不会写循环，而是考察你能不能跳出来看问题」。
例题答案里图论部分，核心是「存图方式的选择」。邻接矩阵适合稠密图且节点数少的情况，邻接表适合稀疏图。第二版里最短路例题基本都用邻接表 + Dijkstra 或 SPFA。网上有些答案用邻接矩阵但不开够数组大小，导致访问越界，在本地可能不报错，但 OJ 上无限 RE。你自己写代码时记住一条：顶点数小于等于 100 才放心用邻接矩阵，否则优先邻接表。
4. 分章攻克例题：第二版各章的难点与高频错题分析
4.1 前两章：语法不熟还是逻辑不熟，用例题答案自测
第一章和第二章是热身章，例题难度不大，但有一个很隐蔽的坑：你以为你懂了，其实只是「看懂了答案里那几行代码」。这两章的核心是「输入输出格式控制」和「循环结构设计」。我在帮人 debug 时见过一个反复出现的错法——printf("%d ", a[i])多打了一个空格，导致输出格式不符。
怎么自测？你可以故意改掉答案里的一行（比如把循环边界从i <= n改成i < n），然后跑样例，看输出差多少。这样你能直观感受到循环边界错误带来的影响。第一二章其实不适合「背答案」，更适合「故意改错看后果」。
#include <stdio.h> int main() { int n, s = 0; while (scanf("%d", &n) == 1) { for (int i = 1; i <= n; i++) { s += i; } printf("%d\n", s); printf("\n"); // 注意：题目要求每组输出后带空行 } return 0; }注意上面代码里s没有在每组数据前重置。如果题目要求「多组输入每组分别计算」，s就必须在while循环内部初始化（int s = 0;写在while里面）。这个错误极其经典，几乎所有刷题的人都踩过一次。例题答案里要么直接在循环内重新定义s，要么在每次计算前手动清零。
4.2 第五章「C++ 与 STL」：为什么答案代码用的是 C++ 你却看不懂
第五章是第二版的一个特殊章节，它专门讲 C++ 的 STL 在竞赛里的用法。这一章之后的例题答案，代码风格会突然切换：vector、set、map、sort、string满天飞。如果你只会 C，打开这一章的例题答案会非常痛苦——别硬扛，花半天时间学一遍 STL 的基本用法更划算。
我看过的例题答案里，第五章最常考的是sort的自定义比较函数和map的计数用法。比如例题 5-2（木块问题）的答案，大量使用vector的push_back、pop_back、resize来模拟木块堆操作。
#include <cstdio> #include <string> #include <vector> using namespace std; const int maxn = 30; vector<int> pile[maxn]; int main() { int n; char s[10]; scanf("%d", &n); for (int i = 0; i < n; i++) { pile[i].push_back(i); } // 模拟操作省略 return 0; }vector在这里替代了「每个木块堆的大小会动态变化」的需求。如果你不会 C++，你可能想用链表来实现木块堆的动态增删——那会非常痛苦。这就是第五章存在的意义：让选手知道 STL 能帮你省多少事。例题答案里出现#include <bits/stdc++.h>这种写法，在 OJ 上能过，但在本地如果用 MinGW 的某些老版本可能编译不过。
我建议你把第五章所有例题的答案代码统一用 C++17 标准编译（g++ test.cpp -o test -std=c++17），并在本机装好验证环境。踩坑概率最高的点是：vector<int> pile[maxn]是固定长度数组套动态数组，下标不能越界；pile[i].size()返回的是size_t类型，和int比较时要注意符号警告。
4.3 第七到九章：暴力求解法、高效算法设计、动态规划
七八九这三章，是整本书的精华，「例题答案」里最值钱的部分也在这里。第七章讲的是回溯法和剪枝，第八章讲的是分治、贪心、双指针，第九章讲的是动态规划。很多同学就是在这几章开始掉队的——不是因为难，而是因为前六章的积累没到位。
第七章的经典例题是「八皇后」和「素数环」。答案代码里通常递归 + 剪枝并行，你在本地测试时要特别注意：vis数组（访问标记）在递归返回后必须恢复现场。忘了恢复，是回溯法 WA 的头号原因。
#include <stdio.h> #include <string.h> int n, ans = 0; int vis[10]; int col[10]; void dfs(int row) { if (row == n) { ans++; return; } for (int c = 0; c < n; c++) { int ok = 1; for (int r = 0; r < row; r++) { if (col[r] == c || col[r] - c == r - row || col[r] - c == row - r) { ok = 0; break; } } if (ok) { col[row] = c; dfs(row + 1); } } }这里用col[r]表示第 r 行的皇后放在第几列，判断冲突的条件是「同列」或者「对角线」——col[r] - c == r - row和col[r] - c == row - r分别代表两个方向的对角线。这个判断不需要额外开vis数组，因为逐行放置天然保证不同行。网上有些答案用三个vis数组（列、主对角线、副对角线）来剪枝，这样能把判断从 O(row) 降到 O(1)，但写起来容易出错——先跑通上面的朴素判断版，再优化也不迟。
第九章动态规划的例题，答案代码短小精悍，但每一行都是精华。比如经典的「最长上升子序列」，朴素 DP 是 O(n²)，而答案给的往往是优化版。但我的建议是：第一遍刷 DP 例题，必须先把 O(n²) 的写法自己抄一遍，再去看优化版本，否则你根本不知道优化在优化什么。
5. 避坑指南：刷例题答案时的 5 个高频踩坑现场
5.1 现象一：答案代码本地编译报错，在 OJ 上却能过
原因：网上流传的很多答案年代久远，针对的是老版 GCC（比如 GCC 4.x），那时候void main()还能编译过、不写头文件也能隐式声明函数。你本地的 GCC 版本到了 12 或 13，标准从严了，这些代码就编译不过。 解决：手动替换老式写法——void main()改成int main()，gets改成fgets，clrscr()直接删除，#include <iostream.h>改成#include <iostream>。如果答案代码里出现for(int i = 0; i < n; i++)这种在for括号里定义变量的写法，老标准要求 C99 才支持，编译时加-std=c99或-std=c11即可。
5.2 现象二：本地跑样例全对，提交 OJ 显示 Presentation Error
原因：输出格式和题目要求不完全一致，通常是少了空行或多了空格。Presentation Error 是 WA 的序曲，OJ 能识别出你的输出和标准输出非常接近但格式有差异。 解决：严格对照题目输出要求，特别注意「每组输出之间有一个空行」和「每组输出之后有一个空行」的区别。判断方法是看输出描述里有没有「blank line」字样，以及样例输出的最后一个数字后面是否还有空行。例题答案一般会在注释里标明格式要求，但有些版本的答案代码没有，你需要自己对照题意检查。
5.3 现象三：答案代码里用了 C++ 特性，但文件后缀是.c
原因：有些博客贴代码时不标注语言，读者复制下来存成.c文件，用 gcc 编译 C++ 语法当然报错。 解决：看到代码里有#include <iostream>、vector、using namespace std这类内容，一律存成.cpp后缀，用g++编译。这是最容易解决的问题，但也是翻车频率最高的问题。
5.4 现象四：数组开小了，本地小数据跑得欢，OJ 大数据直接 RE
原因：很多例题答案里为了省事，数组大小按题目给的上限加了个小余量。但如果题目的测试数据在上限附近再加上一些边界情况（比如字符串还要存结尾的\0），数组就可能越界。 解决：刷题时把数组稍微开大一点，比如题目说n <= 1000，你开1005（留几个余量给边界和字符串结尾），不要精打细算到1000。这不算浪费，是安全习惯。特别是字符串处理题，char s[100]只能存 99 个字符加一个\0，如果你scanf("%s", s)读入的字符串长度刚好 100，就直接越界了。
5.5 现象五：多组输入输出，答案代码只处理了一组就退出了
原因：部分例题答案贴的是「核心代码片段」，不是完整的可 AC 提交版本。作者省略了外层while循环来保持代码整洁，结果你直接复制提交，跑完第一组数据程序就结束，OJ 判定答案根本不完整。 解决：养成一个习惯——拿到答案代码后先看main函数里有没有while (scanf(...) == ...)这类循环。没有的话，先确认题目是不是多组输入；是的话，把核心逻辑包进while循环里。注意在包裹的过程中，原来函数内的局部变量可能需要在循环体内重新初始化，这就是 4.1 里那个s清零翻车现场的重演。
提示：网上找不到靠谱答案时，可以在 OJ 上直接搜题目名，看通过的代码的讨论串，经常能翻到某个人写的详细题解注释版本。这条路径比良莠不齐的博客可靠，因为代码经过了 OJ 的验证。
6. 把例题答案变成自己的武器：一个改题练习法与检查清单
刷完一遍例题答案之后，如果你只是「看懂了」，那这本书的白书称号对你来说就白瞎了。你需要做一件事——改题。我每次带人刷这本书，最后都会让他们做这个练习：把例题答案的代码拿来改一行，让它变成另一道题的解。
具体做法是这样的：选一道你已经「看懂了」的例题，比如 WERTYU，然后给自己出一个变体：输入和输出不变，但键盘错位的方向和原题相反（也就是说，输入的字符是正确键位，你需要输出它右边一个键对应的字符）。打开答案代码，改哪一行？答案是s[i - 1]改成s[i + 1]。就这么一行，你理解整个映射表的结构了吗？理解了，因为你知道了s数组是「物理键盘从左到右排列的字符表」，i - 1就是往左错一位，i + 1就是往右错一位。
这个训练的本质，是让你从「抄结构」升级到「改结构」。网上各种例题答案版本你都能找到，但只有当你亲手改动过代码、并且改坏了再改回来之后，那些数组、循环、状态转移才会长在你脑子里。我做过一个不算严谨的统计，同一道题，只看了答案的人，一周后复现正确率不到三成；做完改题练习的人，复现正确率能到七成以上。
改题时有一个实用技巧：先复制一份原答案代码，然后在不看原答案的情况下打开新文件，凭记忆写改动版。写完以后编译、跑样例，对照原答案排查。这个「凭记忆写」的过程会暴露你对代码的理解盲区——你会清晰地看到：哦，原来我根本没记住vis数组的恢复逻辑，原来我把==写成了=。
最后给你一个自查清单，刷每一道例题答案前对照一遍：
- 题目要求的时间、内存限制大概是什么量级（这决定了你该用 O(n²) 还是 O(n log n) 的算法）
- 输入数据规模的上限（这决定了数组开多大，是否需要动态分配）
- 多组输入还是单组输入（这决定了主循环怎么包）
- 输出格式有没有空行要求（这决定了最后那个
\n该不该多打） - 有没有浮点数的精度比较问题（书里例题 3-2 这类涉及小数的，一般用 EPS 而不是
==判断）
回到我自己的经验上：这本书的例题答案，最正确的用法是「参考答案，而不是依赖答案」。我在刷到第九章时的一个晚上，卡在一道 DP 状态定义上两个多小时，打开答案一看，状态定义比我想的少了一维。那一刻我意识到，两个小时的挣扎其实没有白费——因为如果没有那场挣扎，我不会真正理解为什么少一维是对的，更不会在以后的比赛中主动往「简化状态」的方向想。就是这么一点一点磨出来的东西，才是这本书真正想给你的。
希望这篇笔记的每个注意点都能帮你在刷题路上少开一次gcc编译报错的终端、少提交一次 Presentation Error，也希望你刷完所有例题答案后再回头看：原来那些代码不是用来背的，是用来对话的。祝你刷题顺利。
本文还有配套的精品资源，点击获取
