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. 从AB开始的AC之路多组输入和EOF别栽在第一步2.1 HDOJ 1000题教给我的第一课几乎每个人在HDOJ上的第一道题都是1000号AB 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后来才发现每种错误背后的含义完全不同判断结果含义通常原因Accepted程序通过无Wrong Answer输出和标准答案不一致思路错误、边界没考虑、多组输入没处理Presentation Error输出内容对但格式不对空格、换行、空行的位置或数量不对Runtime Error程序运行中崩溃数组越界、除零、栈溢出、指针非法访问Time Limit Exceeded程序超时算法复杂度过高、死循环Memory Limit Exceeded超出内存限制数组开太大、动态分配未释放Compile Error编译失败语法错误、选了错误的语言提交把这张表记熟之后面对一个红色提示就不慌了至少知道往哪个方向排查。初学者最怕的是看到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 1000 AB Problem考察知识点多组输入、大数加法、素数筛等解题思路用一两句话描述核心算法关键代码片段不是整段代码而是最核心的几行踩坑记录当时的错误结果和原因复杂度分析时间复杂度和空间复杂度比如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例题的积累就在这个过程中真正转化成了解题直觉。
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. 从AB开始的AC之路多组输入和EOF别栽在第一步2.1 HDOJ 1000题教给我的第一课几乎每个人在HDOJ上的第一道题都是1000号AB 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后来才发现每种错误背后的含义完全不同判断结果含义通常原因Accepted程序通过无Wrong Answer输出和标准答案不一致思路错误、边界没考虑、多组输入没处理Presentation Error输出内容对但格式不对空格、换行、空行的位置或数量不对Runtime Error程序运行中崩溃数组越界、除零、栈溢出、指针非法访问Time Limit Exceeded程序超时算法复杂度过高、死循环Memory Limit Exceeded超出内存限制数组开太大、动态分配未释放Compile Error编译失败语法错误、选了错误的语言提交把这张表记熟之后面对一个红色提示就不慌了至少知道往哪个方向排查。初学者最怕的是看到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 1000 AB Problem考察知识点多组输入、大数加法、素数筛等解题思路用一两句话描述核心算法关键代码片段不是整段代码而是最核心的几行踩坑记录当时的错误结果和原因复杂度分析时间复杂度和空间复杂度比如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例题的积累就在这个过程中真正转化成了解题直觉。
