OJ 104/105/106刷题复盘:输入输出、边界与溢出避坑指南 2月26号晚上我把OJ上的104、105、106三道题一次性收掉了。不是ACM大佬那种收是一个普通准备机试的人老老实实坐在电脑前和在线编程与OJ评测系统死磕。这三道题难度不高但刚好覆盖了数学、排序、字符串三类最常考的题型。做完之后我把完整过程复盘了一遍发现里面值得说的细节还真不少尤其是输入输出、边界条件、溢出这几个老生常谈又特别容易翻车的地方。这篇就当是刷题日志把OJ 104、105、106的题意拆解、代码实现、踩坑记录都写清楚。内容也照顾到准备华为OD机试、学校OJ日常训练、或者刚开始刷OJ的朋友很多坑是通用的。1. 刷题前的准备与选题策略1.1 为什么偏偏是104、105、106很多学校OJ的题目编号是按录入顺序排的104、105、106未必是相同难度或相同类型。我这次刷的OJ上104是数学里的最小公倍数105是数组去重排序106是字母频率统计。三道题正好覆盖了机试里最常出现的三类题简单数学题、排序处理题、字符串统计题。对刷题的人来讲我特别建议不要只盯着题号刷。一开始我也觉得“104、105、106”这种连号题肯定是从易到难其实不一定。有些OJ前几十道题是老师随手导入的难度像过山车。但低题号确实有个好处多数题目会收敛到最常见的数据结构和算法适合用来快速恢复手感。如果是准备华为OD机试强烈建议在正式刷题库之前先找一个在线OJ把所有输入输出样板题过一遍。华为OD机试用的是自己的OJ在线题库交互方式和传统ACM赛制接近多组输入、严格匹配空格换行、不允许输出额外调试信息。如果你习惯本地IDE跑通就复制很容易在评测系统上吃输出格式的亏。1.2 在线编程与OJ评测系统有哪些隐藏规则先说评测系统的运行逻辑。你提交代码后系统会用一组或多组测试数据运行你的程序然后拿你的标准输出和答案文件逐字符比对。注意是“逐字符”也就是说行尾多余空格、文件末尾多一个换行都可能导致Wrong Answer。另外大多数OJ都是黑盒测试不会告诉你到底哪个测试点挂了。常见状态有编译错误、答案错误、运行超时、内存超限、运行时错误。我第一次跑OJ 104的时候就是运行时错误后来检查才发现数组开小了但那种题根本没有数组。后来换了long long就过了说明评测系统对类型非常敏感溢出不会给你任何提示。还有个规则容易被忽略循环输入。经典题目都会写“输入包含多组测试数据读到文件末尾为止”很多新手拿cin直接读没判EOF结果只有第一组能过。后面我会专门放代码模板这是最值得抄的东西。2. 第一题 OJ 104最小公倍数先除再乘才是关键2.1 题意与解法选型OJ 104这道题描述很短每行输入两个正整数a和b求出它们的最小公倍数直到输入结束。看着简单其实考察两个点辗转相除法求最大公约数和整数溢出。最笨的做法是从1开始往上枚举一直枚举到a*b。这种暴力解法在小数据下没问题但一旦a和b到10^9级别枚举根本算不完评测系统直接给超时。正确做法是用公式lcm(a, b) a / gcd(a, b) * b注意必须先除再乘。举例说明如果a987654321b123456789a*b的结果约等于1.2e17明显超过了int的范围甚至可能超过32位有符号整数的上限。但如果先算a/gcd(a, b)结果一定小于等于a乘b也可能很大所以要开long long。C里的long long至少64位能表示约9.2e18对多数机试题目够用。求gcd用辗转相除原理很好记gcd(a, b) gcd(b, a % b)直到b为0。也可以用C17里的std::gcd函数但考虑到很多学校OJ的编译器版本老我自己写一个稳妥。2.2 代码实现和踩坑记录下面是我最后提交的版本#include cstdio long long gcd(long long a, long long b) { return b 0 ? a : gcd(b, a % b); } int main() { long long a, b; while (scanf(%lld %lld, a, b) ! EOF) { long long g gcd(a, b); printf(%lld\n, a / g * b); } return 0; }这段代码最核心的是while (scanf(...) ! EOF)。很多人刚刷OJ时会写成scanf(%lld %lld, a, b);然后直接处理一组就结束了。本地测倒是没问题但OJ的多组测试数据只跑第一组后面全没跑到自然答案错误。还有一个坑是输出格式。这题要求每个结果占一行我一开始习惯多打了个空格比如printf(%lld \n, ans);在本地控制台完全看不出来OJ直接给Wrong Answer。从那以后我养成了一个习惯提交前检查每个printf末尾不允许出现多余空格或换行。真的评测系统是个比处女座还挑剔的裁判。关于gcd我再说一个优化经验递归改成循环可以避免递归压栈但这里递归深度很小没问题。很多新手的误区是gcd函数里忘记处理ab的情况实际上辗转相除第一次取模后就会自动交换不需要提前判断。但为了代码可读性用三元表达式就够了。3. 第二题 OJ 105去重排序最后一行的空格害了我3.1 题意与算法选择OJ 105的题目是第一行给一个n第二行给n个整数去掉重复元素后从大到小输出。n的范围题目没说但根据历年机试经验很可能到10^5级别所以千万不要用两层循环暴力去重时间复杂度O(n^2)大概率超时。常见做法有两个用std::set。set底层是红黑树插入时自动去重并排序默认从小到大。如果要从大到小输出插入后倒着遍历或者用反向迭代器。先读入数组用std::sort排序再用std::unique去重。unique只会把重复元素移到末尾真正去重还需要配合erase。我推荐第二种原因有两个sort加unique的常数比set小且可以更自由地控制输出格式。set虽然写起来简单但每插入一个元素都要做红黑树旋转数据量大时性能和内存都不如vector排序。如果你是在华为OD机试那种在线OJ做这道题我个人建议用vectorint arr; sort(arr.begin(), arr.end(), greaterint()); auto last unique(arr.begin(), arr.end()); arr.erase(last, arr.end());。这种写法在C11之后都能编译且代码短。3.2 输出边界的处理方式这道题我踩过最亏的坑在输出要求每个数字之间用一个空格分隔但行尾不能有多余空格。很多人直接写for (int i 0; i ans.size(); i) { cout ans[i] ; }在本地看结果是“1 2 3 ”末尾多了个空格。OJ比较严格时这个空格就会让你Answer Wrong。正确的写法有两种我给出一种最容易理解的for (int i 0; i (int)ans.size(); i) { if (i) printf( ); printf(%d, ans[i]); } printf(\n);这个if (i)的意思就是除了第一个元素其他元素前面都补一个空格。这种输出风格在OJ题里特别常见建议直接当模板背下来。这道题还有一个边界n可能为0。虽然题目可能没说n的最小值但代码要兼容。如果n为0ans是空数组上面的循环会直接跳过最后输出一个换行。OJ一般允许你输出一个空行但有些题会要求什么都不输出。稳妥起见建议在循环前if (ans.empty()) continue;。写代码考虑边界不是强迫症是评测系统的测试数据真的很喜欢塞边界值。完整代码参考#include cstdio #include vector #include algorithm using namespace std; int main() { int n; while (scanf(%d, n) ! EOF) { vectorint a(n); for (int i 0; i n; i) scanf(%d, a[i]); sort(a.begin(), a.end(), greaterint()); a.erase(unique(a.begin(), a.end()), a.end()); for (int i 0; i (int)a.size(); i) { if (i) printf( ); printf(%d, a[i]); } printf(\n); } return 0; }强调一下unique(a.begin(), a.end())只能去掉连续重复的元素所以必须先排序再去重。如果你写成先unique再sort重复元素并不会被正确消除。4. 第三题 OJ 106字母频率统计getline和getchar要分清4.1 这道题真正想考什么OJ 106的题目是输入一行字符统计其中英文字母出现的次数忽略大小写和非字母字符最后按字母顺序输出每个字母和它的出现次数。这类题目表面上是字符串处理实际上考的是ASCII码映射和输入读取方式。先说输入读取。一行字符可能包含空格用cin s只能读到第一个空格为止所以必须用getline或cin.getline。在C语言里则是fgets或gets不过gets因为不安全在很多OJ编译器上已经不可用了。具体读法在C里推荐string line; getline(cin, line);但注意如果用scanf和getline混用会有一个很经典的坑。比如前面用scanf(%d)读了一个整数输入缓冲区里还剩一个换行符后面的getline会直接把这个空行读走。这就是为什么OJ 106这种题往往输入只有一行还好如果前面还有n你就得在getline之前把换行吃掉。处理办法是getchar()或者cin.ignore()。这里我更喜欢在每一个scanf后面加一个getchar()虽然麻烦但不会出问题。4.2 字母统计的两种实现统计字母频率可以用数组也可以用一个长度为26的map。数组更简单int cnt[26] {0}; for (char c : line) { if (isalpha(c)) { char lower tolower(c); cnt[lower - a]; } } for (int i 0; i 26; i) { if (cnt[i]) { printf(%c:%d\n, a i, cnt[i]); } }这里最关键的是cnt[int lower - a]让字母a到z映射到数组下标0到25。差值的范围一定是0到25所以数组长度26就够了。我见过有人写成cnt[c - 97]效果一样但可读性差。关于大小写也有人用位运算小写转大写可以c 0xDF大写转小写可以c | 0x20。我不建议新手用这种奇技淫巧直接tolower(c)最安全。注意tolower在C语言里接收int参数返回int需要强转成char。输出顺序要求按字母顺序因为我们遍历数组就是a到z天然有序。如果你用mapchar,int也会自动按键排序但map的常数比数组大不少。能用数组就不要用map。下面是完整代码#include cstdio #include cctype #include string #include iostream using namespace std; int main() { string line; while (getline(cin, line)) { int cnt[26] {0}; for (int i 0; i (int)line.size(); i) { if (isalpha(line[i])) { char low tolower(line[i]); cnt[low - a]; } } for (int i 0; i 26; i) { if (cnt[i]) printf(%c:%d\n, a i, cnt[i]); } printf(\n); } return 0; }三个坑点再提醒一遍isalpha只判断英文字母中文和数字都不算getline读到EOF时会返回false所以能自然退出循环每行输出后加一个空行是很多OJ的格式要求但有些题要求行间空行而末尾不空行这个要看题目描述。如果题目没说可以不加空行只按行输出。OJ 106原题里明确说了“每组输出后跟一个空行”所以我加了。5. 从学校OJ到华为OD机试不同OJ平台的风格差异5.1 别被平台差异绊倒刷题时间一长你会发现在信阳师范大学OJ、郑州轻工业大学OJ、杭电OJ、华为OD的OJ在线题库上做同一道题体验完全不同。最明显的是数据范围和测试点强度。杭电OJ的题量大很多经典题历史悠久数据范围出得比较狠。你在学校OJ上O(n^2)能过的题放到杭电OJ可能直接超时。信阳师范大学OJ这类校内OJ相对温和适合入门。华为OD机试更贴近工程筛选不会考特别偏的算法但特别在意输入输出和时间复杂度。XTU OJ 1103这种题比如平方差数或三数求和重点也是数学思维而不是代码量。我的经验是准备机试不要只刷一个平台。先在学校OJ把基础语法练熟再去杭电OJ或POJ感受真正的数据范围最后用华为OD题库做针对性训练。每个平台都是同一个评测逻辑但测试数据的“恶意”程度不一样。5.2 在线编程与OJ评测系统的通用模板不管在哪家OJ做单文件输入输出题我都建议保持一套固定模板。这个模板不一定最优但能帮你减少低级失误#include cstdio #include iostream #include algorithm #include cctype using namespace std; int main() { // 多组输入固定写法 int n; while (cin n) { // 做好输出格式控制 } return 0; }while(cin n)和while(scanf(...) ! EOF)是等价的。读字符串时注意和getline的配合。所有变量能用局部就不用全局。所有循环变量尽量定义在循环内避免污染作用域。这些习惯对评测系统没有任何影响但对排查bug很有帮助。6. 刷题避坑清单与长期建议6.1 我踩过的5个坑希望你别再踩整理一下2月26日刷题过程中遇到的典型问题全部转化成清单形式坑表现解决方法数据溢出用int算lcm样例过提交WA统一用long long存可能超int的结果多组输入没处理只输出第一组答案while循环读到EOF输出行尾空格本地看不出OJ报错用“第一项前不加空格”模板getline吃空行混用scanf和getline读不到数据scanf后加getchar或cin.ignore数组下标越界统计字母时cnt[c]而不是cnt[c-a]先减‘a’再访问数组只开266.2 给新手的刷题路径如果你真的想把OJ刷明白我建议按照这个顺序来先用两周时间专门练输入输出。不要觉得简单很多人卡在字符串输入上。每天做五道“ab”级别的题重点练scanf、getline、多组输入的组合。然后按专题刷数学题刷20道排序和查找刷20道字符串处理刷20道基础数据结构再刷20道。每道题AC之后花五分钟看一下别人的解法特别是时间复杂度和内存差距。最后再做套题和模拟机试。华为OD机试和很多学校OJ都有模拟赛定时两小时做三道题。只有定时你才会发现时间分配和调试效率有多重要。归到今天我做的104、105、106三道题都不算难但每道题都对应一类常见错误。能在一晚上把这三类错误全遇到再一个个解决我觉得比闷头刷十道重复题有用得多。刷OJ这事儿AC只是结果真正值钱的是排查“为什么不对”的过程。