企业官网建设流程全解析

简介：《算法竞赛入门经典（第二版）》例题答案包由刘汝佳原书配套代码仓库整理而成，面向备战ACM/ICPC竞赛、系统学习算法基础的高校学生与编程爱好者。压缩包共含224个文件，其中191个cpp源程序对应原书各章节例题与练习解答，12个in与10个ans构成配套测试数据，便于本地运行对照输出，另有11个md文档梳理代码实现思路，整体仅208KB。内容覆盖基础排序与搜索、动态规划（背包、最长公共子序列）、图论最短路与最小生成树、KMP字符串匹配、组合数学与常用数据结构等竞赛核心考点，代码风格清晰，并包含边界条件处理、快速输入输出等实战细节。已有2003人学习下载，这份答案包既能辅助逐题精读原书，也可作为赛前复习算法模板、提升编码效率的高性价比参考资料。

1. 别急着翻答案：先让例题卡住你十分钟

很多入了算法竞赛门的同学，手里都有这本经典的入门教材，刷到例题做不下去的时候，第一反应就是上网找一份例题答案直接抄。我见过不少人把答案代码存进收藏夹，复制粘贴提交AC，觉得自己“会了”，结果过两周连原题都写不出来。这份例题答案真正的价值，不是让你跳过思考，而是给你一个高质量的对照样本——在你被题目卡住的时候帮你定位思路偏差，在你写完代码之后帮你对比边界条件和写法习惯。它适合卡在某道例题超过半小时的人，也适合准备校赛、ACM新手赛的选手，不适合一题没写就急着抄代码的人。先读下去，我会告诉你这份答案应该怎么用，以及哪些坑我替你踩过了。

2. 例题答案的组织方式：目录结构与三遍阅读法

2.1 先看懂答案的目录结构，别一上来就翻到最后一题

拿到一份例题答案，第一件事不是打开代码，而是看它怎么组织文件。正规一点的整理版，都会按教材章节建目录，每道例题单独一个文件，命名最好能直接对上题号。

我一般拿到手会先列一下清单，确认覆盖了教材里标了“例题”的所有题号，而不只是挑着做了几题。检查命令在Linux或macOS终端里这样写：

find . -type f \( -name "*.c" -o -name "*.cpp" \) | wc -l find . -type f -name "*.cpp" -o -name "*.c" | sort

第一个命令统计总文件数，第二个命令按文件名排序输出，方便你对照教材目录检查缺失。对不上号的文件，多半是整理者自己添加的补充题，先忽略就好。

2.2 本地编译环境：一劳永逸的检查方式

答案代码拿到手，第一件事是编一遍确认它在你机器上能跑。不要偷懒只在OJ上提交试，本地编译能让你更快看到警告信息。我习惯用的编译命令：

g++ -std=c++11 -O2 -Wall UVa679.cpp -o UVa679 ./UVa679 < input.txt

-std=c++11指定语言标准，过老的教材代码可能只用了C++98语法，这个参数向下兼容情况比较好；-O2开启优化，有的答案代码不开优化时行为正常，开了优化才暴露潜在的未定义行为；-Wall打开编译警告，数组越界、变量未初始化这类隐患都会在这里露头。把测试样例写到input.txt里，用重定向输入运行，这样跑多组数据时不用反复手敲。

2.3 三遍阅读法：把答案从“别人的代码”变成“自己的工具”

我推荐一套三遍阅读法，这也是我拆这份答案时最常用的一套流程。

第一遍：自己先写，卡住十五分钟再看答案的“思路段”，不看代码。这一遍的目的不是抄，是确认自己的思考方向对不对。如果只是某一层循环想错了，根本不值得去看代码；如果是状态设计没想明白，那看答案代码也能理解半天。

第二遍：对着代码默读，把关键变量和边界条件标注出来。重点看三样东西：数组开多大、循环结束条件是什么、状态转移方程在代码里体现在哪一行。在代码旁边写下注释，不写注释等于白看。

