企业官网建设流程全解析

简介：《算法竞赛入门经典（第二版）》例题答案包，面向备战ACM/ICPC及算法入门学习者，提供刘汝佳教材各章节例题的完整代码实现与测试数据。压缩包共224个文件，以191个C++源程序为主体，并配12个输入样例、10个输出答案和11个Markdown说明文件，总大小约208KB，便于按章节对照调试。内容覆盖排序搜索、动态规划、图论、字符串处理、数学基础、常用数据结构、贪心、递归分治及快速IO等竞赛核心知识点，每道例题均包含可直接运行的代码与对应判题数据，适合在理解教材后动手验证并内化算法思想。已有1996人学习下载，资源短小精悍，是系统刷题和赛前巩固的高性价比参考。 先说点题外话。很多读者拿到《算法竞赛入门经典（第二版）》后，第一反应是上网找例题答案。这本书口碑好，但配套资源分散，网上能找到的解答版本五花八门，有的只有代码没有思路，有的思路写得太玄看不懂。我当年把这本书刷了两遍，第一遍对着答案抄，第二遍才真正体会到例题的价值——它给的从来不是标准答案，而是一条“看到题目条件后该怎么往下想”的路径。这篇文章就把我反复揣摩后觉得最值得细说的例题整理出来，从思路推导、代码实现、常见踩坑到性能优化一次讲透，适合正在刷紫书的算法竞赛新手，也适合想快速回顾基础算法模型的老手。如果你手上正好有这本书，建议边看边手写代码；没有书也不影响，核心思路我完整写在下面。

1. 这本例题集的真正价值：先学会“被剧透”，再学会“自己演”

1.1 例题答案不等于题解，它是一套思维脚手架

很多初学者把例题答案当成“对答案”的工具，做不出来就翻答案，看懂了就觉得自己会了。但紫书里的例题和练习题性质完全不一样。练习题考察的是“你会不会这个算法”，例题则是在示范“遇到这类问题，经验丰富的选手会怎么分析”。所以例题答案里最重要的不是那几十行代码，而是代码前面的推导过程、边界条件讨论和复杂度估算。

我的建议是：拿到一道例题，先给自己设定一个无声思考的时间窗口，哪怕只有二十分钟，也要把“暴力解法长什么样”“最坏情况要跑多久”“有没有明显可以优化的冗余计算”这三个问题写下来。之后再翻开答案，重点不是看代码抄得对不对，而是对比自己卡在哪个环节——是没想到用栈？还是没意识到要排序？这个“卡点”就是你最需要补的思维短板。

1.2 例题的选择顺序：按章节梯队推进，不要跳着翻

第二版的章节结构有一个明显的递进关系：前四章是语法、输入输出、数组和字符串、函数与递归，属于“地基”；第五章开始进入排序、栈、队列等数据结构；第六章以后是树、图、动态规划和数学专题。我的亲身教训是：跳过第二章直接看第六章的图论例题，会有种“每个字都认识但完全不知道怎么落地”的挫败感。老老实实按章节推进，虽然看起来慢，但每一章例题里铺垫的技巧会在后面反复出现，比如栈的模型在第6章的表达式求值、第8章的单调栈里都会用到。跳着刷的结果往往是前面的坑没填平，后面越看越乱。

2. 以“铁轨”为例，拆开一道经典例题的完整思考链路

2.1 题目在问什么，为什么它非常容易做错

铁轨（UVa 514）是第六章“数据结构基础”里很有代表性的一道题。题目背景是火车调度：车厢编号从1到n按顺序从A方向驶入，车站只有一个“栈式”的岔道，也就是后进入的车厢可以先出去，问给定一个目标的出站顺序，这个顺序能不能实现。

