如果说刷OJOnline Judge在线判题系统最容易让人心态崩溃的节点我投票给第19题。前十几题基本都是ab这类热身题提交上去闭眼AC自信心膨胀得不行。但刷到第19到21题这个区间题目开始变着花样折腾你多组输入、字符串边界、数学特判稍不留神就是一个Wrong Answer。更气人的是本地编译器跑得好好的一交上去就错改来改去也找不到原因。这篇文章就是围绕这个阶段写的我想拆一拆OJ刷题从第19题到第21题这段普遍遇到的坎儿讲讲判题机制到底怎么回事、常见报错怎么排查顺便聊聊我试过的几个OJ平台HDU OJ、郑州轻工业大学OJ、东方博宜OJ这类的差异。不管你是刚开始刷题的大学生还是准备找实习想刷点算法基础的只要卡在这个区间这篇文章应该能帮你少走不少弯路。这个阶段的人有一个共同特点已经不是完全不会写代码的新手但又没过会做题的坎。说白了代码语法都认识但一碰到OJ的判题规则就懵。别急下面我按实际刷题的顺序从原理到实操一步步讲。1. 从19-21题说起入门阶段的真实处境1.1 为什么卡在19题的人最多我当年刷HDU OJ时前18题几乎全是送分题很多就是求个和、比个大小、算个阶乘题目描述里连拐弯都不打。但到了19题往后题目难度曲线突然陡了一下开始出现字符串处理、多组数据输入、格式要求严格的输出。很多人在这个区间第一次遇到Presentation ErrorPE也是第一次知道原来输出结果对和输出格式对是两回事。这类题目之所以容易劝退不是因为算法有多难而是因为考点从你会不会写代码变成了你能不能完整地理解题目规则。第19到21题恰好是这种转变的典型代表。我自己带过的几个学弟学妹几乎都在这个区间发出过灵魂拷问我明明本地运行样例完全一样凭什么判我错这种挫败感很容易让人放弃。把这个区间单独拿出来讲就是想说明你在这里卡住不代表你智商不够只是你还没习惯OJ的规则。一旦适应了后面再刷几十道题反而会轻松很多。1.2 这个阶段最容易出现的三个错觉第一个错觉是运行结果对就是对的。很多人写代码只看样例输出样例过了就提交结果WAWrong Answer得莫名其妙。OJ判题比对的是你程序在任意合法输入下的完整输出不只是题目给你看的那个样例。样例只是给你一个参考它覆盖不了所有边界情况。第二个错觉是本地跑通就万事大吉。本地编译器不会因为你数组开小了就报错也不会因为你少初始化一个变量就警告。很多时候代码在本地能跑只是因为内存里的脏数据碰巧没出问题换到OJ的评测环境就露馅了。我见过一个同学在本地跑第19题10组数据全部正确一交上去TLE原因是他数组开成了100000每次循环都从1遍历到100000实际题目数据范围只有1000白白超时。第三个错觉是不会做就是自己太菜。说实话能卡住人的往往不是算法本身而是没读懂题意。比如题目说输入以0结束你可千万别把0当成有效数据处理题目说每个结果后面跟一个空行那就不是空格而是空行。这些细节在题目描述里写得清清楚楚但新手习惯快速扫一眼就开写自然容易翻车。2. 在线判题系统是怎么判的机制决定策略2.1 从提交到ACOJ到底做了什么想搞明白为什么老错最好先搞清楚OJ的完整工作流程。你点下提交按钮后评测系统会做四件事编译你的代码、用预设的测试数据运行你的程序、捕获程序输出、和标准答案做比对。比对时绝大多数题目是逐字符精确匹配少数字符串或几何类题目会启用Special Judge只验证你的输出是否在合理范围内。所以OJ的判定结果其实就是在告诉你你这个程序在哪个环节出了问题。汇总一下常见结果判定结果含义最常见的诱因ACAccepted通过恭喜不用改了WAWrong Answer答案错误算法思路不对、边界值没处理、初始化遗漏PEPresentation Error格式错误多了空格、少了空行、输出末尾多了东西TLETime Limit Exceeded超时算法太慢、死循环、用了过慢的输入方式MLEMemory Limit Exceeded超内存数组开太大、递归层数过多RERuntime Error运行时错误数组越界、除零、野指针CECompile Error编译错误语法问题、选错语言标准我个人觉得新手最需要理解的是AC和WA之间的差距。OJ里面很多题目是一题多解只要输出正确就行不需要关心你用的方法是不是和答案一样。但前提是你必须在题目规定的时间限制和内存限制内跑完。也就是说OJ不光考你会不会还考你写得够不够快。2.2 输入输出格式新手翻车重灾区OJ题目和平时写单次运行的练习程序最大的区别就是输入输出格式。大多数题目都支持多组测试数据你的程序必须能循环读入直到输入结束。如果用C语言最常见的就是这样#include stdio.h int main() { int a, b; while (scanf(%d %d, a, b) ! EOF) { printf(%d\n, a b); } return 0; }这里scanf的返回值是成功读入的参数个数。读到文件末尾时它返回EOF循环就终止。如果你把while条件写成while (scanf(%d %d, a, b))在某些评测环境下最后一次读取失败时返回值可能是0循环会提前结束导致漏掉最后一组数据。这个问题在OJ上很经典我见过不少人在第20题这种计算并输出的题目上因为这里写错丢掉AC。如果是Java可以用while (in.hasNextInt())作为循环条件Python则是for line in sys.stdin。原理都一样读到流结束就停。输出格式的坑就更多了。常见的规则有每一行输出后要换行、多组结果之间要不要空行、行首行尾不能有多余空格。题目里如果写了每个测试用例的输出占一行或样例输出长什么样你就照着那个格式来多一个空格都可能变成PE。PE虽然不算错但也不会给AC必须重新提交。3. 三道代表性入门题的全过程拆解虽然不同平台上第19题、第20题、第21题的具体题目可能不一样但这类题目通常非常有代表性。我以最常见的三道题为例走一遍完整解题流程你看完就明白这个阶段该怎么思考了。3.1 第19题字符串处理的边界这类题目常见的形式是输入一行字符串要求统计单词个数、反转字符串或者判断回文。比如郑州轻工业大学OJ和杭电OJ的早期题目里都有一堆字符串题。它们共同的坑点有两个一是字符串怎么读才能读进空格二是数组开多大才够。先看读入。如果你用C的scanf(%s)遇到空格就会停根本读不了句子。要读一整行C里建议用fgets#include stdio.h #include string.h int main() { char s[1005]; while (fgets(s, sizeof(s), stdin) ! NULL) { // 去末尾换行符 int len strlen(s); if (s[len - 1] \n) s[len - 1] \0; printf(%s\n, s); } return 0; }这里有个细节fgets会把换行符一起读进来所以统计长度或输出时要注意。如果用Ccin.getline也有类似情况。Python则可以直接用strip()去掉换行。再说边界。字符串题最容易错的就是数组越界。很多题目字符串长度上限是1000但你在循环里写for (int i 0; i strlen(s); i)多出来的那个等于号就可能访问到结尾的空字符导致RE或逻辑混乱。我的习惯是数组长度在上限基础上加10遍历时明确用 len而不是用。3.2 第20题数学模拟的坑第20题最常见的类型是素数、最大公约数、进制转换、数列求和这几种。我拿素数判断举例因为这个题看起来简单实际错的人一堆。int is_prime(int n) { if (n 1) return 0; for (int i 2; i * i n; i) { if (n % i 0) return 0; } return 1; }第一坑1不是素数也不是合数n 1一定要返回假。第二坑循环边界是i * i n但这里的i最好用long long否则当n接近int上限时i * i会溢出。第三坑2是素数上面这个函数里2能正确返回真但有些写法是for (int i 2; i n; i)遇到n2时循环不执行直接返回1这没问题可就怕有人初始值写成i 1那所有数都会被1 % 1 0坑掉。数学题还有一个特点数据范围往往会逼你选对方法。比如让你判断1000000以内所有素数你要是每个数都从2除到sqrt(n)勉强也能过可要是让你判断100000000以内那个复杂度就危险了得考虑用筛法。这就是为什么刷OJ不能只看代码能不能跑还得估算时间。一般评测限时1秒代码的循环次数控制在千万级别以内比较稳妥超过一亿基本就TLE了。3.3 第21题多组数据与提前终止第21题常以输入以0结束或者第一行是N接下来是N组数据的形式出现。前者是典型的哨兵值控制循环后者是先读个数再循环。先看以0结束的写法#include stdio.h int main() { int n; while (scanf(%d, n) ! EOF n ! 0) { // 处理 n } return 0; }注意顺序scanf必须成功读入后再判断是否为0所以n ! 0放在第二个条件。如果写成while (n ! 0 scanf(...))n在第一次判断时还没被赋值行为未定义。这种细节在OJ上是真实发生过的别问我怎么知道的。第一行先读N的写法更简单但有个容易忽略的点N后面往往跟着N行数据如果你在前面用了scanf(%d)读N接下来第一行数据的换行符还在缓冲区里。此时如果你用getchar或gets读字符串可能会读到空串。解决办法是用scanf连续读或者读数据时跳过换行符。这个阶段练的就是这种输入输出流程控制的熟练度。说白了OJ里很多题目的算法可能只需要十行代码但前面的数据读入能把你绕晕半小时。4. 刷题报错排查从WA到AC的完整链路4.1 WA案例复盘我明明本地是好的我总结过自己WA的几百次经历大部分都能归到三句话里变量类型不对、初始位置不对、特殊情况没处理。类型不对最常见的是int溢出。比如求1到n的和n是100000和是5000050000int根本装不下必须用long long。OJ里的数据范围经常是这样卡着你的你不对着题目描述看光用int写样例小数据能过大数据就WA。初始化位置不对多发生在多组数据的题目里。很多人在主函数开头定义sum 0但放进while循环之后忘了每次重新赋值。结果第二组数据一进来sum还带着上一组残留的数值答案自然错。这属于最冤的一种WA。特殊情况没处理就是边界值。比如排序题里所有数相等怎么办再比如输出前导零的数位题9999和1000这种临界数。我一直以来的习惯是把样例改出几个变体自己测最大值、最小值、单元素、重复元素、空串。这套测试样例跑下来能过滤掉大部分WA风险。4.2 TLE与MLE效率是练出来的如果你刷题遇到TLE先别急着怀疑评测机卡大概率是你代码本身的复杂度超了。怎么估算看循环。如果你写了两层循环每层都跑到十万那总操作数就是百亿级别1秒内绝对跑不完必须换思路。我常用的优化手段有三个把cin/cout换成scanf/printf或者加上ios::sync_with_stdio(false);加速把重复计算提到循环外比如循环内部不必要的函数调用、重复的strlen调用换算法比如暴力枚举改成双指针、前缀和、二分查找MLE相对少见但一旦出现多半是数组开得太任性。有些题明明只用到100个数据非开成1000000的全局数组内存直接爆掉。还有递归深度过大的问题深度到几十万层时栈会溢出表现为RE而不是MLE但本质都是内存问题。4.3 PEOJ特有的洁癖PE是OJ特有的结果它的意思是你的答案内容全对但格式不对。常见原因有行尾多了一个空格、每行之间多了一个空行、少打了一个换行、输出的英文字母大小写和题目要求不一致。遇到PE解决的思路很简单把题目给的输出样例下载下来用diff命令或者文本编辑器的对比功能逐字节对比你的输出和标准输出。很多新手不知道这个操作所以我在这里多说一句在本地用文件重定向跑程序生成out.txt再和题目提供的sample_out.txt做比对任何多出来的空格、空行都能一眼看出来。提示写OJ题的时候输出末尾的换行通常可有可无但行与行之间的空行必须严格按题目要求。如果题目说每个样例后面输出一个空行那就需要在每组结果后额外printf(\n)。5. 不同OJ平台怎么选几家平台实测体验5.1 常见OJ的特点对比搜索热词里出现了很多OJ平台杭电OJ、郑州轻工业大学OJ、东方博宜OJ、杭师大OJ、华为OJ等。这些平台我大多注册过简单聊聊使用感受方便你选一个适合自己的。平台适合人群特点注意事项杭电OJHDU OJ算法竞赛入门到进阶题目全、经典题多、讨论区资料丰富全英文题面对英语有一定要求郑州轻工业大学OJ大一新生、校内课程中文题面多和课程贴合紧密部分题目需要校内账号游客可刷公开题东方博宜OJ编程初学者、中小学生中文、题目友好、题型分类清楚难度梯度较缓适合打基础杭师大OJ校内教学、课程实验题目和作业绑定有班级功能外校用户可能无法访问部分题目华为OJ求职笔试准备题目更贴近工程场景、字符串处理多部分平台已改名为华为OD机试题面较长我的建议是如果你刚开始接触OJ先找中文题面、难度梯度合理的平台比如东方博宜或者郑州轻工业大学OJ把输入输出这个基本功练熟。等你能稳定刷完50道入门题了再切到杭电OJ刷HDU 1000到1100这个区间感受一下经典竞赛题的风格。华为OJ这种偏求职风格的可以放到准备面试前再专门刷里面的题更综合不太适合纯新手。5.2 刷题路线从19-21题往后怎么走刷到第21题说明你已经过了连输入都不会写的时期。接下来我不建议继续按题号硬刷而是按主题刷。大致顺序是简单模拟和枚举10道字符串处理10道排序和查找10道贪心算法10道搜索DFS/BFS10道动态规划入门10道每一个主题刷的时候把AC的代码留档同时写一句话笔记记录这道题的坑在哪里。这条笔记比代码本身值钱得多。因为代码是固定的你的思维过程才是下次遇到同类问题的解题钥匙。我还想多说一个习惯不要死磕一道题超过一小时。如果你在一个题上卡了超过一个小时说明方向可能有问题这时候去讨论区看看别人怎么描述思路比继续钻牛角尖强。OJ的讨论区不是抄答案的地方是帮你打破思维定式的地方。我个人刷题的时候还有一个习惯每道题AC之后会把我的代码拿到本地去跑一些极端数据比如最大值、最小值、随机值确认它不是侥幸AC。因为OJ的测试数据往往覆盖不到所有情况可能你靠运气过了但换个数据就错。这个习惯帮我在后面的比赛里少翻车很多次。这个方法也推荐给你从第19题开始养成后面会越来越值钱。