刷东华OJ基础题刷到74-76这个位置很多人会有一个共同的感受前面七十多道题写起来挺顺的基本就是练练循环、数组、条件判断到这儿突然觉得题目“变味”了。不是题目超纲而是这阶段的题开始把多个知识点揉在一起考。你可能上一题还在处理简单数学公式下一题就要同时处理字符串、数组索引、边界条件甚至还要自己琢磨输入格式。基础74-76题恰恰是东华OJ基础区里一道分水岭刷过去后面再看结构体、链表、递归这些章节心态会稳很多卡在这儿很容易怀疑自己是不是不适合写代码。这篇就专门聊这个阶段。我会把74-76这几题常见的出题套路、解题思路、提交时容易踩的坑都拆开讲一遍。不管你是刚把循环搞明白的新手还是刷题进度卡住的“半卡户”这篇都值得看完再动手写。1. 东华OJ基础74-76题的整体定位与核心难点1.1 为什么刷到这儿突然觉得吃力先说说我对东华OJ基础题区的整体印象。前面大概70题基本上是一道题对应一个考点判断闰年、求阶乘、数组逆序、冒泡排序只要你把对应的模板记熟了套进去就能过。代码量普遍在二三十行以内思路也比较直。到了74-76这个区间题目描述开始变长考点也开始叠加。我举个例子纯考察“判断回文串”的题前面已经出过好几道了但到中后段如果再出现回文相关题往往会加上“忽略空格和标点”“不区分大小写”“输入可能包含多组数据”这些附加条件。表面上看还是回文判断实际考的是字符串预处理、边界处理、多组数据循环这三件事的组合。这种变化让很多习惯“背模板”的人很难受。因为模板解决的是单考点问题而组合题需要你自己去拆解这题到底要我做几步每一步的输入输出分别是什么中间哪些地方可能出边界问题1.2 这个阶段真正考察的能力拆题我在带学弟学妹刷题的时候发现一个挺常见的现象拿到一道题读了三遍然后就开始写代码写到一半发现思路不对删掉重来。这不是代码能力问题是缺少拆题的环节。所谓拆题就是把一道完整的题目分成三块来看输入是什么包括数据的类型、数量、格式以及是否有结束条件比如读到EOF为止。处理过程是什么这一步是核心决定了你要用哪些变量、哪些循环、哪些条件判断。输出是什么包括格式、精确位数、换行要求。拿基础74-76这类中后段的题来说80%的“不会做”其实不是不会写代码而是没有把题目里的逻辑梳理清楚。我在这个阶段养成了一个习惯先拿纸笔写伪代码用自然语言把处理过程描述一遍再转成C语言。这么做前期看起来多花几分钟实际上能省下反复调试的一两个小时。1.3 中后段基础题常见的三个出题方向根据东华OJ基础题区的整体分布74-76这个位置通常逃不开这三个方向字符串处理类读入字符串、逐字符判断、大小写转换、子串操作。数值计算与数论入门素数判断、进制转换、最大公约数、数字拆分重组。数组操作与简单逻辑去重、排序、矩阵操作、按规则筛选。我后面会分别把这三个方向拆开讲每个方向都会给出可以直接“抄作业”的思路和代码框架。提示如果你刷到某道题发现不是这三类先别急着怀疑看看题目的核心数据是“字符”还是“数字”还是“一组数的排列”大概率是这三类的变种。2. 字符串处理题先搞定一行数据的读入再谈逻辑2.1 一个必踩的坑scanf和gets混用字符串处理题在这个阶段频繁出现而新手栽跟头最多的地方不是字符串的逻辑处理而是“数据读不进来”。典型场景是这样的题目先给你一个整数n表示后面有n行字符串然后要求你对每一行做处理。很多人的第一反应是int n; char str[100]; scanf(%d, n); gets(str);然后发现第一行字符串读出来是空的或者直接跳过了一行。原因很简单scanf(“%d”) 读走的是数字回车符还残留在输入缓冲区里紧接着的gets把这个回车符当成空串读走了。解决方式也很简单在scanf之后、gets之前用一个getchar()把残留的换行符吃掉int n; char str[100]; scanf(%d, n); getchar(); // 吃掉换行符 gets(str);如果你用的是fgets也一样需要处理这个残留换行。这个问题几乎每学期都有一堆人踩属于这个阶段“打过一次就再也不会忘”的经典坑。2.2 回文判断的完整拆解假设题目是给一行字符串可能包含空格和标点判断忽略空格、标点、大小写之后是否为回文。这个题目就很典型能代表74-76阶段的字符串难度。我的做法是分三步走。第一步读入整行。考虑到字符串中可能有空格不能用scanf(“%s”)读得用gets或fgetschar str[1000]; gets(str);第二步过滤掉非字母数字字符统一转为小写或大写存到一个新数组里char clean[1000]; int len 0; for (int i 0; str[i] ! \0; i) { if ((str[i] A str[i] Z) || (str[i] a str[i] z) || (str[i] 0 str[i] 9)) { if (str[i] A str[i] Z) { clean[len] str[i] 32; // 大写转小写 } else { clean[len] str[i]; } } } clean[len] \0;第三步双指针判断int left 0, right len - 1; int flag 1; while (left right) { if (clean[left] ! clean[right]) { flag 0; break; } left; right--; } if (flag) { printf(YES\n); } else { printf(NO\n); }这里要特别提醒判断结束条件是 left right不是 left right。如果字符串长度为偶数用 会在中间两个字符错位后多判断一次导致误判。2.3 字符串处理题的其他常见变化74-76阶段的字符串题除了回文判断还经常出这些变种统计某个字符出现的次数注意大小写是否合并统计。把字符串中的单词按顺序输出每个单词之间用空格隔开。字符串加密或解密比如循环移位。这类题的处理套路是一致的先逐字符遍历把需要的字符挑出来再对挑出来的内容做进一步处理。不要试图“一步到位”——边遍历边输出有时确实能过但逻辑一复杂就容易乱还是先处理到新数组里更稳妥。3. 数值计算与数论入门题数学建模是核心3.1 素数判断别只会从2除到n-1这个阶段如果遇到素数相关题目首先得判断只是单纯判断一个数还是要输出一堆素数。这两者的复杂度差别很大。如果只是判断单个数是不是素数用从2到sqrt(n)的循环就够了int isPrime(int n) { if (n 2) { return 0; } for (int i 2; i * i n; i) { if (n % i 0) { return 0; } } return 1; }注意两个细节一是n小于2直接返回0二是循环条件用 i * i n不要用 i sqrt(n)。前者是整数运算快后者每次循环都要调用sqrt函数效率低而且涉及浮点数精度边界容易出错。如果是要求输出一个区间内所有素数建议直接用埃氏筛。这个阶段接触筛法确实显得有点超前但它的原理很好理解从2开始把所有2的倍数标记为合数然后找下一个没被标记的数再把它的倍数标记掉。int isPrime[1000001]; void initPrime(int n) { for (int i 2; i n; i) { isPrime[i] 1; } isPrime[0] isPrime[1] 0; for (int i 2; i * i n; i) { if (isPrime[i]) { for (int j i * i; j n; j i) { isPrime[j] 0; } } } }我自己就是在这个阶段第一次接触筛法当时觉得“这也太麻烦了吧”但后面做数据结构的题时经常用到那时候才发现这个思路有多重要。如果这道题的数据范围是10万以上你还在用逐个判断的写法几乎必然超时。3.2 进制转换除基取余注意逆序输出进制转换题在基础题中后段基本是保留曲目。最常见的是十进制转R进制思路就一句话除R取余逆序排列。举个例子十进制13转二进制13 % 2 113 / 2 66 % 2 06 / 2 33 % 2 13 / 2 11 % 2 11 / 2 0把余数从下往上排得到1101。代码实现上用一个数组存余数最后倒着输出void decToR(int n, int r) { int ans[100]; int len 0; if (n 0) { printf(0\n); return; } while (n 0) { int mod n % r; if (mod 10) { ans[len] A (mod - 10); } else { ans[len] 0 mod; } n / r; } for (int i len - 1; i 0; i--) { printf(%c, ans[i]); } printf(\n); }这里面最容易被忽略的是n等于0的情况。很多人的while循环条件一写n0时就压根不进入循环输出就成了空。这种边界情况就是OJ的爱考的点。反过来R进制转十进制也要会。思路是从高位往低位逐位处理result result * r 当前位数字。int rToDec(char str[], int r) { int result 0; for (int i 0; str[i] ! \0; i) { int digit; if (str[i] 0 str[i] 9) { digit str[i] - 0; } else { digit str[i] - A 10; } result result * r digit; } return result; }3.3 数字拆分取模和整除的配合还有一种经常混在74-76里的题给一个数要求逆序输出、求各位之和、判断某位数字出现次数等。这类题核心就是取模和整除的配合。while (n 0) { int digit n % 10; // 处理 digit n / 10; }这个循环体每转一圈就处理了当前最低位然后砍掉最低位。如果你要的是从高位往低位处理一种办法是先算出这个数的位数另一种是把数字转成字符串处理。说实话字符串在某些时候反而更简单比如判断某位数字出现次数时直接遍历字符串就行。注意如果题目要求保留前导零比如输入是00123那就不能用整数读入了必须按字符串处理。这个细节经常成为WA点。4. 数组操作与简单逻辑先想清楚数据怎么存4.1 数组去重两种思路对比数组去重题在OJ里出现频率极高形式变化也很多有的要求去掉重复值然后原顺序输出有的要求统计每种值出现次数有的要求按出现次数排序。但底层逻辑都一样需要记录“这个值是否已经出现过”。最直接的做法是暴力双重循环外层遍历每个元素内层看它是否在之前已经出现过。这个方法我一开始也在用但写到后面发现每次内层都要从头扫时间复杂度是O(n^2)数据量一大就跑不动了。更好的做法是“空间换时间”用一个标记数组记录每个值是否出现过。比如数据范围是1到10000就开一个长度为10001的数组int seen[10001] {0}; int result[1000]; int resultLen 0; for (int i 0; i n; i) { if (!seen[a[i]]) { seen[a[i]] 1; result[resultLen] a[i]; } }这个思路的核心是把“这个值出现过没有”这个信息存下来而不是每次去现查。很多初学者会觉得“开这么大的数组太浪费了”其实现代OJ内存通常是128MB甚至更多一个10000的int数组才40KB完全不用担心。4.2 排序题要搞清楚排序规则这一类题只要涉及排序很多人直接掏出冒泡排序或选择排序的模板开始写。但在74-76阶段题目往往会要求“按分数排序分数相同按名字字典序排序”“按出现次数排序次数相同按首次出现顺序排序”之类的复合规则。这时候要先确定一件事交换两个元素的依据是什么如果是双关键字排序就要把比较的逻辑单独拎出来if (score[i] score[j] || (score[i] score[j] strcmp(name[i], name[j]) 0)) { // 交换 }这种写法放在冒泡里很直观。推荐先把比较条件写在纸上再往代码里套不容易乱。4.3 矩阵类题目下标的对称关系矩阵相关的基础题也常在74-76出现比如求主对角线元素之和、副对角线元素之和、矩阵转置。核心是要记住下标规律主对角线i j副对角线i j n - 1如果同时要求“不包括两条对角线交点”要判断 n 是奇数还是偶数。交点元素在主对角线和副对角线相交处n为奇数时存在n为偶数时不存在。这类细节题目不会明说但样例里通常藏着答案。另外矩阵输入的行列顺序也要看清是先输入行数还是先输入列数直接影响双重循环的嵌套顺序。5. 从“本地能跑”到“OJ能过”的实操过程5.1 先看输出格式Presentation Error 的根源很多新手第一次被PE格式错误整懵就是在基础题中后段开始。明明输出内容是对的答案却判错问题往往出在空格和换行上。我踩过最经典的一个坑题目要求输出一行多个数每个数字后面跟一个空格。我写成了“先输出第一个数再循环输出空格数”结果最后面多了一个空格被判PE。后来我养成了一个习惯把题目给的样例输出复制到文本编辑器里用“显示所有字符”功能看它末尾有没有空格。虽然有点笨但很管用。对于输出格式记住一句话严格照着题目示例来不要自由发挥。5.2 多组输入与EOF必须掌握的循环框架基础题中后段开始频繁出现“输入包含多组测试数据每组以...结束”的描述。处理多组输入的通用框架是int n; while (scanf(%d, n) ! EOF) { // 处理这一组数据 }这里有个容易忽视的坑每处理完一组数据该重置的变量一定要重置。比如求和变量sum、计数器cnt要放在while循环内部初始化不能放在外面。否则第二组数据的结果会把第一组的数据加进去。5.3 调试三板斧打印、注释、分段在这个阶段你不可能每道题都一遍过。调试能力决定了你刷题效率的上限。我的调试流程是在代码里加临时printf把关键中间变量打出来比如循环里的i、数组当前元素、sum的当前值。用题目给的样例去跑逐步核对中间结果和手算结果是否一致。定位到出错的分段后把该段代码单独拎出来测甚至写一个小的测试函数。调通之后把临时printf全部删掉再提交。这个方法听着简单但能解决80%的逻辑错误。不要在代码里猜直接看变量实际值很多时候一眼就能看出问题在哪。5.4 边界测试清单每次提交前我习惯先过一遍这些边界值输入为0或1程序是否还能正确处理输入为最大范围值比如数组长度是1000就测1000数据值是上限就测上限。输入包含多组数据时第一组和最后一组是否正确。字符串数组是否可能在str[MAX]的最后一个下标溢出。用int类型的变量去存乘法结果是否会溢出。这些问题在OJ上是实实在在的WA来源。一个看起来能过的代码往往就是栽在这些边界细节上。6. 常见问题与避坑速查6.1 OJ提交报错类型速查报错类型一般原因建议对策Compile Error语法错误、变量名冲突本地编译过了再提交选对语言Runtime Error数组越界、除零、栈溢出检查所有下标边界排查除以变量的运算Wrong Answer逻辑错误、边界未处理对照样例构造边界测试数据Time Limit Exceeded算法太慢减少循环层数用筛法/哈希替代暴力Presentation Error多余空格、缺少换行把样例输出的空格和换行一个一个数清楚6.2 基础题阶段的高频坑点清单scanf和gets混用缓冲区残留换行导致字符串读不进来。数组开小了越界写不报错但在OJ上表现为WA或RE。int溢出特别是做乘法和累加时注意改用long long。忘记输出换行符导致两个输出粘在一起。没有正确处理“多组输入”每组之间的变量没有重置。题目要求“忽略大小写”却直接比较原字符。读题时漏看“从大到小”“从小到大”“保留两位小数”等修饰词。6.3 卡题时的求助策略卡题超过半小时我建议按这个顺序做回到题目原文一个词一个词地重新读一遍重点关注“输入格式”和“输出格式”两节。手工演算一遍题目给的样例确认自己的输出和标准输出是否真的完全一致。加printf调试检查中间步骤。如果还是不行再考虑看别人的题解。看题解也有讲究。不要直接复制代码先看别人的思路然后合上题解自己写一遍。如果看完题解直接粘贴过去AC了也没多大意义下次遇到同类题照样卡。7. 最后说几点个人体会东华OJ基础74-76题这几道在整个刷题路径里不算难但它卡住过很多人也筛掉了很多人。我在帮学弟学妹改代码时发现一个有意思的规律这个阶段能独立刷过去的人后面学结构体、链表、DFS这些内容的时候普遍不太慌而靠搜题解混过去的人到后面往往又会回来补基础。这个阶段最值得刻意练习的不是某一道题的解法而是“拿到题先想清楚再做”的习惯。我刚刷到这儿的时候也经常拿到题就开写写一半发现思路错了。后来强迫自己在草稿纸上写伪代码把输入、处理、输出三块列出来AC率确实上了一个台阶。我自己现在帮人讲题也是先问对方一句你能用大白话把题目要求说清楚吗能说清楚基本就成功了一大半说不清楚代码写得再漂亮也白搭。这个建议同样送给你刷题路上慢慢体会吧。