东华OJ基础三件套：辗转相除法、回文判断与排序题避坑指南

最近我朋友在东华OJ上刷基础题，卡在了50、51、55这三道题上。他一开始觉得题库里的“基础”两个字，意味着几分钟就能A掉，结果折腾了一下午，WA到怀疑人生。我跟他说，这三道题恰好是入门阶段最典型的组合套餐，它们分别覆盖了数论、字符串、排序三个方向，是后面所有算法题的“地基三件套”。这篇文章我就拿自己账号里的这组50/51/55题面来复盘，说说每道题背后真正要考的东西，以及那些不会直接写进课件里的踩坑细节。

1. 先给50、51、55定位：这三题不是送分题，是基础三件套

1.1 常见题面与知识点对照

先说清楚我刷到的题面，方便后面按题展开。当然，不同课程班、不同老师挂出来的题库顺序可能不完全一致，但东华OJ基础段题目的构成通常就这几类，你按题目类型对号入座就行。

这三道题的难度都不高，但它们就像数学里的自然数：看起来谁都会，可一旦要写严格、写稳，细节立刻暴露水平。

1.2 三题连刷暴露的共性问题

我在帮朋友排错的过程中发现，这三道题连在一起，正好把新手阶段最常犯的四种错误全部引爆了：

• 多组输入只处理了一组，样例能过，提交后只能对第一组数据；
• 边界条件想当然，比如求最大公约数时遇到0，判断回文时空串，排序只有1个元素；
• 输出格式和OJ的预期不一致，通常表现为行末多一个空格、缺一个换行；
• 对题目给的数据范围不敏感，int敢存10^9以上的中间运算，算法复杂度也完全不考虑超时。

把这四个问题从三个题目里一起收拾掉，后面刷中等题时你会轻松非常多。下面逐题展开。

2. 50题复盘：最大公约数和最小公倍数到底怎么写给满分

2.1 辗转相除法的原理与递归写法

如果题面是输入两个正整数a和b，求最大公约数，学习过任何算法入门课程的人都能想到辗转相除法。它的数学表达只有一句话：gcd(a, b) = gcd(b, a % b)，当b等于0时，a就是最大公约数。

C++递归写法非常短：

int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); }

这个写法的好处是代码量最少，坏处是新手对递归过程没有直觉。如果遇到比较大的数，递归深度也就几十层，不用担心爆栈。但我个人更推荐迭代版本，因为你在本地调试时可以在循环里打印a和b的变化：

int gcd(int a, int b) { while (b != 0) { int tmp = a % b; a = b; b = tmp; } return a; }

这两种写法在OJ上都能AC，区别只在于你对过程的掌控感。如果你刚接触这类题，建议先把迭代版本手写三遍，直到闭着眼都能写对，再去背递归版本。

2.2 最小公倍数的运算顺序与溢出

最小公倍数的公式很简单：a * b / gcd(a, b)。但基础题里最大的坑就在这个公式上。如果a、b都是10^9级别，a * b已经是10^18，远超32位int的极限，中间结果直接溢出成负数，整个答案跟着崩。

正确写法是先除后乘：

long long lcm = a / gcd(a, b) * b;

先让大的数字变小，再做乘法，溢出的概率大大降低。这里还要提醒一点：即使你打算用long long，也不等于可以随便写。C++里a和b如果本身是int，a * b在执行乘法时仍然是int运算，只有把结果赋值给long long时才会拓宽。所以最好的习惯是：

long long lcm = (long long)a / gcd(a, b) * b;

先把其中一个因子转成long long，整个表达式的计算级别就被抬上去了。这个细节用Python的人体会不深，因为Python的int不会溢出，但写C/C++时它就是一个很实在的WA来源。我在给朋友看代码时，他直接就写了(a * b) / gcd(a, b)，我说你不用跑样例，肉眼就能看出这里有问题，换掉就对了。

2.3 多组输入与速度优化

东华OJ这类基础题常见的要求是“多组测试数据，每组占一行”，直到文件末尾EOF结束。很多新手只写一次处理就交，本地跑题目样例时当然能过，因为样例只有一组。提交后OJ会同时塞很多组数据进来，你的程序读了一组就结束，自然只对第一组。

C++的正确打开方式是：

