如果你正在准备东华大学的机试或者对高校OJOnline Judge在线评测系统的题目风格感到头疼那么“2023东华大学OJ机试题22-70”这一批题值得你花时间好好研究。我今年实际刷完了这批题也带过几个学弟学妹做同样的训练今天就把我踩过的坑、总结出的套路、以及针对典型题目的完整拆解一次说清楚。这篇文章不止是题解汇总更是一份机试备考的实操指南适合正在准备复试、想要系统训练算法基础、或者单纯想搞懂OJ评测逻辑的同学阅读。先说一个很多人容易忽略的点OJ机试题和我们平时在IDE里写代码完全是两个世界。你本地跑通不算数评测机只看你的程序能不能在规定时间内、用规定的输入输出格式稳定地得出正确结果。东华大学这批题从22题到70题恰好覆盖了从“入门语法”到“经典算法”的完整阶梯我刷完之后最大的感受是它不搞偏题怪题但非常考验基本功的熟练度和边界情况的处理能力。1. 内容整体设计与思路拆解1.1 这批题的核心定位从语法巩固到算法入门的过渡带22-70这个题号区间很有意思。它不像1-20题那样纯考if、for、while的语法层面也还没到后面那种动辄需要图论、网络流、线段树的高强度算法题。如果你打开东华OJ的题目列表你会发现这个区间里大量出现的是模拟题、字符串处理、简单排序、数论基础、以及最基础的动态规划模型。我个人的理解是这个区间是出题人专门设计的“分水岭”。基础好的同学做这些题可以快速找回手感基础薄弱的同学也能通过这一批题建立“用程序解决实际问题”的思维模式。它不会让你一上来就面对一个复杂的算法模型发懵但如果你只会背API、不理解和推导这几道题会精准地暴露你的问题。举个例子第30多题附近有一道关于日期计算的模拟题表面上是“给定年月日求星期几”核心考察点其实是闰年判断的完整条件、月份天数的预处理、以及累加过程中是否会溢出或越界。这类题放到LeetCode上就是简单题但在OJ的机试场景里它就是用来筛掉“粗心”和“不严谨”的。1.2 为什么说机试备考一定要刷OJ而不是只刷LeetCode很多同学问我我LeetCode刷了两三百题机试是不是稳了说实话这完全是两个体系。LeetCode的主流模式是“核心代码模式”也就是你只需要补全一个函数输入输出都被封装好了。而OJ机试绝大多数是“ACM模式”也就是你需要自己处理标准输入输出用scanf或cin把数据读进来再用printf或cout把结果打出去。就这一步能把很多只刷LeetCode的同学卡住。更关键的是OJ的评测机对代码的“边界行为”极其敏感。多输出一个空格、少输出一个换行、读取时没有处理多组数据直到EOF、数组开小了导致越界、递归层数太深导致栈溢出这些在LeetCode上可能根本触发不了但在OJ上就是实打实的“Runtime Error”或“Wrong Answer”。东华大学这批22-70题就是帮你把这些“机试专属的坑”一个个踩平。刷完这批题你至少能建立起三个核心能力第一能熟练处理各种输入输出格式包括多组输入、特定终止条件、字符串含空格第二能估算自己算法的最坏时间复杂度判断在1秒或2秒的时间限制下是否可行第三能养成极端数据测试的习惯比如测试0、测试最大值、测试空串。1.3 选择C/C作为主语言的理由如果你去看东华大学OJ上的通过率统计会发现使用C/C的提交数量远远超过Java和Python。这背后有历史原因也有实际考量。最主要的原因是性能。机试的评测机通常不会很豪华一台物理机上要跑大量提交每个题目还有严格的时间限制一般是1000ms到2000ms。同样的算法用C写能过用Python写可能就超时了。尤其是涉及双重循环的模拟题、或者10^6级别的排序题Python的动态类型和解释执行开销会被瞬间放大。但这不代表你不能用Python如果你对Python的优化技巧非常熟悉比如多用sys.stdin.readline而不是input避免不必要的对象创建一部分题也能过。只是从稳妥和普适的角度我强烈建议备考机试的同学掌握C的基础语法和STL标准模板库的基本用法。你不需要精通模板元编程但像vector、string、sort、map、queue、stack这些高频容器必须达到肌肉记忆的水平。2. 核心细节解析与实操要点2.1 输入输出格式的“潜规则”比你想的更严格不管你是刚接触OJ还是已经刷了不少题输入输出格式永远是最容易翻车的地方。东华的这批题里输入格式大概分成三类我逐个说一下它们的特点和应对方式。第一类是单组输入这是最简单的。比如题目说“输入一个正整数n”你直接读就行。关键是第二类多组输入直到文件结尾EOF。这类题通常会写“输入包含多组测试数据每组第一行是一个整数n”或“处理到文件结束”。C标准的写法是int n; while (scanf(%d, n) ! EOF) { // 处理逻辑 }这里有一个非常典型的坑如果你在循环里用了continue一定要先用scanf把本组数据读完再去continue不然残留的输入数据会污染下一组。我就见过很多同学在“判断到某个标志就跳过本组”的题目上反复WAWrong Answer一查代码全是这个原因。第三类是有特定终止条件的输入。比如“输入两个正整数a、b当a和b都为0时结束”。这种题需要你小心处理“0 0”到底算不算一组有效数据。很多题明确说了“0 0表示输入结束不作为测试数据”那就意味着你要在循环开始先判断这两个值是否为结束标记如果是就直接break不能把这一组数据拿去算结果。再来说输出。OJ对输出格式的判定是绝对严格的多一个空格、少一个换行、整型输出成了长整型带了一串数字统统判错。有一条实用经验是“宁可多换行不要多空格”。比如要求“每行输出一个数”那一行结尾的换行是必须的如果要求“两个数之间以空格分隔”那么最后一个数后面不要跟空格最简单的处理方法是先输出第一个数剩下的数用“空格数”的格式输出或者把结果存进容器再统一拼接。2.2 数组和容器的边界与初始化九成的RE根源Runtime Error运行时错误是机试里最让人抓狂的反馈而它绝大多数情况下都指向数组越界。东华这批题里有很多模拟题需要你开数组来存储状态比如模拟一个矩阵、模拟某种序列的变化。很多同学倒在了“数组开小了”或者“数组下标越界”这种低级错误上。核心原则是凡是涉及数组下标一律使用从0开始的索引并且把数组空间开大一点。假设题目说n最大是1000你开一个a[1005]这种余量是必要的。另外如果你要用数组模拟“第1个到第n个”这种逻辑比如1-based我建议直接用a[0]占位不用代码里用a[i]表示第i个省去很多减一加一的头脑体操。另一个高频问题是初始化。OJ评测机每次运行你的程序分配的内存空间里的数据是不确定的也就是说局部数组如果不初始化里面是什么随机值都有可能。如果你忘了初始化但是代码逻辑恰好依赖于数组初始为0那你的程序可能在本机能跑出正确答案提交后却WA。用memset(a, 0, sizeof(a))或者C的vectorint a(n, 0)都是稳妥的选择。2.3 时间复杂度概算别让超时成为你的宿命说到底机试考的不只是“能不能写出来”更是“能不能在规定时间内跑完”。东华OJ的题目通常会指明数据范围比如n ≤ 10^5。看到这个数字你心里应该立刻做一个换算如果算法是O(n^2)那最坏要执行10^10次操作在1秒的时间限制内基本不可能通过如果优化到O(n log n)大约是10^5 × 17 ≈ 1.7×10^6次这就是正常范围。我见过不少同学在一道题上写出了完全正确的算法但因为复杂度太高而TLETime Limit Exceeded。这不是粗心而是缺少“复杂度意识”。刷题时有意识地记录每个题目的数据范围然后在纸上写一下自己的算法复杂度坚持一段时间会形成本能。特别是排序题能用sort就不要手写冒泡能在读入时做前缀和就不要在查询时双重循环。2.4 特殊场景与极端数据从“能跑”到“能过”的最后一公里题目说n的范围是1到1000你的测试样例全是温和的两位数这远远不够。机试评测数据里一定会包含边界值、最大值、最小值、甚至空输入。优秀的刷题者会主动给自己设计“攻击性测试用例”。比如一个求数组最大值的题极端情况就是数组只有一个元素或者所有元素都是负数或者数组长度到达上限。一个字符串处理题极端情况就是空串、字符串只有空格、字符串长度到达上限。如果代码在这些情况下能稳定输出才勉强算这道题过关了。我自己的习惯是写完代码后先用题目给的示例测试再自己构造3到5个边界用例尤其是把“0”“1”“最大值”这些特殊值喂进去。这个习惯让我在东华这批题里少走了很多弯路。3. 实操过程与核心环节实现前面讲了理念这里进入正题。我以22-70这个区间里几道有代表性的题目为例按题型分类来做一次完整的源码级拆解。这些题目的具体文字描述我记不完全但题型和考察点是非常清晰的我也给每道题标注了“题号区间仅供参考”大家实际在做的时候遇到同类题可以直接套用思路。3.1 经典模拟题“多组输入下的数据统计”约22-30区间这类题型的标准描述是输入有多行每行包含若干个整数先给出一个n表示这一组里有多少个数然后求出这组数的和、平均值、最大值、最小值中的某几项。题目不难但它考察的是对输入结束条件的判断、累加求和时的类型选择、以及输出格式的控制。我给出的参考模板是这样#include cstdio int main() { int n; while (scanf(%d, n) ! EOF) { int sum 0, maxv -1000000000, minv 1000000000, x; for (int i 0; i n; i) { scanf(%d, x); if (x maxv) maxv x; if (x minv) minv x; sum x; } printf(%d %d %d\n, maxv, minv, sum); } return 0; }这里有一个值得展开的细节为什么maxv要初始化成-1000000000而不是0因为题目并没有说数据一定是正数如果所有输入都是负数而你把maxv初始化为0那结果就错得离谱。对minv的初始化同理。这是一个极其典型的边界条件问题也是机试判分中非常喜欢埋的雷。还有一个常常被忽略的点累加和的数据类型。如果每一组数很多很多比如n10^5数值范围又大比如每个数最大10^9那么累加和完全可能超过int能表示的范围大约21亿。这种情况下必须使用long long在32位系统上是64位否则你会得到一个看起来莫名其妙的“溢出后的错误结果”。机试中涉及大数求和、乘方、组合数计算第一反应就应该是long long不要犹豫。3.2 字符串处理题“含空格的字符串处理”约40-50区间字符串题是机试的常客东华这批自然也少不了。有一道典型的题目是输入一行字符串可能包含空格要求统计其中某个字符出现的次数或者把其中某些字符过滤掉后逆序输出。这里最大的坑是输入读取方式。如果你用了cin s或者scanf(%s, s)遇到空格就会停止读取那空格后面的内容就全被截断了。要读入一整行含空格的字符串C里应该用cin.getline(s, len)或getline(cin, str)后者需要包含string头文件C语言则用gets(s)虽然不够安全但在OJ环境通常能用或者fgets(s, len, stdin)。针对这类“含空格字符串处理”题目一个标准的读取和遍历框架是#include iostream #include string using namespace std; int main() { string line; while (getline(cin, line)) { // 读入整行包括空格 for (int i 0; i (int)line.size(); i) { // 逐个字符处理 } } return 0; }注意line.size()返回的是无符号类型如果你在循环体里写了line.size() - 1这类代码在size()为0时就会发生下溢变成一个巨大的正数导致循环异常。所以要么把size()的结果强转成int要么在循环前用一个int len line.size();保存长度。这个小细节我在复查代码时经常见到。还有一个很隐蔽的点getline(cin, line)和前面的cin n混用时中间可能会残留一个换行符。如果你先读入一个整数再用getline读字符串第一次getline很可能读到的是那个换行符直接返回一个空串。解决办法是读完整数后加一句cin.ignore()把缓冲区里的换行符吸收掉。这是OJ里“为什么我第一次读到的字符串是空的”这种问题的最常见解释。3.3 排序应用题“结构体排序与多关键字比较”约50-60区间排序是机试的永恒主题。东华这批题里有一道很经典的学生信息排序题输入若干行每行包含学号、姓名、成绩要求按成绩从高到低排序如果成绩相同则按学号从小到大排序。直接用系统自带的sort函数关键在于怎么提供“比较规则”。C的标准做法是定义一个结构体然后写一个自定义比较函数或Lambda表达式#include cstdio #include algorithm #include cstring using namespace std; struct Student { char id[20]; char name[50]; int score; }; bool cmp(Student a, Student b) { if (a.score ! b.score) return a.score b.score; return strcmp(a.id, b.id) 0; } int main() { int n; while (scanf(%d, n) ! EOF) { Student stu[105]; for (int i 0; i n; i) { scanf(%s%s%d, stu[i].id, stu[i].name, stu[i].score); } sort(stu, stu n, cmp); for (int i 0; i n; i) { printf(%s %s %d\n, stu[i].id, stu[i].name, stu[i].score); } } return 0; }这里有两个实际经验分享。第一个是比较函数里“成绩降序、学号升序”这种多关键字排序千万不要写成“返回false就交换”的反向逻辑。sort的比较函数要严格遵循“严格弱序”原则a排在b前面的条件是cmp(a,b)为真。我一般习惯把所有比较规则写成一个完整的逻辑表达式而不是嵌套多个if-else这样读起来更清晰也不容易出错。第二个是用C风格字符串比较时一定要用strcmp不要直接写a.id b.id。因为结构体里的id是字符数组不是string直接比较数组名比较的是两个地址值结果完全随机。如果你嫌麻烦可以改用string id; string name;但这样就不能用scanf读了得先用cin读入。这里本质上是一个“C风格输入 vs C风格输入”的取舍我的做法是审题后统一凡是结构体里全是数字我就用C风格凡是字符串多我就全用C的string和cin绝不混用最大程度避免缓冲区残留问题。3.4 动态规划初阶“最大连续子段和”约60-70区间到了这个区间动态规划开始出现。最经典的入门DP题就是求一个序列的最大连续子段和给定一个整数序列找出一个连续的子序列使它的和最大。这类题如果用暴力枚举起点和终点再求和复杂度是O(n^2)在n稍大的时候会超时。正确做法是线性DP核心状态转移是以当前位置结尾的最大子段和要么是自己单独成一个子段要么是上一个位置的最大子段和加上自己。写成代码很简短#include cstdio #include algorithm using namespace std; int main() { int n; scanf(%d, n); int x, cur 0, ans -1000000000; for (int i 0; i n; i) { scanf(%d, x); cur max(x, cur x); ans max(ans, cur); } printf(%d\n, ans); return 0; }这里最关键的是ans的初始值。如果你把ans初始化为0当所有数都是负数时你会输出0但正确答案应该是那个最大的负数比如序列是-1, -2, -3答案是-1。所以ans必须初始化成一个足够小的负数比如-1000000000对应int范围内的最小值附近或者直接用INT_MIN要包含climits头文件。DP题在机试中的考察重点其实不是“背公式”而是“想清楚状态代表什么”。我在带学弟学妹时经常说如果你能用自己的话解释清楚cur和ans各自表示什么这道题才算真正会了。cur表示“强制以当前扫描到的元素为结尾时能得到的最优子段和”ans表示“扫描到现在为止已经能确定的全局最优子段和”。如果这个逻辑在写之前没有想透写出来的代码一改就错。3.5 数论基础“约数与素数判断”约60题附近数论题在任何OJ题库里都不会缺席。东华这批题里有一个非常常见的题型判断一个数是否为素数或者统计某个区间内素数的个数或者求最大公约数GCD。判断素数最基础的写法是枚举2到sqrt(n)复杂度O(√n)。但如果你需要判断多次比如有T组测试数据每组n最大10^6这个复杂度可能不够用。更稳的做法是预处理素数表也就是“埃氏筛法”核心思路是从2开始把每个素数的倍数全部标记为合数。预先筛好之后每次判断一个数是否是素数就只需要O(1)查表。埃氏筛的参考实现#include cstdio #include cstring const int MAXN 1000005; bool isPrime[MAXN]; void sieve() { memset(isPrime, true, sizeof(isPrime)); isPrime[0] isPrime[1] false; for (int i 2; i * i MAXN; i) { if (isPrime[i]) { for (int j i * i; j MAXN; j i) { isPrime[j] false; } } } }这个写法里有一个非常经典的优化点内层循环从i * i开始而不是从2 * i开始。原因是对于任何一个小于i * i的、且能被i整除的数它一定已经被更小的素数标记过了所以从i * i开始可以减少很多无效操作。这个细节在笔试面试中都是加分项在机试中也能切实降低常数时间。另外一个值得注意的点是i * i在i比较大时可能溢出int。在MAXN不超过10^6的情况下i最大也就1000平方完全在int范围内所以这里没问题但如果你把MAXN扩到10^7级别i * i就可能超过int上限这时需要写成1LL * i * i强制提升为long long再做比较。4. 实战经验与常见问题排查4.1 本地运行正确提交却WA可能是这些原因这个问题几乎是每个OJ刷题者的“老朋友”了。程序在自己电脑上怎么跑都对一上交就判错最可能的三个原因是输入输出格式问题、数据范围问题、未初始化的变量问题。输入输出格式问题最常见比如该输出“Case #1: xxx”但你漏了“Case #”或者冒号后面少了个空格或者大小写不一致。这些细枝末节一旦错了哪怕你的算法完美依然WA。所以我的建议是提交前逐字检查输出格式尤其是英文单词的拼写、大小写、空格位置、换行位置。数据范围问题更隐蔽。你本地测试用的数据都是题目示例那种小数据根本不会触发溢出但评测数据里全是接近上限的数你的int或者long long就会爆掉。所以做题前先看题目给的数据范围不确定时一律用long long。这年头机试里用long long绝对不会被扣分但该用没用就一定会被扣分。未初始化的变量问题在上面的字符串处理和DP题里都提到过。还有一个典型场景是你开了一个全局数组程序里只在满足某个条件时才给它赋值其他分支直接拿来用。这种情况下如果评测数据恰好走了一个你没有赋值的分支数组里的随机值就会导致错误。对策是养成“声明变量时就初始化”的习惯数组一律memset局部变量一律0。4.2 编译错误和运行时错误的高频雷区很多同学一看到“Compile Error”就慌其实这反而是最好解决的错误类型因为OJ通常会给出详细的编译报错信息。常见的原因包括头文件没写全、C代码用了C语言编译器提交、数组长度用了非常量比如int n; scanf(%d,n); int a[n];这种变长数组在某些编译器下不通过、结构体名字和变量名冲突等。我的建议是先在本地使用和OJ相同或相近的编译器标准主流的OJ一般用GNU C 11或17把所有警告当作错误对待。比如-Wall -Wextra能检查出很多潜在问题例如变量未使用、类型转换可能丢失精度等。不要觉得这些是小题大做评测机的编译环境和你本地的IDE完全不同提前用严格模式检查能省下大量调试时间。运行时错误RE的排查思路是先把数组空间加大一倍看错误是否消失然后检查是否可能存在除零、对负数开根号、空容器访问等非法操作。如果这些都没有再考虑是否需要long long。RE这个问题很多时候不是“你的逻辑错”而是“程序在执行的过程中的某个阶段环境不合规”冷静下来逐步排查一般能定位到具体行。4.3 调试技巧不会打日志那就学会“分段输出法”机试环境下你不能用IDE的断点调试所以一套高效的“无IDE调试”方法就很重要。我自己的方法是“分段输出法”在怀疑有问题的代码段前后各加一句printf(check point 1\n)或printf(debug: cur%d\n, cur)观察这些输出在评测数据下是否如预期出现。如果代码在循环里就在每个关键变量的变化处输出值提交后用实际输出和期望输出做对比。虽然这样会多消耗一点时间但远比盲猜快得多。等定位到具体问题再把这些调试输出删掉重新交。有一个小技巧可以在调试输出前面加一个特殊的标记字符串比如//DEBUG_PRINT最后用编辑器的全局替换一次清掉不容易漏删。4.4 常见问题速查表为了让你在面对“东华OJ机试题22-70”这类区间时能快速定位问题我做了一张结合本批题型的速查表供你参考错误现象大概率原因快速排查方案WA答案错误输出格式不匹配逐字核对输出尤其是空格、大小写、Case编号WA答案错误数据范围超出int检查数据范围改long longWA答案错误未初始化变量数组memset变量声明时赋初值WA答案错误多组数据循环中没有正确读完本组检查continue是否残留输入RE运行时错误数组越界扩大数组空间检查下标计算RE运行时错误除零或取模零检查所有除法/取模操作的分母TLE超时算法复杂度过高O(n^2)换成O(n log n)或O(n)预计算TLE超时输入输出用了cin/cout且未关同步使用scanf/printf或加ios::sync_with_stdio(false)CE编译错误头文件缺失或提交语言错误检查头文件确认提交G而非GCC输出“nan”或巨大负数计算过程溢出改用long long并检查中间结果4.5 现场作答的节奏控制机试不只是拼智商最后聊一个很容易被忽略但极其重要的点机试现场的时间分配和心态控制。以东华大学这类高校机试为例一般时间是两个小时到两个半小时题目数量在5到8题不等。你不可能每道题都从容地从头写到尾所以必须分清主次。我的策略是“先易后难先稳后快”拿到题先全部扫一遍把题意最短、思路最清晰的题放到最前面做保证在考试中期就能稳住几题的分数把那些需要较复杂推导的模拟题或DP题放在后面留足思考时间。还有一个细节写每一道题之前先在草稿纸上把核心数据结构和算法流程写出来。不要觉得这是浪费时间它帮你避免“写到一半发现思路跑偏”的尴尬。尤其是矩阵类的模拟题不画图直接写代码十个里面有八个要修修补补。我在做东华这批题时养成了“先小规模模拟一组数据推导出每一步的数组变化再动手敲码”的习惯实测下来正确率提升非常明显。另外务必预留最后10到15分钟做“全局检查”重点检查所有代码是否都按要求输出了最后一行换行、是否有遗漏的return 0、是否有调试输出被复制到正式提交里。这些低级失误一旦发生白白丢分真的很亏。总的来说东华大学OJ机试题22-70这个区间是一段非常适合从“会写代码”过渡到“能过机试”的训练材料。它的题目难度梯度合理覆盖的知识面广而且坑点集中、有代表性。如果你能把这批题刷透不只是掌握了几道题的解法更重要的是收获了一套属于自己的机试方法论——从审题、设计、编码、自测到提交每一个环节都有章可循。这个方法论才是应对任何高校OJ或者线上笔试最值钱的东西。