刷OJ第五天：数字三角形、字符串反转与最大公约数实战总结

不知不觉，刷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 题目与样例

这道题目描述很简短，输入一个正整数n（1 ≤ 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 olleh

3.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和b（1 ≤ a, b ≤ 10^9），输出它们的最大公约数。

输入：

12 18

输出：

6

4.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^9，int类型最多能表示约21亿，表面上能存下，但如果你在这道题基础上求最小公倍数（LCM = a / gcd * b），中间结果会超过int范围。所以我个人习惯：只要题目数据范围有可能超过10^6，我就直接用long long，省得后面踩溢出坑。

另外一个细节：很多老OJ的C++环境里不能用__gcd这个内置函数，那是GNU扩展，不是标准库函数。C++17倒是提供了std::gcd，但如果判题机用的是老编译器，编译直接报错。最稳妥的方案永远是自己写一个gcd函数，十行以内搞定，别依赖那些不确定的编译器特性。

5. 实战踩坑实录：OJ判题的那些规矩

5.1 本地能跑，交上去不对？

第五天第14题就让我体验了一次"本地AC、OJ WA"的经典场景。我在自己电脑上测试了一堆带空格的字符串，全都正常，一提交上去就答案错误。

排查了半天，最后发现是getline前面有个残留的换行符。因为前面我用了cin >> n读测试组数，换行符留在缓冲区里，getline读到的其实是空行，后面的真正内容根本没被处理。本地测试时我输入了完整的换行结构，没有模拟出这个细节，所以没暴露。

从那以后我养成一个习惯：提交之前，把自己代码的输入流程再过一遍，尤其是"先读数字再读字符串"的组合，一定记得处理换行符残留。这个坑非常经典，我建议所有刷OJ的人都提前写好一版带cin.ignore()的模板，避免现场翻车。

5.2 不同OJ平台的"口味"差异

这几天我也搜了一下各个OJ平台的情况。杭电OJ（HDU）是老牌平台，题号从1000开始，1002那题是经典的大数加法，考察的是竖式模拟而不是直接加法，非常典型；杭州师范大学OJ、湘潭大学OJ、西北农林科技大学OJ这些学校平台各有各的题单，很多题目直接对应课程进度。华为OJ则更接近公司机试场景，考察的不仅是算法，还有对题目约束条件的敏感度，题目风格更"工程化"。

不同的平台在细节上也有差异：有的平台用GCC但版本很老，不支持C++11的新特性；有的平台用Visual C++，scanf_s之类的写法各有各的规矩；有的平台要求最后一行输出必须有换行，有的平台多一个换行也不算错误。所以刷一个新平台之前，先看一眼它支持的编译器版本，再到讨论区看看大家吐槽过的提交细节，能帮你少瞎折腾很多。

5.3 五个新手最容易忽略的点

我把自己前五天踩过的坑做了个清单，照着查一遍能省很多时间：

• 变量类型：题目数据范围大不大，要不要用long long
• 输入残留：读完数字后有没用cin.ignore清掉换行
• 输出格式：每行末尾有没有多余空格，最后有没有换行
• 数组边界：开数组时有没有留够空间，多组数据时有没有清空
• 判题结果类型：WA、PE、RE、TLE代表的含义完全不一样，先弄清楚再改代码

这五天下来，我感觉自己的读题能力和调试能力提升得比"会写更多题"更明显。很多时候WA不是不会，而是细节没到位。把这些细节内化成习惯，比多刷几十道题更值。

6. 常见问题速查表

6.1 常见错误类型整理

我看很多刚接触OJ的同学，看到错误类型一多就慌。这里整理个速查表：

看到WA先别改代码，重新读一遍题目，确认输入输出的每个细节；看到TLE优先检查循环层数，看看有没有办法剪枝或者用数学公式替代暴力。

6.2 我刷题时的自查清单

每次提交前，我会回看这几项：

1. 题目给的最大数据范围，我的变量类型够不够
2. 多组输入时，我的循环条件是不是正确的结束方式
3. 读字符串时用的是cin还是getline，有没有空格
4. 输出是不是完全按照题目的样例格式，包括空格和换行
5. 有没有在循环里频繁使用高成本的容器拷贝，导致TLE

这套清单我在手机备忘录里存了一份，每次卡题就拿出来过一遍，效率提高了不少。

6.3 关于刷题平台选择与"答案"资源的建议

平台选择方面，学生党首选自己学校的OJ，因为题目难度和课程内容对上号，遇到问题还能找同学交流。想挑战难度就刷杭电OJ的老题，或者洛谷、Codeforces（国外平台）这类综合题库。华为OJ更适合准备机试、找工作的同学，题目背景更贴近真实场景。

至于"答案"资源，我的真实体验是：搜答案最大的代价不是找不到，而是找到了之后你就不思考了。东拼西看别人的代码，最终写出来的程序自己都不一定每一行都懂。刷题真正的收获量，取决于你有多少次是"自己想通了"。

第五天的一点收尾体会

这几天刷下来，我最明显的感受是：OJ题目更多地是在磨你的"确定性"——确定每一个分支、每一个边界、每一种输入形式都处理对了。第13题让我记住了输出格式不是"差不多就行"；第14题让我学会了正视输入函数的特性；第15题让我意识到同样的答案，实现方式的天壤之别。

如果你也在按部就班地刷题，我想说：别急着赶进度。把每道题吃透，卡过十分钟二十分钟再求助，提交AC之后隔天重写一遍，这些"笨功夫"才是真正的捷径。明天我按计划做第16到第18题，到时候继续把新的坑和心得整理出来。