#include <iostream> using namespace std; int gcd(int a, int b) { while (b != 0) { int tmp = a % b; a = b; b = tmp; } return a; } int main() { int a, b; while (cin >> a >> b) { int g = gcd(a, b); long long l = (long long)a / g * b; cout << g << " " << l << endl; } return 0; }

Python版本则是：

import sys def gcd(a, b): while b != 0: a, b = b, a % b return a for line in sys.stdin: line = line.strip() if not line: continue a, b = map(int, line.split()) g = gcd(a, b) l = a // g * b print(g, l)

关于速度，再补充一点细节。C++里cin默认和C标准库的输入输出同步，在多组输入数据较大时可能比scanf慢。担心性能的可以在main开头加一句：

ios::sync_with_stdio(false); cin.tie(0);

基础题数据量通常不大，加不加都能过，但这是一个值得很早养成的习惯，因为到后面的数据处理题里，输入规模一上来，这两行就能帮你多扛住不少时间。

2.4 一组WA排查流程

如果提交后看到Wrong Answer，先别急着从头到尾读代码，按下面这个顺序排查：

1. 确认有没有用while处理多组输入；
2. 确认输出格式是“两个数一行”还是“分行输出”，有没有多余字符；
3. 试极端数据：两个数相等、一个是1、一个极大一个极小；
4. 检查所有中间运算是否用了足够的类型宽度；
5. 如果用了递归，确认递归函数能正常终止。

我自己见过最多的情况是第一种和第二种，也就是多组输入和输出格式。算法写得再漂亮，输入输出拉胯，一样白搭。

3. 51题复盘：回文判断的字符串读入和边界是真正的拦路虎

3.1 双指针写法的原理

回文题常见题面是：输入一个字符串，判断它是否是回文，输出Yes或No。核心思路就是比较首尾字符是否相等，不断往中间收拢。双指针写法如下：

#include <iostream> #include <string> using namespace std; bool isPalindrome(const string& s) { int left = 0; int right = (int)s.size() - 1; while (left < right) { if (s[left] != s[right]) { return false; } left++; right--; } return true; } int main() { string s; while (getline(cin, s)) { cout << (isPalindrome(s) ? "Yes" : "No") << endl; } return 0; }

双指针的优势不只是省空间，更重要的是它训练的是“从两端逼近”的思维。后面遇到链表的回文结构、数组里的回文子串、在字符串里找最长回文区间，双指针都是最基础的起步思路。所以我建议你多用双指针，不要一上来就写reverse(s.begin(), s.end())然后比相等。虽然那种写法也能AC，但它对思维训练的贡献比较小。

3.2 空格、大小写、过滤条件

回文题最容易歧义的地方，就是题面里到底有没有说“忽略空格和大小写”。有的题要求只考虑字母和数字，忽略其他字符；有的题要求忽略大小写；有的题则什么都不忽略，原样判断。

别自作主张去过滤。题目没提忽略空格，字符串里面有个空格就不该算回文。如果真的要求过滤，最好的做法是先构造一个干净的字符串：

string cleaned; for (char c : s) { if (isalnum(c)) { cleaned.push_back(tolower(c)); } }

然后再对cleaned做双指针。isdigit、isalpha、isalnum、tolower、toupper这些函数都是C语言标准库自带的能力，刷题时很常用，值得背下来。ASCII码大小写转换这件事，我也提一句：'a' - 'A'的差值固定是32，如果你非要做手工转换，可以这么写，但能用tolower就尽量用标准函数，可读性高，还不用记ASCII表。

3.3 三种读入方式的选择

字符串读入是个反复会踩的坑。scanf("%s")、cin >> s遇到空格都会停，只能读不含空格的单词；getline(cin, s)或C语言里的gets能读整行。题面说“字符串可能包含空格”时，就必须用整行读入。

这里有一个特别常见的翻车现场：程序先读一个整数n，再用getline读字符串。你以为是读一行，结果getline把第一次读n之后留在缓冲区的换行符直接吞了，字符串就是空的。解决办法是在读整数之后加一句cin.ignore()，把缓冲区的换行清掉。

还有一个细节：Python里用input()读一行，会自动去掉末尾换行，但不会自动去空格。如果你用sys.stdin做逐行处理，记得把strip()加上，否则会把空白字符也带进字符串里。