第三遍：合上代码，自己重新写一遍，再拿你写的和标准答案做对比：

diff -u my_solution.cpp standard_solution.cpp

diff输出的每一行差异都值得想一下，是自己没理解边界，还是标准答案里用了你没掌握的函数。这一步做到位，这份答案才算真正开始属于你。

3. 三类经典例题代码拆解：从枚举优化到DP再到图论

3.1 最大连续和：从O(n^3)到O(n)的三步优化

这本书里枚举优化讲得非常经典，最大连续和问题是典型的例子。初学者第一反应是三重循环枚举起点、终点、累计求和，复杂度O(n^3)。能够优化到O(n^2)甚至O(n)，靠的是对中间计算过程的复用。

#include <cstdio> #include <algorithm> using namespace std; int a[100005]; int main() { int n; scanf("%d", &n); for (int i = 0; i < n; i++) scanf("%d", &a[i]); int ans = a[0]; // 答案至少包含一个元素 int cur = 0; // 当前以 i 结尾的最大连续和 for (int i = 0; i < n; i++) { cur = max(a[i], cur + a[i]); // 要么从 a[i] 重新开始，要么接上之前的连续段 ans = max(ans, cur); } printf("%d\n", ans); return 0; }

这段代码的核心是cur这个状态变量。每一轮迭代里，cur + a[i]表示把当前元素接到前面最优连续段的末尾，a[i]则代表放弃前面的部分、从当前元素重新起头。二者取最大值，就是“以 i 结尾的最大连续和”。ans则在每一轮里保留历史最大值。逻辑不复杂，但最容易写错的点是把初始化写成0，这样一来全负数数组会输出0而不是最大负数。所以ans初值设为a[0]，cur初值也是a[0]但循环从i = 1开始也可以，或者像代码一样从0开始让cur从空段接续。这个边界问题用随机的负数数组做一轮测试就能暴露出来。

3.2 数字三角形：从递归到递推的状态设计

数字三角形是动态规划入门的必做题，答案代码里最常见的是递归加记忆化，也有直接写递推的版本。我建议你两种都看一遍，因为递归版能帮你理解“状态”是什么，递推版能帮你写出更稳定的比赛代码。

#include <cstdio> #include <algorithm> using namespace std; int a[105][105]; // 三角形值 int dp[105][105]; // dp[i][j] 表示从 (i,j) 出发走到最底层路径的最大和 int n; int solve() { // 自底向上，最后一层就是 a 本身 for (int i = 1; i <= n; i++) dp[n][i] = a[n][i]; for (int i = n - 1; i >= 1; i--) { for (int j = 1; j <= i; j++) { dp[i][j] = a[i][j] + max(dp[i + 1][j], dp[i + 1][j + 1]); } } return dp[1][1]; } int main() { scanf("%d", &n); for (int i = 1; i <= n; i++) for (int j = 1; j <= i; j++) scanf("%d", &a[i][j]); printf("%d\n", solve()); return 0; }

状态定义成dp[i][j]为从当前位置走到最底层的最大和，决策就两步：往左下走还是往右下走。取两个子状态的最大值，加上当前格子的值，递推公式就出来了。自底向上的写法避免了递归函数调用开销，也省去了记忆化数组的初始化判断。这里要注意dp[n][i]的初始化必须放在所有递推之前，如果忘记初始化，递推第一层读到的就是未定义值。另一个容易踩的坑是三角形边长超过105，所以刷题平台上如果数据范围变大，记得同步扩大数组维度，或者直接用vector动态分配。

3.3 Dijkstra优先队列实现：堆里的pair别写反

图论部分，这本书例题覆盖面很广，最短路径是必须吃透的一类。优先队列优化版的Dijkstra，答案里最常见的写法就是priority_queue<pair<int, int>>，但pair的排序规则坑过很多人。

