不知不觉刷OJ已经到了第五天。按计划推进到题单里的第13题到第15题不算快但每天三道题的节奏让我慢慢摸到了门道。这三天的题目分别是数字三角形、字符串反转和最大公约数覆盖了循环嵌套、字符串处理、基础数论三类基本功。顺便说一句每次我点开输入框准备搜某某OJ答案的时候都会告诉自己再想十分钟。今天想把这三天踩过的坑、悟到的思路、以及关于OJ刷题平台的一些个人观察认真整理出来。1. 先说说这个第五天刷13到15题的计划1.1 为什么固定每天三题刚开始刷OJ的时候我也试过一天刷十几道水题爽是爽但第二天全忘了。后来我改变策略每天只做三道题做完以后把代码重写一遍、把易错点记录到笔记里反而进步更明显。三道题的量刚好能让你保持手感也不会因为连续卡题产生挫败感。第五天这个时间点选得挺巧妙。前四天基本把输入输出、条件判断、简单循环这些热身内容过了一遍到第13到15题正好进入一个综合应用的过渡阶段。题目不再是单一步骤能解决需要你开始考虑怎样的循环结构更清晰、哪个输入函数不会出幺蛾子、哪种算法能避免超时。1.2 13到15题恰好是三种基本功这三天遇到的三道题刚好覆盖了三个不同方向。第13题是数字三角形典型的循环嵌套加输出格式控制题。它表面上是让你打印图形实际上考查的是你能不能用一个外循环控制行数、内循环控制列数同时保证输出的空格和换行一个不多一个不少。这种题最恶心的地方是——逻辑很简单格式错了照样WA到怀疑人生。第14题是字符串反转考的是你对字符数组或者说字符串类的掌握。题目本身思路极直白但里面埋了输入函数的坑。你要是不知道 cin 遇空格就停这个特性怎么写都只能过一半数据。第15题是求最大公约数从暴力枚举升级到辗转相除法算是一道入门算法题。它需要你具备最基本的优化意识同样能出答案但你的程序能不能在数据范围变大之后依旧跑得快。这三道题放在一起效果其实是递进的先练代码实现能力再练输入输出的严谨性最后练算法思维。如果你现在也刷到类似的进度位置正好可以对照这三个方向自查一下。1.3 关于搜答案我多说两句基于我搜索过的关键词记录来看现在搜XX大学OJ答案、XX OJ 1065答案的同学真不少杭电OJ 1002、东方博宜OJ 1065、郑州轻工业大学OJ的题几乎都有人求答案。我不反对借鉴题解但强烈不建议直接复制提交。原因很简单OJ判题只看代码对不对你复制一次平台不会给你任何警告但下次考试、面试笔试的时候没有现成代码可以抄。正确利用题解的方式是卡了二十分钟想不出来去看一眼题解的核心思路然后合上题解自己把代码写出来。哪怕写得磕磕绊绊、效率很差那也是你的收获。这份自己啃出来的体验比交十道抄来的AC题有意义得多。2. 第13题数字三角形2.1 题目与样例这道题目描述很简短输入一个正整数n1 ≤ n ≤ 9输出一个n行的数字三角形第i行输出i个数字i。输入4输出1 22 333 4444听起来毫无难度对吧但你要是小看它分分钟在格式上被卡死。2.2 解题思路思路就是一层循环控制行数一层循环控制这一行输出几个数字。外循环 i 从1到n代表当前是第 i 行内循环 j 从1到 i每行输出 i 次所以内循环每次输出的是同一个数字 i输完 i 个之后换行。这里最容易犯的错误是搞不清内循环输出的是行号还是列号。我见过有人写成cout j结果输出出来是个直角三角形从1递增到n看起来像那么回事但和题目要求完全不符。做题之前先多想一句第 i 行要打印的是 i 个几答案永远是 i和 j 没关系。2.3 代码与两个必须避开的坑#include iostream using namespace std; int main() { int n; cin n; for (int i 1; i n; i) { for (int j 1; j i; j) { cout i; } cout endl; } return 0; }一个必须避开的坑是输出数字之间不能加空格题目要求每行就是连续的一串数字。很多同学习惯在cout i后面顺手加个空格或者 结果格式错误被OJ判成 Presentation Error还以为自己逻辑有问题。另一个坑更隐蔽如果题目变成了金字塔形状前面有空格居中对齐那你还需要额外一层循环来输出空格。那种情况下顺序必须是先空格、再数字、最后换行位置颠倒也会WA。好在这道题是左对齐版本不用考虑这块但你要有这个意识OJ题目的输出格式描述里每一个空格都是算数的。2.4 平时不会说的输出格式细节可能有人会问为什么OJ这么变态程序运行结果明明是对的多加个空格就不给过这个还真不是故意刁难你。OJ的判题方式是把你程序的输出和标准答案做逐字符比较一个空格、一个换行都算差异。真实场景里很多自动化测试工具也是这个逻辑它们不关心你看起来对不对只关心是不是一模一样。从第一天刷OJ起就养成不输出多余字符的习惯后面你会少流很多泪。3. 第14题字符串反转3.1 题目与样例题目描述输入一行字符串可能包含空格长度不超过100输出它的反转结果。输入hello world输出dlrow olleh3.2 核心坑点cin读不了空格这是我第五天踩得最扎实的一个坑。拿到题我看了一眼心想这也太简单了直接写string s; cin s;结果一测输入 hello world输出只有 olleh。原因大家都知道了cin s遇到空格或换行就停止读取它只能读入第一个单词。题目明确说一行字符串可能包含空格所以这里必须用getline(cin, s)来读取整行。注意如果前面刚用cin n读过整数后面再用getline可能会读到一个空行。原因是cin n会在缓冲区里留下一个换行符getline直接把它当成了一行。解决方法是先cin.ignore()把残留的换行符清掉。这个问题在混合读入数字和字符串的题目里极其常见我在笔记里标了三颗星。3.3 三种实现方式第一种直接用STL里的reverse。#include iostream #include string #include algorithm using namespace std; int main() { string s; getline(cin, s); reverse(s.begin(), s.end()); cout s endl; return 0; }这种方式代码最短适合比赛里抢时间。但如果你在练手阶段我建议至少手写一次反转逻辑否则对原地交换这个过程没有体感。第二种双指针交换。一个指针指向开头一个指向结尾交换两个位置的字符后各自往中间移动直到相遇。#include iostream #include string using namespace std; int main() { string s; getline(cin, s); int left 0, right s.length() - 1; while (left right) { char tmp s[left]; s[left] s[right]; s[right] tmp; left; right--; } cout s endl; return 0; }第三种倒序输出不修改字符串本身。用循环从最后一位开始往前遍历输出也能达到效果而且思路最直观。for (int i s.length() - 1; i 0; i--) { cout s[i]; } cout endl;三种写法里比赛用第一种理解原理用第二种面试和基础演示可以用第三种。各有各的使用场景不用迷信哪一种。3.4 复杂度小结无论哪种写法时间复杂度都是O(n)因为你只需要遍历一遍字符串。空间复杂度上reverse和双指针交换都是O(1)的额外空间倒序输出则是O(1)空间没有额外数组。这种入门题不考虑复杂度也能过但提前养成分析的习惯后面做递归、动归的时候会轻松很多。4. 第15题最大公约数4.1 题目与样例题目描述输入两个正整数a和b1 ≤ a, b ≤ 10^9输出它们的最大公约数。输入12 18输出64.2 为什么不能暴力很多初学者第一反应是暴力枚举从1到min(a, b)找出能同时整除a和b的最大数。这个思路没错但效率有问题。假设a和b都在10^9的量级暴力循环最多要执行10^9次在普通的OJ环境下1秒很难跑完。如果题目再狠一点多给几组测试数据暴力时间直接爆炸。这时候就需要数学工具来帮忙。你可以把这件事类比成你要找一个长走廊里的某个开关一间间房间去翻暴力和直接看走廊结构图定位数学方法效率完全不是一个级别。OJ题卡时间本质上就是逼你用后者。4.3 辗转相除法原理辗转相除法欧几里得算法的核心结论是gcd(a, b) gcd(b, a % b)。也就是说两个数的最大公约数等于较小的那个数和它们相除余数的最大公约数。这个操作可以反复执行直到余数变成0此时另一个数就是答案。举个例子求gcd(48, 18)48 % 18 12所以变成求gcd(18, 12)18 % 12 6所以变成求gcd(12, 6)12 % 6 0结束答案是6每一步都在把问题规模缩小而且缩小的速度非常快时间复杂度大约是O(log min(a, b))。即使两个数都是10^9级别最多也就二三十次运算对计算机来说毫无压力。4.4 几个容易翻车的细节递归实现非常简洁#include iostream using namespace std; long long gcd(long long a, long long b) { return b 0 ? a : gcd(b, a % b); } int main() { long long a, b; cin a b; cout gcd(a, b) endl; return 0; }这里我必须提一个新手特别容易犯的错数据范围。题目里a和b最大10^9int类型最多能表示约21亿表面上能存下但如果你在这道题基础上求最小公倍数LCM a / gcd * b中间结果会超过int范围。所以我个人习惯只要题目数据范围有可能超过10^6我就直接用long long省得后面踩溢出坑。另外一个细节很多老OJ的C环境里不能用__gcd这个内置函数那是GNU扩展不是标准库函数。C17倒是提供了std::gcd但如果判题机用的是老编译器编译直接报错。最稳妥的方案永远是自己写一个gcd函数十行以内搞定别依赖那些不确定的编译器特性。5. 实战踩坑实录OJ判题的那些规矩5.1 本地能跑交上去不对第五天第14题就让我体验了一次本地AC、OJ WA的经典场景。我在自己电脑上测试了一堆带空格的字符串全都正常一提交上去就答案错误。排查了半天最后发现是getline前面有个残留的换行符。因为前面我用了cin n读测试组数换行符留在缓冲区里getline读到的其实是空行后面的真正内容根本没被处理。本地测试时我输入了完整的换行结构没有模拟出这个细节所以没暴露。从那以后我养成一个习惯提交之前把自己代码的输入流程再过一遍尤其是先读数字再读字符串的组合一定记得处理换行符残留。这个坑非常经典我建议所有刷OJ的人都提前写好一版带cin.ignore()的模板避免现场翻车。5.2 不同OJ平台的口味差异这几天我也搜了一下各个OJ平台的情况。杭电OJHDU是老牌平台题号从1000开始1002那题是经典的大数加法考察的是竖式模拟而不是直接加法非常典型杭州师范大学OJ、湘潭大学OJ、西北农林科技大学OJ这些学校平台各有各的题单很多题目直接对应课程进度。华为OJ则更接近公司机试场景考察的不仅是算法还有对题目约束条件的敏感度题目风格更工程化。不同的平台在细节上也有差异有的平台用GCC但版本很老不支持C11的新特性有的平台用Visual Cscanf_s之类的写法各有各的规矩有的平台要求最后一行输出必须有换行有的平台多一个换行也不算错误。所以刷一个新平台之前先看一眼它支持的编译器版本再到讨论区看看大家吐槽过的提交细节能帮你少瞎折腾很多。5.3 五个新手最容易忽略的点我把自己前五天踩过的坑做了个清单照着查一遍能省很多时间变量类型题目数据范围大不大要不要用long long输入残留读完数字后有没用cin.ignore清掉换行输出格式每行末尾有没有多余空格最后有没有换行数组边界开数组时有没有留够空间多组数据时有没有清空判题结果类型WA、PE、RE、TLE代表的含义完全不一样先弄清楚再改代码这五天下来我感觉自己的读题能力和调试能力提升得比会写更多题更明显。很多时候WA不是不会而是细节没到位。把这些细节内化成习惯比多刷几十道题更值。6. 常见问题速查表6.1 常见错误类型整理我看很多刚接触OJ的同学看到错误类型一多就慌。这里整理个速查表错误类型含义常见原因AC完全正确无WA答案错误逻辑有误、数据类型不匹配、读入范围有误PE格式错误输出多了空格、少了换行基本是要调整输出格式RE运行时错误数组越界、除以零、递归栈溢出TLE超时算法效率太低需要换复杂度和思路MLE内存超限数组开太大或递归/容器占用过多内存CE编译错误语法错误或者用了当前编译器不支持的语法看到WA先别改代码重新读一遍题目确认输入输出的每个细节看到TLE优先检查循环层数看看有没有办法剪枝或者用数学公式替代暴力。6.2 我刷题时的自查清单每次提交前我会回看这几项题目给的最大数据范围我的变量类型够不够多组输入时我的循环条件是不是正确的结束方式读字符串时用的是cin还是getline有没有空格输出是不是完全按照题目的样例格式包括空格和换行有没有在循环里频繁使用高成本的容器拷贝导致TLE这套清单我在手机备忘录里存了一份每次卡题就拿出来过一遍效率提高了不少。6.3 关于刷题平台选择与答案资源的建议平台选择方面学生党首选自己学校的OJ因为题目难度和课程内容对上号遇到问题还能找同学交流。想挑战难度就刷杭电OJ的老题或者洛谷、Codeforces国外平台这类综合题库。华为OJ更适合准备机试、找工作的同学题目背景更贴近真实场景。至于答案资源我的真实体验是搜答案最大的代价不是找不到而是找到了之后你就不思考了。东拼西看别人的代码最终写出来的程序自己都不一定每一行都懂。刷题真正的收获量取决于你有多少次是自己想通了。第五天的一点收尾体会这几天刷下来我最明显的感受是OJ题目更多地是在磨你的确定性——确定每一个分支、每一个边界、每一种输入形式都处理对了。第13题让我记住了输出格式不是差不多就行第14题让我学会了正视输入函数的特性第15题让我意识到同样的答案实现方式的天壤之别。如果你也在按部就班地刷题我想说别急着赶进度。把每道题吃透卡过十分钟二十分钟再求助提交AC之后隔天重写一遍这些笨功夫才是真正的捷径。明天我按计划做第16到第18题到时候继续把新的坑和心得整理出来。
