HDOJ刷题全攻略：从EOF多组输入到算法优化，避开在线评测常见错误

1. 为什么课程例题要搬到HDOJ上重做一遍

1.1 本地能跑通的代码，提交上去却不一定对

这学期上算法课，老师把作业挂在了HDOJ上。第一节课我还有点怀疑：题目在教材上明明已经给了完整代码，上课也听懂了思路，为什么非得跑到一个评测系统上重新提交一遍？本地Dev-C++能跑出正确答案不好吗？

后来交了几道题才明白，HDOJ这类在线评测系统做的事情，和本地调试完全是两码事。本地环境里你面对的是自己设计的几组样例，输入数据怎么来，输出格式怎么打，全凭你高兴；而评测系统里，你的程序要面对的是很多组你根本看不见的测试数据，包括边界输入、极端数值、空行、多组数据连续输入这些情况。任何一处没考虑到位，回报你的就是Wrong Answer或者Runtime Error。课程例题看起来简单，背后考察的恰恰是“把思路翻译成严格程序”的能力。

也就是说，HDOJ的课程例题不是让你背答案，而是逼着你去处理那些课堂上不会细讲的细节：多组输入怎么读、数组开多大、空格换行打在哪个位置、循环终止条件到底怎么写。这些细节，才是真正容易被扣分的地方。

1.2 判题系统到底在“判”什么

理解HDOJ的判题机制，是刷课程例题的第一课。你的程序提交以后，系统会拿隐藏的测试数据去跑你的代码，然后对比你的输出和标准答案。对比是逐字节进行的，多一个空格少一个换行都不行，这类错误专门有个名字叫Presentation Error，通俗点说就是“格式错误”。

另一个经常被忽略的机制是时间限制和内存限制。HDOJ很多题目会限时1秒或2秒，内存限制在32MB到128MB不等。也就是说，一个算法如果复杂度太高，即使结果正确也会被判为Time Limit Exceeded。这一点与本地跑完全不同——本地你跑个几秒没人在意，评测机上慢一点就是超时。

所以，把HDOJ的课程例题当作一个“最小可运行的战场”来看，心态就对了：你不仅要把题做出来，还要把程序写得严谨、高效、经得起各种输入的考验。这一套标准下来，才是刷这些例题的真正价值。把课程例题在HDOJ上重做一遍，相当于给每个知识点做一次“极限测试”。

2. 从A+B开始的AC之路：多组输入和EOF，别栽在第一步

2.1 HDOJ 1000题教给我的第一课

几乎每个人在HDOJ上的第一道题都是1000号A+B Problem。题目简单到不能再简单：输入两个整数，输出它们的和。但就是这道题，第一次提交就有一大批人卡住。原因不是不会加法，而是不知道“多组输入”要怎么写。

看题目描述，HDOJ 1000的输入要求是“Process to end of file”，翻译过来就是要一直读到文件结束。这意味着程序不能只读一组数据然后退出，而要循环读入，直到没有数据为止。我第一次写的是这种代码：

#include <stdio.h> int main() { int a, b; scanf("%d %d", &a, &b); printf("%d\n", a + b); return 0; }

在本地跑，输入“1 2”输出“3”，感觉完全没问题。提交上去，直接Wrong Answer。为什么？因为评测数据不止一组，程序只处理了第一组就结束了，后面的输入数据根本没有被读取，输出自然对不上。

正确的写法是借助scanf的返回值。scanf在读不到数据时返回EOF（文件结束标志），所以可以写成：

#include <stdio.h> int main() { int a, b; while (scanf("%d %d", &a, &b) != EOF) { printf("%d\n", a + b); } return 0; }

关键点在于scanf的返回值：它返回的是成功读取的变量个数，读不到任何东西则返回EOF。用!= EOF作为循环条件，就能实现“一直读，读到没有为止”。这就是HDOJ课程例题里最基础、也最常用到的套路。

2.2 EOF写法的两种变体，建议都掌握

同样的思路，C++里可以写成：

#include <iostream> using namespace std; int main() { int a, b; while (cin >> a >> b) { cout << a + b << endl; } return 0; }

cin >> a >> b这个表达式，在成功读取时返回流对象本身，隐式转换成布尔值就是真；读到文件结束则返回假。所以while (cin >> a >> b)是最常见的C++多组输入写法。

还有一类题目输入格式是“第一个整数T表示后面有几组测试数据”，比如第一行输入3，代表后面还有3组数据。这种写法不一样，得先把T读进来，再循环T次：

#include <stdio.h> int main() { int T, a, b; scanf("%d", &T); while (T--) { scanf("%d %d", &a, &b); printf("%d\n", a + b); } return 0; }

这两种输入模式在HDOJ课程例题里反复出现。看到“多组输入”四个字就用EOF写法，看到“第一行为T”或“有T组测试数据”就用计数器循环。我见过太多人在这两种模式上搞混，导致交上去明明本地样例都对，最后还是判错。

