前几天晚上我把学校 OJDHUOJ基础区的 40、41、42 三道题连续刷完了。说实话这三题题面都很短没有图论、没有动态规划也没有复杂的数据结构属于典型的“基础题”。但真正提交之后我才发现踩坑的地方比我想象的多得多数组边界、字符串缓冲区、复杂度估算……一个都没少。如果你也在某个 OJ 上刚开始刷题或者正在被课程作业里的“水题”反复折磨这篇复盘应该能帮你少走不少弯路。先说结论基础题练的并不是“我会写循环”而是“能不能把代码写得足够精确”。下面我会从拆题思路、环境准备、逐题复盘到提交排错完整过一遍。1. 先拆题基础 40、41、42 到底在考什么1.1 为什么这类“一眼就会”的题反而值得认真复盘在 OJ 上做题和在自己电脑上写 Demo 完全是两回事。自己写代码只要运行结果“看起来对”就可以收工但 OJ 的评测器是一个只看输入输出的黑盒它不关心你的代码里写了多少注释、逻辑多优雅它只在乎一件事给定的输入数据你是否输出了完全一致的答案。哪怕多打一个空格、少打一个换行结果都是不通过。基础题表面上考查的是“会不会写循环”“会不会处理数组”但本质上是在训练一种精确实现的能力。一个平时写代码习惯比较随意的同学去写基础题很容易出现“本地看着没问题交上去就 WA”的情况原因往往不是思路错误而是某个细节状态没有处理好。这类题更像是“代码习惯的体检报告”能够把你的坏毛病一次性暴露出来。所以我会建议每一个刚接触 OJ 的人不要急着跳过基础区先把这些题当成手术刀认认真真解剖自己写代码时那些不严谨的习惯。1.2 三道题的能力模型与考点分布不同的 OJ 上题号和题型一般不会完全一样但“基础区”里的题目类型其实高度固定。以 DHUOJ 的 40、41、42 为例我这边对应的三道题原型分别是题号典型题面原型核心考点最容易出错的地方40输入 n 个整数求最大值与最小值的差循环、数组、边界处理初始化选错、数组越界、n 为极端值41输入 n 行字符串统计元音字母个数字符串读入与字符处理缓冲区残留换行、中英文符号混淆42判断给定整数是否为素数复杂度分析、数论基础暴力循环超时、乘法溢出看懂这个表格你会发现这三道题并不是随便排在一起的。40 训练数组与循环的“边界敏感度”41 训练字符串读入的“状态意识”42 训练算法设计的“成本思维”。三者恰好覆盖了入门阶段最核心的三个能力短板。接下来我就按这个顺序把每一题的完整做题过程、代码、坑点拆开来逐一细说。2. 动手之前评测规则与本地调试环境2.1 先弄懂 OJ 到底用什么标准在盯着你很多新人第一次提交看到 OJ 返回一个红红的 WA第一反应是“我代码不是对的吗”。这多半是因为你还没理解 OJ 的评测结果分类。这里我先列一张最常用的状态速查表后面排错全靠它评测状态中文含义大概原因AC答案正确恭喜这道题已经过了WA答案错误程序能跑但输出和标准答案不一致TLE超时程序运行时间超过了题目限制MLE超内存程序占用的内存超过了题目限制RE运行时错误比如数组越界、除数为 0、递归爆栈PE格式错误输出内容对但多/少了空格或换行CE编译错误代码在评测机的编译器环境下无法通过PE 是新手特别容易忽略的一种状态。比如样例要求输出两个数字之间用一个空格隔开你在数字后面多输了一个空格机器读入后结果数值其实是对的但因为字符层面不一致就会返回 PE。有的 OJ 会把 PE 直接当作 WA 处理所以基础题里格式问题必须养成肌肉记忆输出最后要有换行行内空格不多不少行末不要画蛇添足。2.2 本地环境准备重定向输入别再手动复制用例做题之前我会先做一件特别省时间的小事用输入重定向把测试用例从文件读入。这样就不需要每次运行程序时都手动往终端里敲数据尤其是刷到第 41、42 题这种有多组输入的题目时效率会高很多。以 C 语言为例典型的写法是在 main 函数开头加上一行#include stdio.h int main() { // 本地调试时打开下一行 // freopen(test.in, r, stdin); int n; scanf(%d, n); // ... return 0; }在本地调试时把test.in和你的源代码放在同一个目录然后运行程序它就会直接读文件里的内容。提交 OJ 之前记得把freopen这一行注释掉或者删掉不然评测机会尝试打开一个不存在的文件最后大概率 RE。如果你习惯用 Python也可以把sys.stdin open(test.in, r)放在脚本顶部效果一样。核心思路就是本地测多组数据的时候不要一遍一遍地手动输入手动输入不仅慢还容易输错反而浪费时间。3. 第 40 题边界和初始化才是真正的考点3.1 先把题意还原成输入输出模型我们这边的第 40 题题面大致是输入一个整数 n然后输入 n 个整数输出这 n 个数中最大值与最小值的差。第一眼看上去确实没什么可说的一个循环就能搞定。但这种题最容易栽的地方不是循环本身而是“初始值怎么给”。简单拆一下输入输出模型输入第一行 n第二行 n 个整数输出一个整数表示 max - min如果 n 等于 1那么最大值和最小值是同一个数差值就是 0。这个样例非常小但恰恰能把很多人的初始化问题暴露出来。你可以先想一想如果是你max 和 min 的初始值会设为多少3.2 两个让新手崩溃的细节第一个细节是最大值和最小值的初始化。最稳妥的做法不是把 max 设成0把 min 设成一个很大的数因为数据可能有负数、有正数如果数据范围没有提前告诉你你默认的初始值就有可能比所有数据都更“极端”。我自己常用的做法有两种先读第一个数把它同时赋给 max 和 min然后再循环读取剩下的 n-1 个数。或者用头文件里的INT_MIN和INT_MAX来初始化 max 和 min。第二种需要一个前提你知道数据的取值范围没有超过 int。如果题目输入是int范围内的整数那INT_MIN和INT_MAX是绝对安全的。第一种做法更“无脑”因为它不需要额外依赖任何宏也不需要关心数据范围读完一个就有的放矢。我推荐新手习惯第一种写法能少想很多边界问题。第二个细节是循环边界的写法。很多人会下意识写成for (int i 0; i n; i)然后数组也从 0 开始存这当然没问题。但如果你用的是“先读第一个再循环 n-1 次”的思路就要注意循环条件到底是i n - 1还是i n写错一个位置要么少读一个数要么数组越界。数组越界不会每次都被评测系统抓到它导致的问题是未知的有时是 WA有时是 RE有时本地运行一切正常。这就是最玄学的地方。3.3 参考实现与实测踩坑记录给一个最朴素的 C 语言参考#include stdio.h int main() { int n; scanf(%d, n); int x; scanf(%d, x); int max x, min x; for (int i 1; i n; i) { scanf(%d, x); if (x max) max x; if (x min) min x; } printf(%d\n, max - min); return 0; }这个版本假设了 n 一定大于等于 1。如果题目里没有明确说 n 的范围你最好再用 if 判断一下 n 为 0 或者输入失败的情况避免自己给自己挖坑。我复盘这道题时记录过三次失败第一次max 初始化成 0min 初始化成 99999结果数据里全是负数差值算错WA。第二次把scanf(%d, n);的返回值忽略掉后来数据换到文件重定向输入时格式不对程序直接把上一次残留值当成输入输出结果全乱。第三次本地测试用了多组样例但程序只处理了一组就退出还以为自己没写错。这三个问题其实都特别基础但我相信每个刷 OJ 的人都多多少少遇到过类似的情况。第 40 题的意义就在于它逼着你把这些基础问题彻底想清楚。4. 第 41 题字符串的读入比处理更坑4.1 缓冲区里那个换行字符能毁掉一次提交第 41 题我这边是统计一行字符串里元音字母的数量。题面大概是输入一个正整数 n接下来有 n 行字符串每行可能包含空格要求输出每行中 a、e、i、o、u 五个小写元音字母出现的总次数。听到“可能包含空格”很多人第一反应是用scanf(%s, str)读入。但scanf按%s读字符串时遇到空格就会停下导致“hello world”只读到“hello”后面的“world”完全被漏掉。这种题目真正考察的能力点是字符串读入方式的选择。更隐蔽的一个坑出现在 “先读整数、再读字符串” 的组合场景里。输入格式是2 apple this is a book你用scanf(%d, n);读入 2 之后输入缓冲区里其实还残留着一个换行符\n。如果你紧接着用gets(str)或者某些带空格读入的函数程序会先把这个换行符当成一行空字符串读走然后真正的字符串全被错位。这种问题本地跑的时候特别迷惑因为你自己敲测试数据时可能不会注意到缓冲区里的细节但评测机是按文件输入来读的每一步都清清楚楚。最简单的解决办法用getchar()在读完 n 之后吃掉那个换行符。注意是只吃一个字符因为输入格式里数据之间没有多余空格时残留的就是\n。如果你不确定中间有没有可能多出空格更稳的方案是统一用fgets读整行然后在程序里再去掉末尾的换行符这样永远不依赖缓冲区的“运气”。4.2 参考实现与处理细节给一个利用fgets的 C 语言版本#include stdio.h #include string.h int main() { int n; scanf(%d, n); getchar(); // 吃掉换行 char line[200]; for (int i 0; i n; i) { fgets(line, sizeof(line), stdin); int cnt 0; for (int j 0; line[j] ! \0; j) { if (line[j] a || line[j] e || line[j] i || line[j] o || line[j] u) { cnt; } } printf(%d\n, cnt); } return 0; }这里有个常见误区fgets会把行末的换行符一并读进line数组比如输入 “apple\n”数组里存的是apple\n\0。不过因为统计逻辑只关心字符是不是元音\n并不会影响结果所以这个版本不主动去掉换行也是能通过的。但如果题目接下来要对字符串做精确比较、反转或者拼接你就必须记得把末尾那个换行符替换成\0。顺便说一句有些旧教材喜欢用gets但gets在评测机的编译环境里往往会有安全警告而且它没有任何长度限制强烈不建议继续用。统一换成fgets控制好目标数组大小是更安全的读行姿势。4.3 本地输出正确、提交却 WA 的排查顺序这道题让我印象最深的一次是本地怎么测都对一交上去就 WA。后来排查了半天发现是我用scanf读完了n但没吃掉换行符导致第一组字符串读成空行整个输出全部错位。这种问题很难靠“盯代码”看出来因为你本地测试时可能用的不是同一种输入方式或者你下意识多做了一步操作把问题掩盖了。之后我就沉淀了一个固定排查顺序先看读入。题目里有没有可能包含空格的字符串整数和字符串之间是否连续读入再看格式。输出有没有多一个换行每行之间是否应该空行最后看字符集。统计的到底是小写元音还是大小写都算题目如果只说“元音”你最好把大写情况也考虑进去很多字符串题都会在这里埋雷。第 41 题做完之后我对“输入状态”有了完全不同的理解程序每次调用读入函数都是在一片缓冲区上操作它记住的不仅是“读到了什么”还有“上一次读到了哪里”。理解了这一点这道题的价值就已经拿到手了。5. 第 42 题从模拟到数学就差一次复杂度分析5.1 如果只想着“暴力判断”TLE 只是时间问题第 42 题我这边是素数判定输入若干个整数对每个数判断它是否为质数。有一个限制是单个数可能达到 10^9。这个数据量出来的时候如果你还在按“从 2 循环到 n-1看看有没有能整除的数”的思路写代码那么恭喜你后面几组数据大概率直接 TLE。为什么假设有 100 个测试数据每个数都是 10^9 量级暴力判断从 2 试到 n最坏情况下要做差不多 10^11 次取模运算。普通 OJ 的时间限制通常是 1 到 2 秒别说 10^11 次了10^8 次运算都已经处于极限边缘被卡超时是一点都不奇怪。这种题真正想训练的是复杂度意识。你拿到题面应该先估算一下“最坏情况输入”是什么再算一下自己的算法在最坏情况下的运算次数最后和题目限制对比。一旦发现数量级对不上就该换思路。5.2 素数判定模板与两个特判判断一个数 n 是否为素数最基本的一点是只需要试除到 sqrt(n) 就行。因为如果 n 能被某个大于 sqrt(n) 的数整除那么一定存在一个小于等于 sqrt(n) 的因子。这个性质能把 10^9 的试除范围缩小到大约 31623 次100 个数也就是 300 多万次完全可以在时限内跑完。一个不容易踩坑的 C 语言写法是这样#include stdio.h int is_prime(long long n) { if (n 2) return 0; for (long long i 2; i n / i; i) { if (n % i 0) return 0; } return 1; } int main() { int t; scanf(%d, t); while (t--) { long long x; scanf(%lld, x); puts(is_prime(x) ? Yes : No); } return 0; }这里有两个细节值得单独拿出来讲n 2需要特判因为 1 不是质数0 和负数也不是质数。很多人写循环时默认了 n 是正数结果输入里混入一个 1整个输出就错位。循环条件写成i n / i而不是i * i n。原因是 i 接近 sqrt(n) 时i * i可能会超过int或long long的安全范围造成溢出。虽然这里 i 最大值也就 31623i * i完全不会溢出但把这种写法变成习惯等以后处理更大数据的时候就能少踩一个隐蔽的坑。5.3 溢出问题坚持用 long long 更省心第 42 题的数据虽然还在 int 范围内但读取和判断我还是建议全部用long long。原因很简单素数判定里不可避免要做乘法或者除法中间结果有可能超过 int 范围。用long long可以让你不用时刻担心“这里会不会溢出”这个问题把注意力集中在算法本身。取模运算的代价其实比想象中要高。如果用暴力试除法最坏情况下的取模次数是 10^11 次量级时间根本扛不住。而用sqrt(n)优化之后单次判断的运算量降到 3 万次左右两者差了六个数量级。这就是“模拟”和“算法”的区别模拟是在硬算算法是在找规律、降复杂度。很多基础题看起来是模拟题其实都在逼你从数学层面重新思考一遍。5.4 实测效果本地怎么判断会不会超时我刷这道题的时候特意在本地验证了一下时间。用一个循环生成了 100 个接近 10^9 的随机数分别跑暴力版和优化版暴力版跑了很久才停下来优化版几乎是瞬间出结果。这种差距不需要专业的性能分析工具自己的直觉就能感受得到。所以当你拿到一道题觉得“可以用暴力做”的时候我强烈建议你先花十秒钟做一次估算最坏情况下输入规模是多少程序最多会被要求处理多少个数每个数最多需要多少步如果总数超过千万级别解法大概率需要优化。第 42 题教会我的就是这种“动手前先算账”的思维方式。6. 提交之后评测结果排查与本地对拍6.1 先列一张问题速查表刷完三题之后我把提交过程里遇到的状态全部整理成了一张速查表后面再刷题遇到类似问题直接对照着查效率高很多症状可能原因排查手段输出内容对但被报 WA/PE多空格、少空格、行末多空行仔细读样例输出用文本对比工具检查第一组数据对后面全错多组数据之间状态没重置检查变量是否在循环内初始化本地正常提交后 RE数组越界、除零、文件操作把数组开大一点检查分母为 0 的分支时间卡得很死的 TLE算法复杂度太高死循环重新估算数据规模考虑优化算法编译不过跟评测机编译器版本不一致避免用新特性关闭本地特有头文件这张表不神但它能把玄学问题变成工程问题。你可能不需要成为算法大牛也能靠有条理的排查一步步接近正确解法。6.2 一个百试不爽的本地对拍思路如果你已经卡在某个问题上很长时间怎么自查都发现不了 bug那就试试“对拍”。思路非常简单写一个保证正确但可能很慢的暴力程序再写一个你觉得应该正确的高效程序然后生成大量随机小数据让两个程序都跑一遍比较输出是否完全一致。一旦不一致就说明高效程序里有一个你没发现的逻辑漏洞。在 Linux 环境或者 git-bash 里可以用一个很简单的脚本完成这件事for i in $(seq 1 1000); do ./generate input.txt ./brute input.txt brute_out.txt ./fast input.txt fast_out.txt diff brute_out.txt fast_out.txt || break donegenerate是一个自动生成随机数据的程序brute是暴力版fast是要检验的版本。只要diff输出不一致并且脚本被 break 掉你就能拿到一组让程序出错的最小输入样例。这个办法对第 40、41、42 题可能有点“杀鸡用牛刀”但对后面真正复杂的题目它是调试利器。6.3 提交前的 3 分钟自检清单以我自己的习惯每次提交前都会按顺序快速过一遍下面五件事样例能不能过不仅过样例还要想一个自己构造的极端样例。变量初始化对不对尤其是有多组数据时上一组的残留状态有没有被清掉。输出格式是否和题目完全一致包括最后一行有没有换行。类型够不够大有没有可能在中间步骤溢出。本地调试用的freopen、文件读写那几行注释掉没有。这五件事花不了三分钟但能把八成以上的低级错误挡在提交之前。刷 OJ 是个熟练活提交次数多不代表水平高能一次 AC 才说明你真的把问题想清楚了。7. 刷完这三题下一步练什么更划算7.1 基础区之后怎么选40、41、42 这三题如果都能顺利通过说明你已经具备了最基本的循环控制能力、字符串处理能力和复杂度估算意识。下一步不建议直接去啃难题而是应该按顺序补上几个高频基础模块排序算法冒泡、选择、快排、二分查找、前缀和与差分、简单的递归和递推然后是基本栈和队列的应用。这些模块之所以值得优先练是因为它们几乎是后面所有题型的“地基”。拿前缀和来说如果 40 题里只求一个最大值最小值那确实用不上但一旦题目扩展成“求某个区间内所有数的和”并且反复查询前缀和能把单次查询从 O(n) 降到 O(1)。这个思路就是从“模拟每次求和”变成“预处理一次、多次复用”本质和第 42 题的复杂度意识是一样的。7.2 这些经验如何反哺课程作业与竞赛很多人觉得 OJ 刷题和课程作业是两回事其实不然。课程作业里最常见的场景是“读取多行数据做统计然后格式化输出”。如果你没有经过 41 题这种“字符串读入”的毒打第一次做课设时很容易在缓冲区上浪费一整天如果你没有 42 题这种复杂度意识写出来的程序也许跑小数据没问题一上真实数据就直接卡死。竞赛更不用多说基础题的稳定性决定了你在正式比赛里能不能稳住心态。三题连刷的意义不在于这三道题本身而在于把一种“动手前先想清楚、提交前先检查完整”的工作方式内化成习惯。我见过很多同学题刷得很多但遇到问题依然靠猜反复修改反复提交最后靠运气 AC。真正有效的刷题方式是每一道题都榨干它的价值先理解题意再设计算法然后写代码最后复盘错误。这套流程走得越扎实后面遇到难题时的正反馈就越明显。最后分享一个小技巧每次 AC 之后把错误的提交记录和错误原因复制到自己的错题本里哪怕只是简单的几行文字。40、41、42 这三题我刷完后最珍贵的产出其实不是那三个 AC而是一份写满了“边界、缓冲区、复杂度”的踩坑记录。以后每次刷题前翻一翻就像有人在你耳边提醒一句别再栽在同一个坑里。