#include <cstdio> #include <vector> #include <queue> #include <climits> using namespace std; const int MAXN = 100005; vector<pair<int, int>> edge[MAXN]; // 邻接表，pair<目标点, 边权> int dist[MAXN]; void dijkstra(int s, int n) { for (int i = 1; i <= n; i++) dist[i] = INT_MAX; dist[s] = 0; // pair<距离, 点编号>，因为优先队列默认大顶堆，所以要存负距离 priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq; pq.push(make_pair(0, s)); while (!pq.empty()) { int d = pq.top().first; int u = pq.top().second; pq.pop(); if (d > dist[u]) continue; // 惰性删除，跳过旧记录 for (auto &e : edge[u]) { int v = e.first; int w = e.second; if (dist[u] + w < dist[v]) { dist[v] = dist[u] + w; pq.push(make_pair(dist[v], v)); } } } }

priority_queue的默认比较器是大顶堆，直接存pair<距离, 编号>会先弹出距离大的节点，完全违背Dijkstra贪心策略。所以要么像代码里这样指定greater<pair<int, int>>，要么存pair<-距离, 编号>。这两种写法在答案里都出现过，我推荐显式写greater的版本，可读性好很多。if (d > dist[u]) continue是惰性删除，因为同一个节点可能被多次入堆，弹出的距离比已知最短距离大就直接丢弃，这是保证复杂度的关键。很多抄了这段代码的读者会忽略这一行，结果就是死循环或者错误答案。邻接表用vector<pair<int, int>>存储，遍历时拿到v和w再更新，逻辑完整紧凑。

4. 对照答案做题的五个翻车点：从编译错误到TLE的排查记录

4.1 数组开小：样例AC不代表边界AC

现象：我用答案代码测试书上的样例输入，输出完全正确，信心满满提交到OJ，结果是Runtime Error。

原因：例题书上的输入数据通常很小，样例只能验证逻辑，验证不了边界条件。我碰到过一道字符串处理的题，答案代码数组开的是char s[105]，但原题数据范围写的是最长1000个字符，超过长度后越界写入，直接栈破坏。

解决：提交前先看一眼原题的约束范围，然后检查答案代码里数组的尺寸。s[105]就改成s[1005]，这行改起来只用十秒，不查的话要耗半小时调试。从那以后我拿到答案代码的第一件事，就是检查所有数组尺寸是否能覆盖题目给出的最大边界。

4.2 iostream拖慢运行速度：本地一瞬，OJ超时

现象：在本地跑，答案代码瞬间出结果。提交到OJ，输入数据一大就TLE，时间卡在几百毫秒的边缘。

原因：cin和cout默认要和C标准IO同步，这个同步机制有额外开销。小数据量看不出来，一旦输入规模到十万级以上，差距就是一倍到两倍。有些例题答案源码用的是scanf和printf，但如果你自己在答案基础上加了cin读入，就会拖慢整体速度。

解决：要么保留答案代码原有的scanf/printf写法，要么在main函数开头加这两行：

ios::sync_with_stdio(false); cin.tie(0);

第一行关闭与C标准IO的同步，第二行取消cin和cout的绑定。这两行写上是救命良药，但要注意关闭同步后，scanf和cin就不能混用了，否则读入顺序会乱。

4.3 文件重定向没关：本地花屏，提交直接卡住

现象：打开答案代码，发现里面有freopen("input.txt", "r", stdin)这行，本地跑能正常读文件，但OJ上提交时这行代码会让程序去读一个不存在的文件，然后什么输出都没有。

原因：很多整理者在本地调试时用重定向读文件，方便批量测试，但提交前忘了注释掉这行。这是常见的不小心，属于历史遗留问题。

解决：本地测试没问题之后，提交前把这行freopen注释掉，或者改成：

#ifdef LOCAL freopen("input.txt", "r", stdin); #endif