提示：判断输入模式的方法很简单——看题目样例。如果样例里只给了一组输入输出，但题干写了“多组输入”，几乎可以确定要用EOF循环。如果样例第一行是个单独的数字，基本就是T组数据的模式。

2.3 大数加法：样例过了，PE却来了

做完1000题之后，很多课程会紧接着安排HDOJ 1002大数加法。这题对于刚学完C语言数组的同学来说是个坎。题目要求计算两个超大整数的加法，超出long long范围，只能把数字当字符串读进来，按位从最低位开始加，处理进位关系。

思路其实不难，但真正让人崩溃的是输出格式。题目要求每两行输出之间空一行，最后一组数据末尾不能有多余空行。这就触发了前面提到的Presentation Error。我那次提交，算法逻辑完全正确，结果还是PE，一看原因就是多打了空行。

解决办法是控制输出的结构：判断是不是最后一组数据，如果不是，在输出完本组结果后打一个空行；如果是最后一组，只换行不再多空一行。这个“控制输出结构”的意识，会成为之后做所有HDOJ题目的通用技能。课程例题在格式上卡人，不是刁难，而是在强调“严格按照要求输出”本身就是程序正确性的重要部分。

3. WA、RE还是PE？一次完整的问题排查链路

3.1 把各种评测结果先认全

HDOJ的评测结果里有几种最常见的情况，我一开始只知道Wrong Answer，后来才发现每种错误背后的含义完全不同：

把这张表记熟之后，面对一个红色提示就不慌了，至少知道往哪个方向排查。初学者最怕的是看到Wrong Answer就开始瞎改，一会儿改格式一会儿改算法，最后越改越乱。

3.2 数组越界的典型排查过程

有一道题我印象特别深，题目要求读入n个整数，倒序输出。我写的程序在本地测了5组数据全部正常，可一提交就Runtime Error。当时完全不知道错在哪。

后来按流程排查：第一步检查数组定义大小，我写的是int a[n]，而HDOJ的编译器对变长数组支持不算友好，而且n的范围在题目里最大是10000。我改成了int a[10005]，比最大值多留一点余量。第二步检查循环条件，我的代码是：

for (int i = n; i > 0; i--) { printf("%d\n", a[i]); }

这里就出问题了。数组下标从0开始，最后一个元素是a[n-1]，而不是a[n]。当i等于n时，访问的是数组越界位置，本地可能碰巧读到了内存里的随机值，表现得“正常”，但在评测机上直接触发运行时错误。

改成for (int i = n - 1; i >= 0; i--)之后，提交就通过了。这次经历让我养成一个习惯：凡是涉及数组下标的地方，先在心里过一遍边界——最小值是什么，最大值是什么，会不会越界。特别是循环变量从1开始时，下标就要对应改成a[i-1]。

注意：本地跑的结果“看起来正常”很有欺骗性。数组越界是未定义行为，在本地可能没崩溃，跑到评测机上遇到不同的内存布局，问题就暴露了。排查Runtime Error时，第一条就是检查所有数组的下标范围。

3.3 Presentation Error是怎么排查的

PE这个错误特别折磨人，因为算法对了，逻辑对了，就是输出格式错了那么一点。我遇到的一个典型情况是打印金字塔图形，每一行前面的空格数少打了一个。本地样例里看着差不多，但评测系统比对的是每个字符，差一个空格就过不了。

排查PE的思路是：拿题目给的样例输出，和你的程序输出做逐字符对比。普通肉眼看不出差别，可以把输出重定向到文件里，再用十六进制查看空格和换行。通常问题出在三种地方：行尾多余空格、行间空行数量不对、每行数据之间用错分隔符。

后来我学到一个通用技巧：把printf和cout里的每个空格、换行都当作一个独立字符来检查。题目要求“两个数字之间用一个空格分隔”，你的代码里千万别打印两个空格或者用逗号。要求“每组输出后跟一个空行”，你就老老实实看最后一组数据后面到底需不需要额外空行。多留意这些细节，PE就能大幅减少。

4. 从TLE说起：课程例题里的算法优化实战

4.1 暴力能过多少分，取决于数据范围

算法课上老师讲复杂度分析的时候，很多同学觉得抽象：O(n²)和O(n log n)到底差多少？HDOJ用Time Limit Exceeded给了最直观的答案。

有一道题是判断一个数是否为素数，数据范围是n <= 1000000。第一次我写的是从2循环到n/2逐个取余，简单粗暴。本地测试几组数据都很快，交上去直接超时。计算一下就知道了：当n等于1000000时，循环要跑50万次，如果测试数据有几十组，总运算次数轻松破千万甚至上亿。1秒的时间限制根本扛不住。

正确的做法是只检查到平方根。一个合数必定有一个小于等于平方根的因子，所以判断素数只需要从2循环到sqrt(n)：

#include <stdio.h> #include <math.h> int is_prime(int n) { if (n < 2) return 0; for (int i = 2; i * i <= n; i++) { if (n % i == 0) return 0; } return 1; }