3.4 空串、单字符与奇偶长度

判断回文时，空串和单字符都算回文。双指针版本里空串的right = -1，循环条件left < right不成立，直接返回true；单字符也是左右指针相等，不进入循环，返回true，所以不需要特殊处理。

奇偶长度的区别在于：奇数长度的回文，中间字符不需要参与比较；偶数长度的回文，左右指针最后会相遇在相邻两个位置。双指针天然处理这两种情况，不需要额外讨论。这比你用“字符串反转后和原串比较”更稳，因为反转版本不会直接给你中间字符的位置信息。

边界条件想清楚之后，这道题的核心代码其实不到十行。难就难在读入方式和题面理解上。

4. 55题复盘：从冒泡排序到sort，排序题应该准备到什么程度

4.1 手写排序的循环边界

55题常见题面是：输入一个整数n，再输入n个整数，把它们从小到大排序后输出。如果题面明确要求手写冒泡或选择排序，那循环边界就是第一道坎。

冒泡排序的C++代码：

for (int i = 0; i < n - 1; i++) { for (int j = 0; j < n - 1 - i; j++) { if (a[j] > a[j + 1]) { int tmp = a[j]; a[j] = a[j + 1]; a[j + 1] = tmp; } } }

这里的第二个循环j < n - 1 - i不是随便写的。每一轮冒泡都会把当前未排序区间里的最大值送到末尾，所以已经排好的部分就不用再碰了。如果写成j < n - 1，也能跑，但后面每轮多做了无效比较；如果写成j < n - i，a[j + 1]在j = n - i - 1时就是a[n - i]，在最后几轮可能越界。基础题偶尔还能侥幸过，数据量大一点就会出问题。

选择排序的思路是每一轮找到最小值的下标，然后和当前位置交换：

for (int i = 0; i < n - 1; i++) { int minIdx = i; for (int j = i + 1; j < n; j++) { if (a[j] < a[minIdx]) { minIdx = j; } } int tmp = a[i]; a[i] = a[minIdx]; a[minIdx] = tmp; }

两个算法都是O(n^2)复杂度，在n是100、1000时没问题，如果n到10^5以上，就等着TLE。所以看到题面的数据范围后，要先决定用不用手写O(n^2)的算法。

4.2 库函数选择与稳定性

如果题面没有要求手写排序，直接用C++标准库的sort：

sort(a, a + n); // 数组 sort(v.begin(), v.end()); // vector

省事是省事，但我建议你同时知道sort和stable_sort的区别。sort不保证稳定性，stable_sort保证相等元素的相对顺序保持不变。排序题里有一个经典场景：若干学生的姓名和成绩，要求按成绩从高到低排，成绩相同的按姓名字典序排。这时候如果你笔试按成绩排一次，再按姓名排一次，或者直接sort，都容易出事。更好的写法是用lambda表达式自定义比较规则：

sort(stu.begin(), stu.end(), [](const Student& x, const Student& y) { if (x.score != y.score) return x.score > y.score; return x.name < y.name; });

结构体排序在基础题里不是必须，但它是从“会排序”走向“会按规则排序”的关键一步。55题就算没考，也值得提前掌握。

4.3 复杂度和数据范围匹配

排序题的隐藏考点往往不在排序本身，而在你选什么排序方式。我看到过有人对n = 10^6的数据用冒泡排序，结果自然是TLE。正确的反应应该是：看到n的范围后，先判断能不能承受O(n^2)。

通常的经验：

• n ≤ 1000：冒泡、选择、插入随便写；
• n ≤ 10^5：需要用O(n log n)的快速排序或归并排序，C++直接sort；
• n ≤ 10^6：sort依然没问题，注意输入速度，必要时用scanf或关闭cin同步；
• 如果数值范围很小，比如0到1000之间，还可用计数排序O(n + maxVal)。

这些不是55题直接考的内容，但它是递进到后续题目时一定要有的意识。基础排序题只是帮你把门槛迈过去。

4.4 输出格式的最终检查

排序题的输出通常有两种方式：每行一个数，或者一行内用空格分隔。每行一个数没什么好说的，直接cout << a[i] << endl。容易出问题的是第二种：一行输出所有数，数字之间一个空格，行末不能有空格。