初次接触这道题的人最容易犯的错误是“盯着目标序列做局部判断”。比如有人会想：如果目标序列里出现了降序片段，就认为一定不可能，因为降序意味着后进的车要先出。这个判断错得很隐蔽。举个反例，n=3，目标序列是2 1 3：2先出，然后1出，最后3出，这是完全可行的——车厢1先进站，车厢2紧接着进去，2出站后1再出站，3最后直接通过。这里存在降序“2 1”，但结果是可行的。所以这道题不能用任何静态的“逆序对”规则去判断，必须模拟整个进出栈过程。

2.2 模板级解法：双指针加栈模拟

正确的做法是模拟“入站”和“出站”两个动作。设当前待入站的第一个车厢编号为A，目标序列当前要匹配的位置为B。算法描述如下：

1. 只要 B 还没有匹配完，就重复操作。
2. 如果当前栈顶恰好等于 target[B]，弹出栈顶，B 后移。
3. 否则把车厢 A 压入栈中，A 加一；如果 A 已经超出 n 而栈顶又不等于 target[B]，说明无法匹配，直接判定失败。

这个算法本质上是一种贪心：当栈顶元素等于当前需要的目标元素时，立即弹出一定不会错过正确答案。因为晚弹出并不会给后面的元素让出更多空间，反而会阻塞栈顶。C++ 实现如下：

#include <cstdio> #include <stack> using namespace std; const int MAXN = 1000 + 10; int target[MAXN]; int main() { int n; while (scanf("%d", &n) == 1 && n) { while (scanf("%d", &target[1]) == 1 && target[1]) { for (int i = 2; i <= n; i++) { scanf("%d", &target[i]); } stack<int> s; int A = 1, B = 1; bool ok = true; while (B <= n) { if (!s.empty() && s.top() == target[B]) { s.pop(); B++; } else if (A <= n) { s.push(A++); } else { ok = false; break; } } printf("%s\n", ok ? "Yes" : "No"); } printf("\n"); } return 0; }

建议把这段代码当做模板来背，因为它体现了“序列模拟题”的通用写法：两个指针分别表示输入源和目标位置，中间用一个数据结构（栈、队列、双端队列）作为缓冲。

2.3 这道题最常见的翻车点：读入格式

很多人代码逻辑写对了，一交上去就是 Wrong Answer。原因几乎都出在输入上。这道题的多组数据结构非常容易踩坑：第一行是一个整数n，表示车厢数，n=0代表整个输入结束。接下来每行是一个目标出站序列，直到该行第一个数字是0为止，代表这一组样例结束。也就是说一个“0”只结束当前序列，需要再接下一组序列；两个“0”才是结束整个测试。

我建议把输入解析封装成一个函数，或者在主循环里严格区分“第一行0”和“序列首元素0”两个分支。这个坑在紫书很多例题里都存在：第一版用C语言的scanf，第二版在部分题目上同样保留这种输入风格，所以熟练处理多组输入本身就是竞赛基本功之一。

3. 例题答案里反复出现的三个模型：暴力、数学、二分

3.1 模拟题的隐藏考点：数据范围往往会暴涨

很多例题表面上考“模拟”，实际考的是“你有没有发现这里不能硬模拟”。举一个大家都熟悉的例子：3n+1问题（也就是 Collatz 猜想）。题目逻辑非常简单：给定一个正整数，如果是奇数就乘3加1，如果是偶数就除以2，反复操作直到变成1，问一共需要多少步。

如果不假思索地按照定义模拟，代码几分钟就能写完。但它有两个坑。第一个坑是int溢出：n 在计算过程中可能远超初始值，比如 n=113383 时的中间结果能达到 2482111348，明显超过32位有符号整数的上限，必须用long long。第二个坑是“区间大小顺序”：题目输入的两个数 a、b 并不保证 a <= b，计算前需要交换，但输出时必须保持原始顺序。这种题就是一个试金石：考的不是你会不会写循环，而是你知不知道竞赛题的“边界条件”永远是隐藏主角。

3.2 数据结构题的数学优化：小球下落

