最近把东华oj基础区刷到第74-76题结果这三道题让我一个晚上都没睡好。不是题目本身有多难而是它们刚好覆盖了刷OJ入门阶段最容易翻车的三个点循环拆数位、因子枚举、字符串处理。74题是水仙花数75题是完数76题是回文数都是在线判题系统里的经典常客。如果你也在oj刷题刚学完循环、数组和字符串拿这套题练手非常合适但一定要有心理准备——你本地跑出来明明是对的上传之后照样可能WA或者PE。这篇文章不是官方的标准题解就是把我从读题、写码、被评测系统打脸到最终AC的完整过程复盘一遍有代码、有边界测试、还有那些OJ不会写在题目里但一定会扣分的规则。1. 刷到基础74-76题之前先把OJ的输出“潜规则”记住1.1 多组输入与EOF哪怕题目没写“多组测试”也要留个心眼很多新手第一次做东华OJ基础题的时候习惯按“单组数据”写代码。比如题目说“输入一个整数判断是不是水仙花数”就直接写一个cin n然后跑完样例本地对提交就只过第一个样例后面全错。这里的关键是OJ的输入评测文件里通常有多个测试样例每一样例单独占一段。你在本地看到的“一个输入样例”只是冰山一角服务器会一次性把多组数据灌进你的程序。所以一定要用循环读入int n; while (cin n) { // 处理一组数据 }如果是C语言习惯对应写法是int n; while (scanf(%d, n) ! EOF) { // 处理一组数据 }EOF就是文件结束标志。OJ把测试数据放在一个文件里程序读到文件末尾就返回EOF。很多老题目的输入描述里根本不会明确说“多组测试”但你得默认它有这个习惯。这个套路在我刷东华oj基础区的时候几乎每三题就能遇到一次提前写上去不亏。1.2 行末不能有多余空格AC和PE之间就差一个空格在线判题里有一种特别搞心态的结果叫PE全称Presentation Error中文一般叫“格式错误”。它表达的意思很明确你的答案逻辑完全正确输出内容也对就是格式不对。最常见的情况就是行末多了一个空格。举一个很典型的例子题目要求输出100到999之间的所有水仙花数数与数之间用空格分隔。很多人会写出这种代码for (int i 100; i 999; i) { if (isNarcissistic(i)) { cout i ; // 每个数后面都带空格 } }本地看输出是153 370 371 407人眼觉得没问题但OJ会把最后一个数后面的空格和标准答案比对结果就是PE不允许通过。正确的做法是“第一个数前面不带空格后面的数输出时先补一个空格”bool first true; for (int i 100; i 999; i) { if (isNarcissistic(i)) { if (!first) cout ; cout i; first false; } } cout endl;这种写法以后刷所有“用空格分隔”的题目都能直接套别等到被PE折磨了才记住。1.3 样例里的普通提示信息不是输出内容还有一个特别新手的问题有些人看到题目样例里写着please input n:就老老实实把这句话也打印出来。实际上样例里的中文提示语或者please这类文本通常只是说明输入是什么不是要求程序输出的东西。除非题目输出描述里明确写了要输出特定字符串否则一律只输出数据本身。这一点听起来很蠢但我在OJ评论区见过不止一个同学犯这个错。记住一句话OJ比对的是“输出文件”而不是“人眼看到的控制台”多一个字符、少一个换行都算错。2. 第74题“水仙花数”循环枚举只是热身真正的坑在拆数位2.1 从“三位数的定义”开始拆逻辑水仙花数是指一个三位数其每个数位上的数字的立方之和等于它本身。例如153 1^3 5^3 3^3。这个题目一般要求输出所有水仙花数范围就是100到999。很多人第一反应是“用一个变量表示三位数然后把百、十、个位拆出来”。这个思路没问题关键是拆位的方式要稳。假设当前数是iint a i / 100; // 百位 int b i / 10 % 10; // 十位 int c i % 10; // 个位这段代码里最容易踩坑的是十位。有人会写成i % 100 / 10也可以但初学者容易搞混。我建议统一用“除以10再模10”的思路先除以10把个位丢掉再模10取现在的个位也就是原来的十位。这样逻辑最顺不容易错。2.2 一份能直接AC的基础代码C版我自己的AC写法是这样#include iostream using namespace std; int main() { bool first true; for (int i 100; i 999; i) { int a i / 100; int b i / 10 % 10; int c i % 10; if (a * a * a b * b * b c * c * c i) { if (!first) { cout ; } cout i; first false; } } cout endl; return 0; }这份代码最大的亮点不是算法难而是把输出空格问题一并处理了。如果题目要求“每个水仙花数换一行”那就把空格判断和 删掉直接cout i endl;即可。2.3 关于pow函数的小提醒有些同学喜欢用pow(a, 3)来计算立方以为更高级。但pow返回的是double在整型环境下可能会出现浮点误差例如pow(5, 3)在某些编译器上可能输出124.9999转成int后就变成124导致判断错误。所以基础题里老老实实写成a * a * a完全够用也不会出错。2.4 边界思维为什么从100而不是0开始题目说的是“三位数”所以不要从0或是1开始遍历。如果你把范围写成for (int i 1; i 999; i)虽然结果可能仍然正确但逻辑上不符合题意在一些改成“所有N位水仙花数”的扩展题里就会出错。刷题时最好养成习惯代码里的边界条件要和题目描述完全对应。3. 第75题“完数”暴力破解不会超时但你要会处理因子对3.1 完数定义与第一版暴力写法完数也叫完全数指的是一个数恰好等于它的“真因子之和”。所谓真因子就是不包括它本身的所有正因子。最经典的例子是6 1 2 3所以6是完数。再比如28它的真因子是1、2、4、7、14加起来也等于28。如果题目要求1到1000内所有完数最简单粗暴的写法是双层循环for (int n 2; n 1000; n) { int sum 0; for (int i 1; i n; i) { if (n % i 0) sum i; } if (sum n) { // 输出 n 和它的因子 } }这个写法优点是思路直白不容易错。1到1000的范围很小1000 * 1000也才100万次计算OJ上早就跑完了。但是我现在刷题会习惯性考虑如果范围变成1万、10万甚至100万这个双层循环就废了。所以与其以后重构不如一开始就写更高效的因子枚举方式。3.2 sqrt优化因子成对出现但容易重复加任意正整数n的因子都是成对出现的。比如n 28因子对是(1, 28)、(2, 14)、(4, 7)。这意味着我们不需要从1一直遍历到n只需要从1遍历到sqrt(n)找到一个小因子i之后直接把它的搭档n / i也累加进去。关键点来了求完数时因子之和不能包含n本身。所以处理因子对时如果n / i n就得跳过。这种情况只发生在i 1时所以我通常在初始化时直接把因子1加进去再从i 2开始枚举这样就永远不会把n本身加进去。另一个坑是平方数比如n 36因子6只出现一次。i * i n时如果把i和n / i都加进去就会把6算两遍。所以需要加个判断只加一次。完整的因子求和逻辑int sum 1; // 1 是真因子先加上 for (int i 2; i * i n; i) { if (n % i 0) { sum i; if (i * i ! n) { sum n / i; } } }注意我用的是i * i n不是i sqrt(n)。这样避免了浮点数运算还更快。这个写法在后续很多数论基础题里都能复用。3.3 按题目要求的等式输出“6 1 2 3”这道题有个容易让人纠结的地方就是输出格式。东华oj基础题里完数通常要求按类似6 1 2 3的格式输出。这里的等号、空格、加号都不能乱而且因子必须从小到大排列。如果采用sqrt优化因子收集时不是严格有序的例如28的因子对会收集到1、2、14、4、7所以输出前需要排序。完整代码如下#include iostream #include vector #include algorithm using namespace std; int main() { int limit 1000; // 根据题目要求调整 for (int n 2; n limit; n) { vectorint factors; factors.push_back(1); for (int i 2; i * i n; i) { if (n % i 0) { factors.push_back(i); if (i * i ! n) { factors.push_back(n / i); } } } sort(factors.begin(), factors.end()); int sum 0; for (int f : factors) sum f; if (sum n) { cout n ; for (size_t i 0; i factors.size(); i) { if (i 0) cout ; cout factors[i]; } cout endl; } } return 0; }这里有一个很容易被忽略的边界输入范围如果是1开头那么n 1需要单独跳过。因为1的真因子是空集和为0不等于1所以直接跳过即可。我这代码从2开始循环就是为了避开这个边界。3.4 我在完数题上亏过的“超时”与“漏因子”我之前第一次写这题时因为想当然用了i sqrt(n)结果在某个OJ上因为浮点误差导致平方数少算了一个因子连续WA了两次。后来改成i * i n才过。还有一次我把sum初始化为0然后从i 1开始枚举结果把n / i这个因子加了进去导致每个数都把自己算进去了怎么都不对。后来我在草稿纸上把28的因子对列出来才发现问题所在。所以建议所有刚开始刷数论题的同学遇到因子类题目先写个测试函数打印每个数的因子肉眼核对一遍再交比盲目提交高效得多。4. 第76题“回文数”能用字符串就用字符串别折腾整数反转4.1 整数反转的溢出与负号问题判断回文数最直觉的做法是把整数反转然后和原数比较。比如121反转后还是121就是回文数。这个思路本身没问题但有一个隐藏风险——整数反转可能溢出。假设题目给的测试数据很大比如1234567899反转后变成9987654321如果用的是32位的int这个值已经超出范围了程序一反转就溢出结果不可控。很多OJ基础题的数据范围看起来不大但保不齐有边界测试。与其去赌数据范围不如换一个更稳的思路。另外负数要不要判断为回文这得看题目要求。如果不做特殊处理直接把-121当成字符串来判断它和121-比较不相等所以会判成“不是回文”。这在多数场景下是对的因为负号出现在开头反转后出现在结尾必然不对称。4.2 用string做双指针三分钟搞定更好的做法是直接读入字符串用双指针从两头往中间比较。代码非常简单#include iostream #include string using namespace std; int main() { string s; while (cin s) { bool ok true; int left 0; int right (int)s.size() - 1; while (left right) { if (s[left] ! s[right]) { ok false; break; } left; right--; } cout (ok ? yes : no) endl; } return 0; }这段代码为什么靠谱因为它完全避开“反转整数”这个操作。字符串比较只看对称位置是否相同即使输入有100位它也照常处理不会溢出。4.3 负数、前导0和空字符串这些边界怎么处理使用字符串解法后有几个边界要特别注意。第一如果输入可能包含-号比如-121直接字符串比较会得到“不是回文”这通常没问题。但如果是-121-这种字符串比较会得到“是回文”可它作为一个整数并不是合法的回文数。所以遇到带负号的输入我一般会先规定如果第一位是-直接输出“不是回文”。具体是否要这样处理一定要看题目描述里有没有“整数”两个字。第二前导0的情况比如010。按字符串判断0和0匹配会认为它是回文。但如果题目把它当作整数10那10不是回文。OJ上这类题一般不会故意用这种输入卡人但你要有这个意识读题时判断它到底按“字符串”处理还是按“整数”处理。第三单个字符比如0或5一定是回文数。双指针条件left right在长度为1时不进入循环ok保持true输出yes这是正确的。4.4 多组输入时把循环写对别把输出写在循环外这道题如果是多组输入很容易犯一个错把while(cin s)循环条件写好但输出语句不小心放在了循环外结果只输出最后一组的结果。我的习惯是每组数据都在循环体内独立判断、独立输出这样即使某一行数据导致异常也不会影响下一组数据的处理。基础题的多组输入逻辑基本上就是这么简单但真的每次都有新手在论坛里问“为什么只输出一行”。5. 东华OJ基础题最容易触发的四种评测结果WA、PE、RE、TLE5.1 WA不一定是思路错可能是你没看到输出格式里的空格WAWrong Answer是大家遇到最多的结果。很多人一看WA就怀疑核心算法实际上在基础题里WA往往和算法没关系而是对题目的“隐藏规则”理解不到位。比如题目要求输出所有完数并且用空格隔开有人输出了换行题目要求“每个测试数据之间空一行”有人只在最后多打了一个换行。这些都是WA。我的解决方法是拿到WA后先不要改算法而是重新读三遍输出格式那一段。把题目里的“每个数之间用空格分隔”“每个结果占一行”这些要求逐词拆开再和你的输出代码对照。多数WA都能在这一步找到原因。5.2 PE答案对但格式错也被判定为不通过PE在OJ上非常让人恼火。从人眼的视角看你的输出和标准答案完全一样但OJ系统逐字符比对发现多了个空格就是不让你过。讲得直白一点OJ就是一台没有感情的机器它不看你“人脑补全”之后的效果。我在第74题里讲过first变量控制空格的思路这个方法在输出“以空格分隔的一维数据”时是万能的。还有一个小技巧如果题目允许不确定的空格数量可以直接把每个数据输出成一行这样从根本上消除行末空格问题。但前提是题目要求“每个占一行”如果要求一行内空格分隔就不能这么做。5.3 RE数组开小经常发生在循环里RERuntime Error往往比WA更吓人因为你觉得代码没问题但评测系统说“运行错误”。基础题里RE最常见的原因是数组越界。有些同学处理多组输入时开了一个定长数组int a[1000]但测试数据里出现了1001个元素越界访问就直接崩。应对RE的思路很简单数组空间宁大勿小尤其是涉及字符串、矩阵的题目开数组时多给一二十个余量。我在刷东华oj基础题时会把所有数组统一开成题目最大范围的2倍这样即使题目边界描述不准确也大概率不会越界。虽然不优雅但很实用。5.4 TLE基础题也会超时循环层次和隐藏数据量是关键TLETime Limit Exceeded在基础题里不像在难题里那么常见但也不是没有。比如完数那题如果题目范围改成1万甚至10万纯暴力双层循环就很容易超时。所以我才在第75题里强调了sqrt优化。还有一个隐藏坑是重复计算。有些人把因子求和写成一个函数在循环里反复调用而且函数里又从1跑到n导致整体复杂度比想象中高很多。基础题锻炼的不仅是“能算出来”还有“别做太多无用功”。把sqrt优化的写法记牢很多数论基础题都能直接套用。6. 刷完这组基础题之后我总结的三点刷题习惯6.1 做题前先把输入输出“翻译”成注释我现在每写一道题第一步不是敲代码而是在代码最上面写注释// 输入多组整数EOF结束 // 处理判断回文数 // 输出每行一个 yes / no这个习惯看起来简单但能有效避免写一半忘记题目要求。之前我经常写代码到一半开始“自由发挥”回头对不上题目只能推倒重来。现在先把输入输出边界写清楚写代码时就不会跑偏。6.2 本地测试别光测样例还要测边界很多人把样例跑过就交这是最亏的。样例只是为了让你理解题意的“友好数据”真正的测试数据里一定包含边界值。刷74-76这类基础题时我会额外测这几个输入最小值比如0、1、100最大值比如999、1000特殊结构比如回文数里的121、完数里的6和28输入包含空格或负号的情况。把这些边界在本地跑一遍比自己盲目提交十几次要高效得多。OJ虽然会扣分但它不会告诉你哪里错了本地调试反而更快。6.3 别迷信“别人AC代码”自己跑一遍边界再抄遇到不会的题参考别人的代码是正常的。但我发现一个问题很多AC代码其实只针对当时那组测试数据换一组边界就会挂。比如用pow判断水仙花数在某个OJ上也许能AC但在另一个OJ上可能因为浮点误差WA。所以抄别人的代码之前一定要自己把逻辑走一遍尤其是边界处理是否严谨。我自己刷完东华oj基础74-76题最大的收获不是记住三道题的答案而是掌握了一套“面对任何基础题都不慌”的处理流程先理清边界再选最稳的数据结构最后用最保守的格式输出。这套东西在后来刷任何OJ平台的题目里都一直在用。最后再分享一个我个人的小习惯如果某道题连续提交三次还没AC我会果断放下代码拿一张纸把题目要求和测试数据手动模拟一遍。往往在我写到第五六步的时候就能发现自己到底哪里想歪了。刷OJ最忌讳的不是写不出代码而是明知道代码有问题却不肯回头一步步验证。基础题尤其如此。