1. 这套题在考什么先盘一盘题目背后的能力要求老实说看到26.3.5 t49-t55这种编号很多人第一反应是又一组刷题任务。但等你真的坐下来把这7道题过一遍就会发现这批题目的编排其实很有讲究它不是在单纯堆题目数量而是在有意识地覆盖机试中最常出现的几类算法场景。我个人的判断是这套题对应的训练阶段应该是在基础语法已经过关之后、开始进入算法思维强化期的节点题号的连续性和知识点的递进关系都非常明显。机试和平时写业务代码最大的区别在于它考察的不只是能不能写出来更是在有限时间内能不能高效地写出来。所以t49到t55这7道题表面上是7个独立的小问题本质上是在反复锤炼你的几个底层能力第一能不能快速识别题目背后的算法模型第二能不能在脑内完成复杂度的预判第三能不能用C的STL把这些算法干净利落地实现出来。尤其对于华为OD这类机试场景这三项能力几乎是选拔的硬性标准。这批题目的难度曲线也值得说一下。从t49到t55整体是循序渐进的状态前两三道题偏基础用来帮你热身和建立信心中间几道开始加入思维难度需要你绕个弯才能想到最优解最后两道题则明显在压轴考察的是综合运用能力。这种编排对于备赛练习来说特别好因为你可以清晰地感知到自己在哪个层次上卡住了而不是一上来就被难题打击。另外我想多说一句这套题虽然带着C机试的标签但解题思想其实是语言无关的。你完全可以用Java或者Python去思考问题本身只是最终实现需要落到C上来。因为机试环境大多指定C所以STL的熟练度、指针和引用的使用习惯、内存管理的意识这些东西会在你敲代码的时候真实地影响你的速度和正确率。这也是为什么我在后面的题解里会刻意标注一些C实现细节而不是只讲算法思路。2. 逐题拆解7道题的核心思路、C实现与踩坑记录2.1 t49看似简单的模拟题卡住你的往往是边界条件这类题出现在热身位是有原因的。它通常描述一个业务场景比如统计一批数据中的某种特征值或者按照某个规则处理一组输入你只需要照着题目描述一步步模拟就能做出来。但模拟题有一个共同陷阱边界条件。以一道典型的统计类题目为例题目会给出若干条记录每条记录包含若干字段要求按某个字段聚合后输出统计结果。我见过太多人在这种题上翻车原因不是不会做而是在循环边界或者空数据处理上出了问题。比如如果输入中包含空行怎么办如果某个字段的值为0你的统计逻辑会不会把它误判成无效数据这些细节在题目描述里往往用一句话带过但恰恰是机试判分时最容易埋雷的地方。C实现这类题我的建议是充分用好STL的容器。统计聚合首选std::map或std::unordered_map前者会自动按键排序适合需要有序输出的场景后者查找速度快适合纯计数的场景。如果你不确定输出是否需要有序稳妥起见用map因为机试判题通常比较严格输出顺序错了不会给半分。再说一个非常实用的小技巧读取数据时用getline(cin, line)整体读入再用std::stringstream按空格或者逗号切分这比直接用cin 逐个读入要灵活得多。因为很多模拟题的输入格式并不规整有时候一行内字段数量不固定有时候分隔符是逗号而不是空格用cin 去一个个读会让你在格式适配上焦头烂额。而stringstream配合getline可以让你在不知道确切字段数量的情况下也能稳健地完成解析。#include bits/stdc.h using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); string line; mapstring, int cnt; while (getline(cin, line)) { if (line.empty()) continue; // 关键跳过空行 stringstream ss(line); string key; int val 1; ss key; // 取第一个字段作为key cnt[key] val; } for (auto p : cnt) { cout p.first p.second \n; } return 0; }为什么ios::sync_with_stdio(false)和cin.tie(nullptr)这两行值得每次都写因为机试的数据量往往会比你预期的要大。当输入规模到达几十万行时默认的C流同步机制会拖慢读取速度好几倍而这两行设置可以让你获得接近scanf的读取性能。这算是C机试的第一课输入输出性能不是可有可无的优化而是必须的条件反射。2.2 t50前缀和的经典应用把O(n)查询降为O(1)从t50开始题目开始进入算法思维区。前缀和Prefix Sum是机试最高频的算法之一因为它考察的是你对预处理这一核心思想的理解。很多题目的朴素做法是每次查询都遍历一遍区间复杂度O(n)当前缀和预处理完成之后每次区间求和直接变成O(1)的相减操作。这就像你统计一个月的生活支出如果每次想知道某几天的支出总和都要把每天的数字重新加一遍效率非常低但如果你先算好一张截止到第n天的累计支出表之后任何区间查询都只查这张表快得多。前缀和的核心代码很短但有一个经典细节必须强调数组下标从1开始而不是从0开始。这么做的好处是prefix[i] prefix[i-1] a[i]这个递推式天然成立而且区间[l, r]的和可以直接写成prefix[r] - prefix[l-1]不用去处理下标偏移的问题。这是我强烈建议你保持的习惯因为机试里因为下标从0开始算导致边界错误的人太多了这不是思维能力的问题纯粹是习惯的问题。#include bits/stdc.h using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin n; vectorint a(n 1, 0); // 下标从1开始 vectorint prefix(n 1, 0); for (int i 1; i n; i) { cin a[i]; prefix[i] prefix[i - 1] a[i]; } int m; cin m; while (m--) { int l, r; cin l r; cout prefix[r] - prefix[l - 1] \n; } return 0; }如果你已经掌握了普通前缀和我想再补充一个进阶版本二维前缀和。题目有时候会升级成给你一个矩阵然后多次查询某个子矩阵的元素和。这时候一维的套路不够用了需要维护一个二维的累计表查询时利用容斥原理做加减。这个扩展非常值得提前练好因为它在机试里的出现频率并不低而很多人由于只练了一维版本遇到二维变体就慌了。二维前缀和的公式是prefix[i][j] prefix[i-1][j] prefix[i][j-1] - prefix[i-1][j-1] a[i][j]查询(x1, y1)到(x2, y2)的子矩阵和时结果是prefix[x2][y2] - prefix[x1-1][y2] - prefix[x2][y1-1] prefix[x1-1][y1-1]。这个加上多减的部分的容斥操作是初学者最容易漏掉的一步。我劝你手推一次这个公式彻底搞清楚为什么是加而不是减不然背熟了也容易用错。2.3 t51贪心策略的经典模型排序是关键中的关键贪心算法的题目在机试里属于想到了就很简单想不到就很痛苦的类型。t51这道题大概率是区间问题——比如会议室安排、活动选择、区间覆盖这些经典变体。它们的共同特征是需要通过排序来为贪心策略创造条件。以区间调度问题为例假设有若干场讲座每场有开始时间和结束时间你希望安排尽可能多的讲座且不能有时间冲突。那应该按什么排序是按开始时间排还是按结束时间排答案是按结束时间排。原因是每次选择结束时间最早的讲座可以为后面的安排留出最多的余地。这个结论背后的逻辑是局部最优可以推出全局最优需要仔细理解。如果你按开始时间排会遇到一个开始很早但持续时间很长的讲座导致你后续什么都排不进去这在直觉上就会让你陷入困境。实现上也很直接先把区间按照结束时间排序然后依次遍历如果当前区间的开始时间不早于上一次选择的结束时间就选择它并更新结束时间。这个算法的时间复杂度是O(n log n)瓶颈在排序上后续遍历是O(n)的。#include bits/stdc.h using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin n; vectorpairint, int intervals(n); for (int i 0; i n; i) { cin intervals[i].second intervals[i].first; // 技巧把结束时间放在first这样sort默认按结束时间排序 } sort(intervals.begin(), intervals.end()); int ans 0; int lastEnd 0; for (auto p : intervals) { if (p.second lastEnd) { ans; lastEnd p.first; } } cout ans \n; return 0; }注意我在代码里用了一个小技巧把结束时间存在pair的first字段开始时间存在second字段这样sort默认就会按结束时间排。这个技巧看起来不起眼但在机试场景里非常实用因为它省去了自定义比较器的时间而且不容易写错。如果你非要自定义比较器也完全可以但需要谨慎处理相等区间的排序结果否则可能导致错误。2.4 t52栈的灵活运用别只盯着括号匹配很多人一看到栈就想到括号匹配这没有错但t52大概率会用一个更有迷惑性的包装来考察栈。比如逆波兰表达式求值、单调栈求下一个更大元素、用栈模拟浏览器前进后退等等。这些变体在机试里非常常见因为栈本身是后进先出的结构恰好适合处理这类需要回头看的问题。我自己在机试中遇到最多的栈题其实是单调栈。它的应用场景可以归纳为给定一个序列快速求出每个元素左边或右边第一个比它大或小的元素位置。这道题用朴素的双重循环解法的复杂度是O(n²)在大数据下会超时而单调栈可以做到O(n)。很多同学习惯了暴力枚举一遇到数据范围稍微变大就提交超时然后开始怀疑是不是C性能不够——这往往是算法复杂度的问题与语言本身无关不能把锅甩给C。单调栈的实现思路是遍历每个元素时把栈中所有不满足单调性的元素弹出弹完之后栈顶元素就是当前元素要找的答案最后再把当前元素入栈。整个过程每个元素最多入栈一次、出栈一次所以总体是线性的。这个算法一定要亲手画几遍流程光看别人的代码理解不会深刻。#include bits/stdc.h using namespace std; // 找每个元素右边第一个比它大的元素的下标 vectorint nextGreater(vectorint nums) { int n nums.size(); vectorint res(n, -1); stackint st; // 栈中存下标 for (int i 0; i n; i) { while (!st.empty() nums[st.top()] nums[i]) { res[st.top()] i; st.pop(); } st.push(i); } return res; }这里有个重要的细节栈中存的是下标而不是元素值。为什么要存下标呢因为当你要把答案写回结果数组时需要知道是哪个位置被解决了光存值你找不到对应的下标。这个存下标的习惯在单调栈、单调队列这类题目中统一适用建议直接形成条件反射。2.5 t53质数判定与优化从朴素到筛法的思维跃迁质数相关的题目在机试里很受欢迎因为它的切入点非常多而且能很好地区分会写代码和懂算法的人。朴素判断单个数是否是质数很简单从2遍历到sqrt(n)看有没有能整除的。但题目一旦变成统计区间内所有质数的个数朴素的单点判断就会在数据量稍大时超时。这就要用到埃拉托斯特尼筛法也叫埃氏筛。核心思想是如果一个数是质数那么它的倍数一定不是质数。所以从2开始把2的所有倍数标记为合数然后找到下一个未被标记的数3它是质数再把3的所有倍数标记为合数以此类推。这个算法的时间复杂度是O(n log log n)对于1e6甚至1e7范围的数据都能在可接受时间内跑完。#include bits/stdc.h using namespace std; vectorbool sieve(int n) { vectorbool isPrime(n 1, true); isPrime[0] isPrime[1] false; for (int i 2; i * i n; i) { if (isPrime[i]) { for (int j i * i; j n; j i) { isPrime[j] false; } } } return isPrime; }注意一个细节内层循环从i * i开始而不是从2 * i开始。这是因为比i²小的i的倍数比如2i, 3i, ..., (i-1)i在更早的轮次中已经被其他质数标记过了不需要重复遍历。这个优化能把时间复杂度再降低一个层级。如果你愿意进一步优化还可以学线性筛也就是欧拉筛每个合数只被它的最小质因子筛掉一次时间复杂度严格O(n)。但作为机试来说埃氏筛已经完全够用不需要过度追求线性筛。2.6 t54快速幂二分思想的一次深刻体现t54大概率会考察快速幂。它的目标很单纯高效计算a^b mod p。最容易想到的方法是循环连乘b次循环复杂度O(b)。但如果b的规模是1e18呢这在机试数据里是随随便便就能出现的情况连乘法会直接超时到无法接受。快速幂的核心思想是把指数b看成二进制然后用平方累乘的方式减少运算次数。就好比你要算2的10次方不一定非得乘9次可以先把2平方得到4再把4平方得到16这样指数增长的速度非常快。4^5 (2^2)^5 2^(10)原本的9次乘法可以拆成几次平方和几次乘法组合。标准的快速幂实现如下long long fastPow(long long a, long long b, long long mod) { long long res 1 % mod; a % mod; while (b 0) { if (b 1) { // 当前二进制位为1 res res * a % mod; } a a * a % mod; // 平方底数 b 1; // 指数右移 } return res; }理解这个代码,关键在if (b 1)这个判断。它就是检查b的二进制表示中的最低位是不是1。如果是就把当前的a乘到结果里然后无论如何都要把a平方再把b右移一位。比如计算3^55的二进制是101从低位开始第一位是1乘一次第二位是0不乘第三位是1再乘——实际上一共就做了两次乘法中间穿插了平方运算。这道题容易出错的地方有两个一个是mod1时的边界此时任何数模1都等于0所以res的初始值必须是1 % mod而不是直接写成1否则答案会错另一个是乘法溢出如果在计算res * a或a * a时超出了long long的范围你需要借助__int128或者拆分成多次乘法来处理。这两个坑都是我实测踩过的教训非常深刻。2.7 t55综合性模拟检验语法细节和调试能力的试金石最后一题通常是综合性最强的可能在单道题里同时用到排序、查找、字符串处理甚至简单的数据结构组合。它的典型特征是题目描述很长数据格式很复杂让你感觉到这道题没有明显的算法模型更考验的是阅读理解 结构化编程能力。应对这类题我有一套固化的流程分享给你参考。第一步仔细读题把它要求的输入输出格式、特殊规则逐条列出来不要遗漏任何约束条件。第二步拆解功能模块把读入→解析→处理→输出四个环节分开不要揉在一起写。第三步为每种数据结构先设计好存储方式尽量避免用字符串切片的方式处理结构化数据优先考虑结构体。比如题目要求处理一组包含姓名、学号、三科成绩的记录然后按总分排序再按名次输出。很多新手会直接用三个数组分开存这些信息然后排序时手写复杂的交换逻辑一旦代码变长就越写越乱。正确做法是定义一个结构体把三个字段打包在一起再用vectorStudent配合自定义比较器排序清晰且不容易出错。#include bits/stdc.h using namespace std; struct Student { string name; string id; int s1, s2, s3; int total; }; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin n; vectorStudent stu(n); for (int i 0; i n; i) { cin stu[i].name stu[i].id; cin stu[i].s1 stu[i].s2 stu[i].s3; stu[i].total stu[i].s1 stu[i].s2 stu[i].s3; } sort(stu.begin(), stu.end(), [](const Student a, const Student b) { if (a.total ! b.total) return a.total b.total; return a.name b.name; // 总分相同按姓名排序 }); for (auto s : stu) { cout s.name s.total \n; } return 0; }Lambda表达式定义自定义比较器是这种场景下最简洁的写法。但要特别提醒比较器必须满足严格弱序也就是说不能出现a b和b a同时为真的情况。如果两个元素完全相同比较器必须返回false否则sort会崩溃。这是一个极其隐蔽的坑一旦触发可能连报错信息都看不懂。3. 机试必备的C代码模板与优化习惯看完这7道题的题解我想单独拿出一节来聊机试中共通的核心技巧。这些内容不针对某一道题但每一道题都会用到。它们是我多年刷机试题、参加各类机考沉淀下来的“肌肉记忆”同样适合所有正在备考机试的读者。首先要说的是万能头文件。C 的#include bits/stdc.h在机试环境中通常可以使用它一次性引入了STL的所有头文件省去了一个个敲vector、algorithm、string的麻烦。但在某些严格的企业机试环境或GESP认证环境中这个头文件可能不被支持稳妥起见你需要确认考场环境。如果环境不支持那就要老老实实逐个引入。这个知识点在热词里也出现了“vscode配置c/c环境”和“c项目”等内容配置环境时最好提前测试这个头文件能不能用。其次是输入输出优化。前面已经提到过ios::sync_with_stdio(false)和cin.tie(nullptr)这里再展开说一下背后的原理。默认情况下C的cin/cout需要和C语言的stdio同步以确保混用printf和cout时输出顺序不出乱子。但这个同步机制会带来额外开销。机试中你通常只会用cin/cout或只会用scanf/printf没必要维持同步关掉它就能获得显著的性能提升。这是一个近乎零成本的优化建议每次刷题都写上让它成为你肌肉记忆的一部分。第三个值得强调的是容器选择。STL里的容器各有适用场景不要无脑用vector或者无脑用list。频繁在容器中间插入删除用list频繁在尾部尾删且需要随机访问用vector需要按键查找用map/unordered_map需要去重且有序可以用set。机试题目通常内存限制比较宽松但时间复杂度卡得很紧容器选错会导致你在不该超时的地方超时冤枉得很。第四个是关于栈和堆的使用。机试中经常有递归函数如果递归深度超过几十万层默认的函数调用栈可能会溢出。这种情况下你有两个选择一是改为显式的栈模拟二是把递归函数改写为迭代版本。比如在DFS遍历图时如果图规模很大递归版本非常容易爆栈这时候我建议直接用stack来模拟递归过程。虽然代码会稍微复杂一些但在数据范围大的题上更稳妥。第五个是我个人特别推荐的习惯把常用的算法封装成独立函数或模板。比如快速幂、质数筛、前缀和计算这些提前写成现成的函数放在代码模板里考场上直接调用而不是现场再手写。这样省出的不只是打字时间更多是降低出错概率。在时间极其宝贵的机试里不出错比写得快更重要因为一次Wrong Answer的排查代价可能在十分钟以上。4. 机试实战中的常见错误与排查技巧机试不像平时开发没有调试器可用的场景也很常见你得靠读代码和加输出来定位问题。这里我把自己常踩的几个坑分类整理了出来每一个都已经被无数人验证过提前知道就能帮你在考场上少走弯路。第一类是输入读取不完整。如果你用cin x读取数据但输入里混着换行符或空格cin 其实会自动跳过空白所以不会出问题。但如果你用getline去读取就要小心getline会吃掉行尾的换行符而它前面的cin 则会把换行符留在输入缓冲区里。这会导致下一次getline直接读到一个空行从而让整个数据解析错位。解决办法是在cin 和getline之间加一次cin.ignore()清除残留的换行符。第二类是数组越界。这个问题听起来低级但在机试的紧张状态下极其容易发生。尤其是当你想用某个数组下标去访问元素却不小心把循环的边界多写了1或少写了1的时候。C的数组越界行为是未定义的可能不会立刻崩溃而是悄悄覆盖了相邻内存的数据导致输出结果诡异且难以复现。我的建议是如果你知道数据规模不超过1e5就用vector并提前resize好容量如果你必须用原生数组那么在写循环边界时反复检查三次或者在草稿纸上把索引的推导过程写清楚。第三类是整数溢出。当题目数据范围达到1e9甚至1e18时int类型就装不下了。很多新手在写累加或者乘法时用的是int等到输出变得异常才意识到溢出问题。我建议在机试中养成这样的习惯凡是可能涉及较大数值的变量一律用long long哪怕暂时看起来不会超过int范围。这个习惯能帮你避免一类非常隐蔽的错误而且几乎不会带来性能上的负面影响。第四类是多组数据的清空问题。机试题目经常是多组测试数据模式每一组数据开头会给出组数或循环条件。很多人会在第二组数据开始后发现结果不对原因往往是容器里残留了上一组数据的旧值。解决方法是每一组数据开始时手动clear()相关容器或者把容器声明在循环内部让它在每次迭代中自动销毁和重建。第二种方式更干净推荐优先使用。第五类是排序规则的返回值陷阱。自定义比较器时返回值true表示前者应排在后者前面false则表示不交换。这个逻辑在sort函数里和常人的直觉可能不一致——如果你想让小的在前应该返回a b想让大的在前应该返回a b。很多新手会在这里写反导致排序结果完全颠倒却不自知。更隐蔽的错误是当a和b相等时比较器必须返回false如果你写成return a b就会造成未定义行为——注意在这个比较逻辑下可能让程序在数据量变大时整体崩溃且崩溃原因非常难定位。5. 时间分配策略与模拟训练方法机试不仅是会不会的问题更是快不快和稳不稳的问题。我在备考的时候逐步找到了一套适合自己的时间分配方法这套方法在近年的机试训练中被反复验证过这里分享给你参考。做题顺序上我坚持一个原则先易后难绝不恋战。拿到试卷后先把所有题目快速浏览一遍对每道题的难度做一个初步评估。如果有数据范围很大、题目描述特别冗长、一眼看不出算法模型的题先跳过把前面能快速做对的题先稳稳拿下。机试的计分方式通常不会因为跳过简单题而去奖励难题所以基础分必须优先保证。时间分配上我大概会按这个比例来规划前30%的时间用来做热身题和确保已经完成题目的正确性中间50%的时间集中攻克中等难度的题最后20%的时间如果还有剩余再回头冲击难题或者复查前面提交的代码。有人喜欢一开始就直接挑战最难的那道题觉得分值高收益大但我不推荐这种做法。因为机试的紧张气氛下心态很容易崩一旦难题卡住后面的简单题也会因为时间不足而失误得不偿失。模拟训练的频率也很关键。我的建议是至少每周安排一次完整的模拟机试时间严格卡在正式考试的规格上比如2小时7道题。模拟时必须使用和考场一致的编译环境与代码模板不要私下用本地调试器一步步跟。这个模拟的逼真度决定了你上考场时的状态切换成本。平时习惯了环境的舒适考场上环境变化就会放大紧张感导致发挥失常。在模拟中我会刻意训练读题→建模→编码→自测的完整闭环尤其是自测环节不能少。很多同学写完代码就直接交也不自己造几组测试数据验证一下结果因为边界情况扣分。正确的自测方式并不复杂拿到题目后先根据题意构造几组极端数据比如最小值、最大值、空输入、单元素输入、逆序输入等等在本地跑一遍确认输出正确再提交。这组自测数据不需要多每组题目4到6个用例就足够覆盖绝大多数坑了。6. 备考路线与长期训练建议如果你不只是想在考前突击而是希望把机试能力真正练扎实那需要有一个更长线的规划。我个人建议把备考周期分成三个阶段。第一阶段是基础语法与套路积累期大约需要两到三周。这个阶段的核心任务是熟悉C的基本语法、STL常用容器和算法库函数。我这里特别推荐把algorithm里的sort、reverse、unique、lower_bound、upper_bound、max_element、min_element这类常用函数都用熟因为在机试中用它们可以减少大量手写代码的时间和出错概率。第二阶段是算法专题突破期大约需要四到六周。把上面那类高频算法逐个击破——前缀和、差分、双指针、二分答案、贪心、动态规划入门、搜索DFS/BFS、图的最短路和最小生成树、常见数论质数筛、快速幂、最大公约数这些是机试题库中出现频率最高的内容。每学一个新算法都要亲手实现至少三到五道对应的练习题不能只看答案不敲代码。算法的理解程度是用代码量堆出来的不是用阅读量堆出来的。第三阶段是综合实战期持续到考前。这个阶段不再按知识点刷题而是整套整套地做真题或模拟题训练自己在限定时间内统筹安排的能力。同时这个阶段还要建立自己的错题本把每次模拟中出错的知识点、易混淆的代码习惯记录下来。考前翻一遍错题本效果远比临时刷新题来得实在。归根结底机试的本质是一场用代码表达思路的考试。算法思想是内核C只是表达工具但工具的熟练度会严重限制你思想的展开速度。我的切身体会是那段时间每天刷题、总结、再刷题虽然累但当你发现自己看到题目描述就能在几秒内判断出该用什么算法时那种手感会让你觉得所有的努力都是值得的。这套t49到t55的题目整体质量很不错能帮你把机试中最核心的几类模型做一次集中的检验。如果你能把这7道题从思路到代码都吃透我相信你在机试中会比大多数人更从容。