推荐写法：

for (int i = 0; i < n; i++) { if (i) cout << " "; cout << a[i]; } cout << endl;

这种“先判断下标，再决定是否输出空格”的模式，能保证最后一个数字后面没有多余空格。如果你写的是cout << a[i] << " "，最后一个数后面就会多一个空格，OJ会返回Presentation Error。这个错误在基础题阶段很常见，但也很容易根治：输出数字序列时，统一用“分隔符前置”的思路。

5. 三道基础题练出来的OJ提交习惯，能帮你避开大多数WA

5.1 本地造数据与重定向测试

我刷这三道题时给自己定了一个规矩：每道题提交之前，先在本地构造至少三组测试数据。一组是题目给的样例，一组是极端边界，一组是多组输入连发。本地多跑几组，绝对比提交到OJ上靠系统告诉你要高效。

终端里可以用输入重定向：

./program < input.txt

input.txt里放多行数据，模拟多组输入。这样你一次性就能验证程序是不是正确读取了全部数据，而不是只在第一组数据上表现出色。

5.2 打印调试法比盯着代码硬看更有效

新手排错时最容易做的事是盯着代码反复看，看了十分钟也看不出哪里不对。这时候不如直接在关键位置打印中间变量。比如手写冒泡排序时，每一轮结束后打印整个数组，立刻就能看到是不是每轮都把最大值送到底部；求最大公约数时打印a和b的变化，能确认循环次数是否符合预期。

打印调试法虽然土，但它是定位逻辑错误最直接的方式。加几行输出再重新运行，往往比闭门造车快很多。问题找到后，记得把调试输出删掉再提交。

5.3 看懂OJ返回状态码的含义

东华OJ的反馈常见有这几种，把它们的含义弄清楚，能少走很多弯路。

WA不是世界末日，它只是告诉你“输出结果和系统期望不一致”。你按顺序排查输入、边界、输出，大概率能定位到问题。别在没看题面范围的情况下反复提交同一种算法，那是低效的测试方式。

5.4 输入输出速度细节

基础题数据量不大时，cin和cout就够用了。但如果你开始刷更复杂的题，输入/输出的I/O开销可能成为TLE的帮凶。C++推荐在main开头加上：

ios::sync_with_stdio(false); cin.tie(0);

Python则可以尽量使用sys.stdin.buffer.read()一次性读入，然后在内存中Split，而不是逐行用input。对基础50/51/55三道题来说，这些属于“提前储备”的技巧，等后面用到时你会感谢自己没偷懒。

6. 按这套思路把基础题吃透，后面刷题会顺很多

6.1 为什么要回头反复看这三道题

我在东华OJ上刷题最受用的一次回顾，就是隔了一周重新做50、51、55这三道基础题。第一遍是磕磕绊绊靠调试过的，第二遍是直接凭框架写出来的。差别在哪？差别在于第一遍只关注“怎么通过”，第二遍开始关注“为什么要这么写”，比如多组输入的while循环意味着评测系统会一次性喂给你很多测试数据，比如排序题的数据范围直接决定算法选择。

这三道题的底层价值，不只是在OJ上刷三笔AC记录，而是把“读题一构造数据一写代码一自查边界一提交验证”这条流程走完整。后面遇到的题不管是动态规划还是广度优先搜索，起步方式依然是这五个步骤。

6.2 如果你现在正卡在三题中的某一题

最后给你一个当下就能用的策略。先把代码放一边，回到题面，看三件事：数据范围、输入格式、输出格式。这三件事想明白了，代码通常十分钟就能改完。然后再用边界数据一个个套，套完再提交。

我自己的经验是，基础题WA一小时以上的情况，十有八九是卡在“多组输入”或“输出格式”上，而不是真正的数学或字符串算法。你把这几个显性坑全部排掉，剩下的才是真正需要动脑的部分。等你把50、51、55三道题都AC之后，成就感不只是那三个绿色打钩，更是你终于对OJ的输入输出规则建立起了肌肉记忆。

后面再刷东华OJ的进阶题，你会发现读入和输出几乎不再是你卡关的原因。那时候基础题的回报，就真正体现出来了。