东华OJ基础题74-76题：C语言算法与字符串实战解析

1. 东华OJ基础题的定位：74-76题在刷题路线中的位置

1.1 基础题到底在考什么

东华OJ的基础题区域，一直是很多C语言初学者从“课本代码”过渡到“在线判题”的第一站。我自己当年也是从这里开始的，所以对这个区间的题号特别有印象。基础74-76题，恰好卡在一个很微妙的位置：前面的题基本在练顺序结构、选择结构和简单循环，到了七十多题，题目开始往数组、字符串、函数和基础数学算法上靠。换句话说，这已经不是单纯的“照着书上敲代码”，而是要求你真的能用C语言去解决一个“需求”。

很多同学到了这个阶段会突然觉得吃力，原因不在于语法不会，而在于“没有建立起一套读题、分析、编码、调试的完整流程”。东华OJ的判题系统不会告诉你哪里错了，只给你一个冰冷的Wrong Answer，这跟以前运行出结果就算对的课堂作业完全不同。所以我强烈建议：别急着刷数量，先把74-76题这种基础阶段的核心题吃透，它们背后的知识点会在后面的题里反复出现。

1.2 别把OJ当“做题”，要把它当“调试实战”

我刚刷OJ的时候踩过一个特别蠢的坑：在本地Dev-C++里运行结果明明是对的，一提交就是WA。后来才发现，我用了scanf("%d%d", &a, &b)，但是题目要求输入一批数据直到文件结束，我压根没处理EOF。这种问题在教科书上不会出现，因为书上的例题只跑一次，但OJ的判题程序会用多个测试点反复跑你提交的代码，任何一端行为不对，整个程序都算错。

所以，基础74-76题的意义不只是“会写这几个功能的代码”，而是让你习惯“程序要能正确处理任意合法输入”。这也是为什么很多刷题前辈会反复强调：一定要掌握while (scanf(...) != EOF)这种输入模式，同时注意变量初始化，不然每次循环残留上一次的数据，就容易出现那种“明明逻辑都对，结果全错”的诡异现象。

2. 解基础题的核心思路：从读题到代码的转化过程

2.1 读题时先抓四件事：输入、输出、边界、样例

拿到一道题，不管在东华OJ还是别的地方，我都建议你先做一个“四步拆题法”。第一步，看输入格式：有几组数据？一行几个数？是整数还是实数？有没有多组测试直到EOF？第二步，看输出格式：每行输出几个结果？中间用空格还是换行？末尾有没有多余空格？第三步，看数据范围：数的上限是多少？会不会超过int的范围？数组该开多大？第四步，看样例：把样例手动跑一遍，确认自己没有理解偏。

我见过很多同学把时间浪费在“尝试各种奇怪写法”上，实际上是因为第一句话就没看懂。比如题目说“多组输入，每组一行两个正整数”，有人只写了一次scanf，那提交上去基本必WA。基础74-76题的难度不大，但恰恰会考察这种细致程度。把四件事写在草稿纸上，再动手，效率至少提高一倍。

2.2 选择算法前先算复杂度，别让TLE毁掉你的AC

很多刚接触刷题的同学会问：“这题不是很简单吗？直接循环不就完了？”但你得先看数据范围。假设题目要求输出100万个斐波那契数的某一项，你用递归去写，栈直接爆掉，就算不爆栈，光是重复计算的次数就够让判题系统给你一个Time Limit Exceeded。

基础题阶段虽然不会出特别变态的复杂度题，但你要习惯在写代码前算一笔账。比如求最大公约数，用辗转相除法，每次迭代都能让数据规模缩小一半以上，100万以内的数最多几十次循环；如果你用从1开始枚举到min(a,b)的方式，那到100万量级就要循环百万次，遇上多组数据就直接超时。我在第74题左右的区间见到过类似“最小公倍数”的命题，很多同学直接暴力枚举，侥幸跑过一部分测试点，但隐藏测试点一上大数就露馅。学算法初期就养成“算一算再动手”的习惯，后面受益无穷。

2.3 数据类型与溢出：基础题里最隐蔽的坑

这个点我必须单独拎出来说，因为太多人挂在上面。东华OJ的基础题经常涉及“求最大公约数和最小公倍数”这种数学计算，最小公倍数的公式是a * b / gcd(a, b)，看起来没问题，但实际上a * b可能已经爆掉int的范围。正确做法是先除后乘：a / gcd * b，或者直接用long long。

另外，斐波那契数列这类递推题，到第46项附近就会超过int的2^31上限，如果你题目要求n到50，那你必须用long long，否则溢出后出现负数，WA得莫名其妙。我建议基础阶段就把一个习惯刻进脑子里：涉及乘法、累加、递推的题目，只要数据范围没有明确小到离谱，一律优先考虑long long。这不丢人，反而能帮你少交好几次WA。

3. 典型题型演练：以三个常考方向拆解74-76题的解法

3.1 数论类题目：最大公约数与最小公倍数