第六章还有一道特别适合用来体会“模型推导”的例题：小球下落（UVa 679）。一棵满二叉树，深度为D，每个节点有一个开关，初始全部关闭。小球从根节点落下，每经过一个节点，如果开关是关闭的，就向左子树走，然后开关变为打开；如果开关是打开的，就向右子树走，然后开关变为关闭。现在有 I 个小球依次落下，问最后一个小球落在哪个叶子节点。

最直接的做法是模拟每个小球的完整下落路径，复杂度 O(I * D)。听上去不算大，但题目的数据范围里 I 最大可以达到 2^D - 1，而 D 最大是20，这意味着模拟次数接近一百万乘以20，勉强能跑，但已经处在超时边缘。如果 D 再大一点，模拟法就完全不可行。

答案的巧妙之处在于：不需要模拟每一个小球，只需要观察单个节点上小球到达的奇偶性。某个节点第一次被小球访问时，小球会走左边；第二次被访问时，会走右边。所以第 I 个小球到达某个节点后，如果 I 是奇数，它就是该节点被访问的第 (I+1)/2 个球，应该往左；如果 I 是偶数，它就是第 I/2 个球，应该往右。于是只要用当前是第几个球决定每次往左还是往右，一层一层走下去，O(D) 就能定位到最终叶子节点。这个思路虽然看似数学化，实际操作起来非常机械，非常适合作为“把模拟转化为递推”的第一个训练案例。

3.3 查找问题的标准套路：排序加二分

紫书第五章有一道很基础的例题，题目是一堆大理石，每个大理石上有一个数字，要求回答某个数字出现在哪个位置。因为需要回答多次询问，最笨的方法是对每次询问都扫描一遍数组，复杂度 O(N*Q)。而标准做法是先对数组排序，再对每个询问二分查找，复杂度降为 O(N log N + Q log N)。

这道题的代码本身不难，但它带出了一个非常重要的判断习惯：当题目里有大量询问，并且数据顺序不影响答案时，第一反应就应该是排序加二分。很多人在做图论或者树论题时碰到“查询子树上小于某个值的个数”“查询区间内第K大”这类问题，第一反应是复杂的平衡树，反而忘了“排序后离线处理”这个最朴素的思路。这种“先排序再回答询问”的思维范式，就是靠这种基础例题建立起来的。

4. 例题答案之外：竞赛实战中的代码习惯和性能意识

4.1 多组输入输出的统一模板

刷完十几道例题后你会发现，80%的输入都是“以0结束”或“先读一个T表示组数”这两种格式。把这两种模板提前写好，能省下大量思考时间。

“以0结束”的用法：