在代码开头定义LOCAL宏就是本地调试模式，提交到OJ时不会自动定义，重定向自然失效。这个技巧建议直接写进自己的模板里。

4.4 看完答案就“会了”：代码合上就忘，两周后原题还是不会

现象：对着答案代码看了半小时，每一步都看懂觉得理解了，过了两周再翻同一题，写不出完整代码。

原因：看懂别人的代码是一个被动接受过程，大脑没有经历“自己推导状态转移方程”的主动构建步骤。注意力流向了理解，而不是生产，记住的只是一段文字，不是解题思路。

解决：启用三遍阅读法里的第三遍——不看答案重写。重写时卡住不要马上翻答案，先想一分钟，再卡住再看一眼答案的关键行，然后继续合上写。一道例题这样折腾三四轮，思路就成了你自己的。如果你连续三次在同一个位置卡住，说明你对这个算法类型的熟练度还不够，去找教材里同类型的其他题再练两遍。

4.5 编译器版本差异：OJ不认你的代码

现象：本地用新版GCC编译没问题，提交到OJ却报compile error，提示某个头文件找不到或者某个函数未声明。

原因：答案代码里有些用了C++11或C++14的特性，比如auto关键字、nullptr、unordered_map，但某些旧OJ默认编译器是C++98标准。还有一些代码用#include <bits/stdc++.h>这个万能头，它在GCC上能用，但不是标准头文件，换个编译器就报“No such file or directory”。

解决：我平时用-std=c++11编译，如果确认答案是老代码但平台支持C++14或C++17，就升级编译参数再试。万能头的问题，直接把#include <bits/stdc++.h>替换成具体的头文件，比如换成<cstdio>、<vector>、<queue>、<algorithm>，每行一个，这样代码就算换编译器也稳。

5. 把例题答案升级成自己的模板库：输出记录法与变式验证

5.1 输出记录法：让每道例题的复习变得可追踪

看过答案不代表拿下这道题，真正的检验标准是“一周后能不能独立AC”。我习惯用一张表跟踪每道题目的掌握状态：

这张表不需要复杂工具，一个文本文件就够。记录的核心价值不是做统计，而是让你每复习一次就看到自己上次的薄弱点。标注为“否”的题，建议两天后立刻重写一次。标注为“是”的题，放进下一轮复习周期，两周后再写一次。这样做下来，一个算法专题的掌握情况一目了然。

5.2 变式验证：改一个参数，检验你是否真的理解

把答案代码背下来没有意义，要验证理解深度，可以试一个方法：改动题目中的一个条件，然后看标准答案还能不能跑通。

举一个具体做法：随便选一道样例答案里用了n <= 1000范围限制的题，把数组扩大十倍的测试文件造出来：

python3 -c " import random n = 10000 print(n) for _ in range(n): print(random.randint(-1000, 1000), end=' ') print() "

然后拿标准答案去跑这组数据：

./solution < big_input.txt

如果程序在合理时间内退出并给出结果，说明你的理解到位、代码的复杂度达标。如果内存溢出或者耗时异常，就说明原答案可能只是针对小数据设计的，你需要自己优化算法。这个验证方法能帮你从“看答案的人”变成“懂答案结构的人”。

另一类变式是改输出要求。比如一道题要求输出所有解，你可以改成输出解的个数；要求输出最小值的题，改成输出最大值。每次变式都是一次完整的“读题-修改-调试”循环，这个过程里你会被迫去理解原答案里每一行代码承担的责任。

从我自己拆这份例题答案的经验来看，真正拉开差距的不是看答案的数量，而是重写的次数。一道例题你重写三遍，比你看三十道题的答案有用。从那以后，我每次从答案里学到一种解法，都强制自己当晚不看代码重写一遍，再构造一组更大的数据验证复杂度，第二天把这题记录到表格里并安排复习日期。坚持做完整的三遍阅读加输出记录，希望帮到你，祝你在算法竞赛这条路上走得更稳。

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