基础区间最常出现的数论题就是最大公约数和最小公倍数。约定的解法是欧几里得算法，也叫辗转相除法，核心就一句：两数相除取余数，再把除数变成被除数、余数变成除数，直到余数为0，最后的除数就是gcd。

#include <stdio.h> int gcd(int a, int b) { while (b != 0) { int t = a % b; a = b; b = t; } return a; } int main() { int a, b; while (scanf("%d %d", &a, &b) != EOF) { int g = gcd(a, b); long long lcm = (long long)a / g * b; printf("%d %lld\n", g, lcm); } return 0; }

我特别解释一下为什么这里要先除后乘：如果按a * b / g的写法，当a和b都在10万量级时，a*b能达到1e10，已经超出32位int的范围，变成负数后再除g也没意义。而a / g算出来一定是整数，再乘b，只要结果是long long范围内的数，就不会出错。这个细节，笔试面试也常考，属于“看着简单但很容易忽略”的典型。

3.2 字符串处理题目：反转、判回文

字符串在OJ基础题里是另一个高频方向。通常考察的是字符数组的操作、strlen的使用、对称位置的交换。比如“字符串反转”这道经典题，很多人会用第三个变量交换，但只看结果的话，整个字符数组原地反转需要一个循环：

#include <stdio.h> #include <string.h> void reverseString(char s[]) { int len = strlen(s); int left = 0, right = len - 1; while (left < right) { char t = s[left]; s[left] = s[right]; s[right] = t; left++; right--; } } int main() { char str[1005]; while (gets(str) != NULL) { reverseString(str); puts(str); } return 0; }

这里要提醒两点。第一，C语言用gets读取带空格的字符串，但现在很多平台不推荐gets，因为存在溢出风险，网络安全领域对此批评很久了。稳妥的替代方案是用fgets(str, sizeof(str), stdin)，它会读入换行符，所以要在处理前手动把末尾的\n删掉。东华OJ的判题环境是接受gets还是禁止，不同版本可能有差异，如果你提交遇到编译警告，建议直接改用fgets。第二，题目如果是“输入一行字符，按单词反转”，那又是另一套思路了，需要先反转整句，再反转每个单词，这类变形题我后面再说。

3.3 递推与数列题目：斐波那契与循环结构

基础题里还有一种典型：给出递推公式，求第n项或前n项。最经典的就是斐波那契数列。很多教材都会用递归来讲，但刷OJ时我不建议用递归，因为n稍微大一点，递归的时间和空间开销都无法接受。迭代才是正解：

#include <stdio.h> int main() { int n; while (scanf("%d", &n) != EOF) { long long a = 1, b = 1; if (n >= 1) printf("%lld", a); if (n >= 2) printf(" %lld", b); for (int i = 3; i <= n; i++) { long long c = a + b; printf(" %lld", c); a = b; b = c; } printf("\n"); } return 0; }

你要注意，输出格式要求“数字之间用空格隔开”，我上面的写法是每输出一个数就带一个前导空格，这样能避免最后一个数后面多出空格。多数OJ对行末空格其实容忍，Presentation Error就是专门用来提醒你格式有问题的。为了少一次提交，建议一开始就按严格格式写。

这个阶段还会出现“数列求和”“分数序列”之类的变体，但核心都是找递推关系。我的经验是：先把前三项写出来观察，找到规律后再动手写循环，经验不足时千万别直接开码。

4. 完整实操：三题从零到AC的现场记录

4.1 第74题的完整代码与提交过程

我在刷这个区间的时候，把第74题当成了“数学基础题”的代表。假设题面是“求两个正整数的最大公约数与最小公倍数，多组输入”，那么我的操作步骤是这样的：先在草稿纸上写完gcd的迭代过程，确认边界情况——如果b是0，gcd返回a；如果输入一个0一个正数，gcd应该是那个正数，但很多OJ会保证输入都是正整数，所以不用过于担心。接着写主函数，处理EOF循环。

提交之前我做了一次自查：把int lcm改成long long lcm，因为最小公倍数可能超过int上限。这个改动看似无关紧要，但在隐藏测试点里能救你一命。提交后返回AC，这个题就算扎根了。如果你的WA，优先检查是不是没处理多组输入，或者输出格式里多打了case这类字样。

4.2 第75题的完整代码与提交过程

第75题如果是字符串方向，我当时的做法是写一个reverseString函数，先算长度，再用双指针向内收缩交换。双指针这个技巧在数组、链表、字符串里都通用，值得专门练熟。写完后，我习惯用带空格的字符串测试一遍，比如输入hello world，看反转过来是不是dlrow olleh。

这里最容易踩的坑是：忘记字符串以\0结尾，导致strlen多算或少算。使用fgets时，换行符也会被存进数组里，反转后换行符跑到了字符串开头，输出怪怪的。解决方法是读入后如果最后一个字符是\n，就把它改成\0，处理完再反转。这个问题在东华OJ的讨论区出现过好多次，可见是共性问题。