int n; while (scanf("%d", &n) == 1 && n) { // ... }

“先读组数”的用法：

int T; scanf("%d", &T); while (T--) { // ... }

这里值得注意一个细节：scanf的返回值尽量用“== 1”或者“== 2”这样的形式判断读入是否成功，而不要只写while (scanf("%d", &n))。因为当输入文件结束时，scanf会返回 EOF（即 -1），有些编译环境下while(scanf(...))仍然会进入循环，导致读入未初始化的变量。这种错误非常隐蔽，在本地测试时几乎发现不了，但在线评测一跑就会出错。

4.2 全局数组、memset 和递归深度

紫书的例题代码有一个共同习惯：把大数组声明在main函数外面。这不是随便写的，而是因为局部变量存储在栈上，栈空间通常只有几兆字节，声明一个int a[1000000]就可能爆栈；而全局变量在静态存储区，空间大得多。同理，如果题目要求的递归深度可能达到数万层，像 DFS 遍历一条很深的链，C++ 默认的栈大小往往不够用，这时候应该考虑改成显式栈模拟或者递推。

另外，memset看起来是万能的初始化工具，但它按字节填充，对它来说最安全的赋值是0和全0xFF（即-1）。想填充成1或其它整数，用memset得到的结果会是乱七八糟的十六进制值。很多人在第一次做图论题时用memset(dist, 1, sizeof(dist))意图把距离初始化为1，结果得到一个巨大的数，排查半天才发现问题。建议养成习惯：初始化0或-1用memset，初始化其它值用fill或循环。

4.3 复杂度预估：1秒到底能跑多少次计算

做例题时最值得养成的习惯，是在写代码前先估算最坏情况下基本操作次数。根据我自己的经验，1秒的时限内，简单的加减乘除、数组访问操作大约能承受10^7到10^8次。也就是说：

• 如果 N 是10^5，O(N^2) 的算法就是10^10，一定会超时；
• 如果 N 是10^3，O(N^2) 是10^6，很安全；
• 如果 N 是10^9，连 O(N) 都很危险，基本只能想 O(log N) 或 O(1) 的办法。

以小球下落为例，O(I * D) 的最坏情况约为2*10^7次操作，看起来勉强在边缘，但考虑到常数和在线评测的波动，它已经有超时风险；而 O(D) 的做法只有20次运算，这才是竞赛题期望的复杂度。这个对比表格我放在下面：

5. 三个调试工具：边界用例、暴力对拍和重读题面

5.1 别用小样例验证完就交，边界用例是隐藏杀手

紫书例题的样例输出往往很简单，样例过了只能说明程序没有语法错误。我自己的习惯是遇到“给定一个序列判断是否合法”这类型题，先构造以下三类边界用例：最小规模用例（n=1）、极端顺序用例（全部升序、全部降序）、以及最大规模用例（n等于上限）。

以铁轨为例，n=1时只有“1”一个目标序列是合法的，其它都是非法；全部升序时直接按顺序入栈出栈，显然合法；全部降序时，比如n=3的“3 2 1”，合法原因是要先把123全部压入栈，再依次弹出。这些用例能在两分钟内检验出算法中最基本的逻辑分支是否漏掉。

5.2 对拍验证：用暴力程序当“标准答案”

对于规模较小的输入，暴力枚举往往能给出正确结果但速度差。这时候写一个简单的暴力程序作为“对拍器”，再写一个数据生成器产生小规模随机数据，对比两个程序的输出，就能高效定位逻辑错误。这个做法在竞赛圈里叫“对拍”，虽然很多初学者觉得额外写程序很麻烦，但这恰恰是排查复杂逻辑错误最快的方式，比盯代码盯半小时高效得多。我通常先把暴力程序打印输出和优化程序的结果逐行比较，一旦发现差异，再用文件流定位到最小能复现问题的数据上。

5.3 出错了先重读题面，再动代码

我见过太多选手在代码逻辑正确却 Wrong Answer 时，第一反应是怀疑自己的算法，反复修改核心逻辑，结果最后发现题目要求“每行输出后有一个空行”，而自己漏了；或者题目说“按字典序输出”，自己按输入顺序输出。这类低级失分完全可以通过“提交前重读一遍题面”避免。重点检查几个地方：多组数据的结束条件是什么；输出对空格、空行、大小写是否有特殊要求；数据范围里有没有提示说明某个量很大。这些细节经常藏在题面中间位置而不是开头，很容易被忽略。

最后分享一点我的个人体会

刷《算法竞赛入门经典》这本书，最忌讳的就是把例题答案当小说看——看懂一行，点点头，翻下一页。我第二遍刷的时候给自己定了一个规矩：看完例题答案后合上书，只凭理解重新实现一遍代码，如果写不出来或者写完和原答案差异很大，就说明这个“答案”还没有真正内化。铁轨那道题我前后写了七遍，每一遍都能发现不同的边界疏漏。算法竞赛不是比谁见过的题多，而是比谁在有限时间内能把见过的套路稳定复现出来。与其用同样的时间快速扫十道例题的答案，不如把一道题按“自行尝试、对照答案、隔天复现”三步走完，这样留下的记忆和代码手感会牢固得多。希望这份拆解能帮你把这本书“吃”得更透。

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