这里用i * i <= n代替i <= sqrt(n)，是因为浮点运算有精度误差，而且乘法比开方快得多。就这么一个改动，复杂度从O(n)降到了O(sqrt(n))，超时问题就解决了。

4.2 预处理：把重复计算挪到程序启动之前

课堂例题里还有一类题目让我真正理解了“预处理”的价值。比如要计算多组输入里每个数的阶乘或者斐波那契数列值，如果每组数据都从头算一遍，重复劳动太大。HDOJ 2041超级楼梯那道题就是典型的例子：每次输入一个n，要求输出走法数，而走法数正好对应斐波那契数列。

如果写成递归：

int fib(int n) { if (n <= 2) return 1; return fib(n - 1) + fib(n - 2); }

看上去简洁，但n稍微大一点，重复计算伴随着递归调用成倍增长，TLE几乎是必然的。改进的办法是递推，把每一项都存进数组：

int f[45]; void init() { f[1] = 1; f[2] = 1; for (int i = 3; i < 45; i++) { f[i] = f[i - 1] + f[i - 2]; } }

程序一开始就调用init()把前45项算好，后面每组输入直接查表输出，时间消耗几乎为零。这就是预处理的核心思想：把可能重复用到的计算结果提前准备好，时间换空间的思路反过来用，用一点内存换大量时间。HDOJ上很多题目只要把预处理加进去，超时问题直接消失。

4.3 剪枝和记忆化：两道典型题的取舍

有一类题目，看起来必然要搜索枚举所有情况，但直接搜会超时，这时候就要想剪枝。我做过一道HDOJ上的数字排列题，要求从n个数里选m个，输出所有排列。初版代码生成所有全排列然后筛选，n稍微大一点就爆了。后来改成在递归过程中判断当前前缀是否满足条件，不满足就直接return，少走了大量分支。

另外一类常见情况是递归函数存在大量重叠子问题，斐波那契数列的递归就是典型。除了递推，还可以用记忆化搜索：用一个数组记录已经计算过的结果，递归时先查表，计算过就直接返回。

long long memo[50]; long long fib(int n) { if (n <= 2) return 1; if (memo[n] != -1) return memo[n]; memo[n] = fib(n - 1) + fib(n - 2); return memo[n]; }

初始化memo数组全为-1，每次递归前先看有没有算过。这样递归树就从指数级缩减成了线性级，算完第n项只需要O(n)的时间。剪枝和记忆化，本质上都是“减少无效计算”，它们是程序从“正确但慢”走向“又快又对”的关键手段，也是算法课程例题里最值得在OJ上反复磨炼的部分。

5. 如何整理HDOJ课程例题记录，让它变成可复用题库

5.1 一题一档：从AC代码到踩坑笔记

刷过的HDOJ例题如果只是堆在提交列表里，过一段时间就忘了自己当时是怎么想出来的、卡在哪里。我自己的做法是为每道题建立一个记录条目，核心是以下几个字段：

比如HDOJ 1002大数加法，我的记录里写着：“字符串读入，从低位逐位相加，用int变量保存进位，最后去掉前导0输出。注意输出格式：组间空行、末尾无多余空行。”

这样一条记录，在期末复习或参加竞赛集训时特别有用。看到题号和知识点就能快速回忆起这道题的解法，不需要重新翻提交记录。

5.2 错题是真正的老师：标记和重做的价值

我有个习惯：凡是第一次提交没通过的题，统一打上一个“WA重做”标记。几个星期之后，从标记过的题目里抽几道重新写一遍，完全不看原来的代码。

这一步作用很大。一道题你当时AC了，不代表你真正掌握了。两周后再写一次，如果还能独立通过，说明思路真的进入长期记忆了。如果卡住了，那就得翻出当时的记录，看看当初是怎么解决的。这种“间隔重做”比连续刷十道新题更有用，它逼着你把短期记忆转化成真正会用的能力。

重做时我还会刻意换一种写法。比如第一次用C写的，重做时改用C++的STL；第一次用递归写的，重做时逼自己用递推。这样做不是为了炫技，而是把同一道题当多个训练场景用，对同一知识点的理解会更深。毕竟HDOJ课程例题本身的价值不只在“AC”，更在于例题背后的思考方式能否迁移到新题目上。

5.3 把例题按知识点归组，形成自己的刷题地图

最后一步，也是我比较推荐的做法：把做过的HDOJ课程例题按知识点分组。我自己的分组清单大概是这样的：

• 基础输入输出：1000、1001、2000
• 模拟与简单字符串处理：1002、1003、1004
• 排序与查找：1106、1040、2017
• 数学与数论：2012、2031、2138
• 递推与动态规划：2041、2044、2084
• 搜索与图论基础：1180、1010、1312

整理完之后，你会发现自己对“课程讲到了哪些算法”“这些算法常以什么题型出现”有了整体认识。做题不再是零散地一道接一道，而是形成一个知识网络。这个网络在考试和后续刷题时能帮你快速定位：看到题目描述，就能大致猜出该用到哪一类算法，HDOJ例题的积累，就在这个过程中真正转化成了解题直觉。