4.3 第76题的完整代码与提交过程

第76题如果是递推类，我建议你除了写代码，还要在本地额外测几个边界输入：n等于1时只输出一个1；n等于2时输出“1 1”；n等于20时，输出应该以6765结尾。如果你发现n=2时多输出一个空格，或者n=1时崩了，那就是边界条件没写好。

我当时提交时还犯过一个很经典的低级错误：变量a和b没有初始化，导致第一次循环时用了未知值。虽然C语言里long long a=1,b=1这种写法看似啰嗦，但相比之下，万一你写成long long a, b;然后在循环里才赋值，就可能因为某条分支没走导致输出垃圾值。基础题阶段，把所有变量统统初始化，能帮你省掉非常多的无谓WA。

5. 新手常踩的坑与判题系统规则速查

5.1 WA、TLE、RE、PE分别是什么问题

我把东华OJ常见的返回状态整理成一个速查表，方便你们对照排查：

碰到WA别急着改代码，先在本地把样例跑一遍。如果样例能过，就自己构造极端数据，比如最大数、最小数、同一数连续输入等。大部分WA都是隐藏测试点暴露出来的边界问题。

5.2 导致隐藏测试点挂掉的五个典型原因

第一个是输入循环条件写错，常见的有while(1)没有跳出分支，或者没判断EOF，程序在最后一次读不到数据时重复执行了旧值。第二个是数组开小了，常见于字符串题，题目说字符串长度不超过1000，你就得开到1005以上，多留几位给末尾的\0甚至换行符。第三个是没有处理多组数据之间的残留值，比如你用了静态变量，上一组数据影响下一组结果。第四个是整数溢出，前面提到的a*b/g是典型。第五个是输出格式问题，比如每组结果之间需要空一行，你只用了单换行。

5.3 快速定位Bug的三个小技巧

我在刷题时有一个“三分法定位”的思路：先在程序开头加一句printf("test1\n")，看是否执行到那里；再在循环中间加printf("test2\n")，看循环执行次数对不对；最后在输出前加打印，看变量值是否符合预期。定位后再把调试语句删掉，重新提交。

第二个技巧是“对比样例逐行跟踪”。拿题目样例里的输入，自己用草稿纸算出期望输出，然后观察程序每个循环后变量的变化。很多逻辑错误其实一遍手算就能发现问题，比瞎改来得快。

第三个技巧有点取巧：如果实在找不出错，把代码里所有int改成long long再提交一次试试。这不是万能药，但能快速排除一类溢出型WA。不过要记住，改完后基础题的输出格式可能对%d和%lld敏感，别漏了格式串。

6. 刷完基础题之后怎么走

6.1 把每道题沉淀成代码模板

我在基础区间反复练习之后，最大的收获不是AC了几道题，而是攒下了一套模板：带EOF循环的主函数框架、gcd函数、fgets处理字符串的写法、迭代斐波那契的写法。遇到新题，先把模板搭起来，再往里面填业务逻辑，速度会快非常多。

模板这个东西很私人的，建议你自己整理，不要直接抄别人的。整理的本身就是在梳理思路。比如我会在注释里写清楚“这段循环为什么从3开始”“为什么这里用long long”，这样等过一个月回头翻，还能明白当初的思考过程。

6.2 用“改题”的方式检验自己是否真懂

检验一道题你有没有真正掌握，我推荐一个“改题三部曲”。第一，把输入范围改大一倍，想想代码还能不能AC。第二，把输出要求从“顺序输出”改成“倒序输出”，你还能不能快速改出来。第三，把数据结构从数组改成链表或字符串，看看你理解是否还成立。

这三种改动会逼你思考题目背后的本质，而不只是背代码。我在刷东华OJ的时候，最喜欢干的事情就是看完一道题的题解之后，合上题解重新敲一遍代码，然后故意给自己出几个变体，直到变体也能顺利AC才肯罢休。

6.3 从东华OJ向更广的刷题平台延伸

东华OJ的基础题是一个很友好的起点。它帮你确认了语言基础、输入输出习惯、判题系统的基本规则。但编程能力真正拉开差距，往往是在你跳出舒适区之后。等基础题刷完，可以尝试去更大众的在线判题平台，从简单题开始，逐步接触深度优先搜索、动态规划、图论这些内容。

不过我想提醒一点：不要一味追求平台名气，也不要因为某个平台判题更严格就焦虑。刷题的本质是训练“把实际问题转化为可计算步骤”的思维方式，东华OJ基础题和外面的题，背后的逻辑都是相通的。你在这里养成的每一个好习惯，后面都会十倍百倍地回报你。

就我个人来说，从基础74-76题往后刷了大概两百题之后，我才真正体会到“先分析后动手”这句话的力量。很多同学在七十多题这个位置放弃了，真的太可惜。基础阶段的题目确实不起眼，但它们就像盖楼前的地基，看着全是泥，其实决定了你这栋楼能盖多高。