前两天刚把这组编号为t49-t55的C机试题完完整整复盘了一遍趁着思路还热乎赶紧把每道题背后的知识点、容易踩的坑以及可以直接抄的代码模板整理出来。如果你正在准备C机试或者刚接触算法刷题这组题很值得拿来当作“基础到进阶”的过渡练习——基本都是高频考点过了这一关后续再啃动态规划、并查集这类难题会顺很多。先说下整体感受七道题放在一套卷子里难度是有梯度的从最基础的字符串处理一路拉到BFS搜索中间串了前缀和、排序优化、单调栈、快速幂、链表反转。可以看出命题人想通过这一组题把考生对C基础语法、STL熟练度和算法模板的掌握程度一次摸清。我把每道题的定位、实现细节和验证方法都写在了下面。1. 试题分布与考察逻辑1.1 七道题的知识点画像这组题的编号从t49到t55我按自己做题时的感受给它们画了个知识图谱t49是字符串去重排序核心考STL容器和输入处理。t50是一维区间和查询一看就知道要前缀和不然连续多次询问肯定超时。t51是排序相关重点在交换次数统计和稳定性暴力冒泡只能过小样例。t52是“下一个更大元素”经典单调栈应用。t53是快速幂取模专门考查大数运算和边界处理。t54是单链表反转考指针操作和内存边界。t55是迷宫最短路径标准BFS模板但里面能挖的坑不少。这里的“知识点画像”不是原题复现而是根据机试常见出题风格归纳出的练习方向。实际机试中具体题目表述可能不同但底层解题模型高度重合。你把这七个模型吃透基本就能应对大部分普通机试。1.2 为什么机试偏好这类组合机试和笔试不同笔试还能写点思路拿过程分机试是黑盒评测程序跑不过就是零分所以命题人会刻意选择“思路简单但实现容易翻车”的题目。比如前缀和思路一句话能讲完可有人就是会把下标写反再比如链表反转核心就三行但忘了保存后继指针就会段错误。从命题习惯来看整套卷子一般分三层第一层是t49这类送分题考察STL基本操作目的是让大部分考生能快速拿分稳定心态。第二层是t50到t53需要主动选择更优算法考察时间复杂度的敏感度。第三层是t54、t55涉及手动内存管理和多层状态维护用来拉开分差。所以你看到“t49-t55”这个连续编号时不要以为它们难度一样实际是按“基础-进阶-拔高”排布的。复习时也应该按这个顺序逐个击破。1.3 做题策略模板优先边界先行我做完这七道题最大的收获是考场上最宝贵的不是灵感而是熟练度。t49到t55里面除了t52需要现场分析单调性之外其余题目几乎都有固定模板。前缀和怎么预处理、BFS怎么标记访问、链表反转怎么迭代都是反复写到肌肉记忆里的东西。因此我建议你平时就给自己建一个“模板库”把每个算法的核心代码保存成自己的风格。上考场时不要临时想细节先把模板写出来再根据题目微调。同时每写完一个模板立刻检查三类边界空输入、极端值、单元素场景。这套流程会在后面的章节里反复用到。2. 核心解题思路与C实现细节2.1 输入输出先把数据读利索机试里一大半的崩溃都和输入输出纠缠不清。最常见的是cin/cout与getline混用。如果你前面用cin读了一个整数再想用getline读取带空格的字符串那个残留的换行符会被getline吃掉导致你拿到一个空字符串。我习惯在main函数最前面写这两行ios::sync_with_stdio(false); cin.tie(nullptr);关掉同步之后cin/cout的速度大幅提升足够应付绝大多数机试数据量。代价是不要在同一段代码里混用scanf和cin不然可能出现数据错乱。如果需要读整行比如t49的字符串去重排序我会这样写string s; getline(cin, s);如果前面确实用了cin那就在getline之前加一句cin.ignore()把换行清掉cin.ignore(); // 忽略掉上一个输入后的换行符还有一类高频场景是“多组测试数据直到文件末尾”可以用while(cin x)来循环读入循环体里正常处理。这个写法可以避免用EOF判断时记不住头文件的麻烦。2.2 容器选型STL是朋友别徒手造轮子t49题目如果要求去重并排序最直接的写法是丢进set里红黑树自动完成去重和排序。代码量短出错率低。setchar st(s.begin(), s.end());但你要清楚set的特性底层是红黑树插入和查找复杂度O(log n)内存占用比数组高。如果数据量达到几百万用set可能既慢又占内存这时可以换用“排序unique”的写法sort(v.begin(), v.end()); v.erase(unique(v.begin(), v.end()), v.end());我选择set还是排序去重主要看两点是否需要保持某种特殊顺序以及内存是否吃紧。机试中大部分去重排序题都适用set但如果你对STL的unique很熟排序去重有时更快。另外unordered_map和map的选择也常让人纠结。map有序但查找慢unordered_map无序但哈希查找平均O(1)。机试中默认可以用unordered_系列除非题目明确要求按字典序输出那才需要map或排序兜底。2.3 几个高频算法的代码骨架这组题我最看重的是四个模板前缀和、单调栈、快速幂、BFS。它们分别是“查询类优化”“单调关系”“大数幂模”“图上最短步数”的代表也是机试的常客。前缀和的核心是预处理数组查询时用两个前缀值相减pre[i] pre[i - 1] a[i]; query(l, r) pre[r] - pre[l - 1];单调栈维护一个单调序列用“弹出-记录-压入”三步完成while (!stk.empty() nums[stk.top()] nums[i]) { ans[stk.top()] nums[i]; stk.pop(); } stk.push(i);快速幂把指数拆成二进制循环中不断把底数平方while (b 0) { if (b 1) res res * a % mod; a a * a % mod; b 1; }BFS用一个普通队列先初始化起点然后四方向扩展queuepairint,int q; q.push({sx, sy}); dist[sx][sy] 0; while (!q.empty()) { auto [x, y] q.front(); q.pop(); // 扩展邻居 }只背模板还不够你得训练“看到题面就知道该用哪个模板”的能力。比如看到“多次查询区间和”就想到前缀和看到“右边第一个比它大”就想到单调栈看到“a的b次幂取模”就想到快速幂看到“最短步数/最少操作次数”就想到BFS。这个识别过程做得越快考场上的心态越稳。2.4 边界条件机试的隐形杀手我见过很多同学写代码时主逻辑全对最后却挂在边界上。这组题里几乎每道都有边界陷阱t49如果输入是空串set构造后直接遍历不会有输出但getline前若没处理换行空串就会导致结果全错。t50如果查询区间从0开始pre[l-1]就会变成pre[-1]数组越界。所以前缀和数组我统一从1开始编号。t53如果模数是1任何数对1取模都是0初始化res时应写成1 % m而不是1。t54如果链表只有一个节点或为空反转循环不执行返回pre指针即可但前提是pre一开始是nullptr。t55如果起点和终点重合BFS会在第一次出队时直接返回0这个分支也要保证逻辑正确。养成一个好习惯写完核心逻辑后花一分钟检查“空输入、最小规模、最大规模、单元素”这四类场景。机试多数情况下没有补测时间前面的细心能帮你稳住分数。3. 实操复盘t49-t55逐个击破3.1 t49 字符串去重排序set帮你一次搞定先假设题面是这样输入一行字符串去掉重复字符后按ASCII码升序输出所有不同字符。这题最核心的是读清“去掉重复字符”和“升序输出”。如果你不假思索先排序再手动去重也能做但用set代码最短#include bits/stdc.h using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); string s; getline(cin, s); setchar st(s.begin(), s.end()); for (char c : st) { cout c; } cout \n; return 0; }复杂度是O(n log n)对字符串长度在百万以内都没问题。set的遍历本身就是有序的所以结果天然满足ASCII升序。这里要提醒一句set 会把字符去重但如果你需要保留字符出现次数那就得用mapchar, int了。除了字符去重这题还适合改成“单词去重按字典序”思路一样只是要把set 换成set 输入处理从getline改成while(cin word)。3.2 t50 区间和查询前缀和别贪图暴力假设题面是给定n个数m次询问每次输入l和r输出从l到r的区间和。n和m都是10^5量级。如果每次询问都从l到r遍历一遍复杂度是O(nm)最坏情况10^10次运算直接超时。前缀和的做法是把每个前缀累积和存在pre数组里查询时只做一次减法#include bits/stdc.h using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, m; cin n m; vectorlong long pre(n 1, 0); for (int i 1; i n; i) { long long x; cin x; pre[i] pre[i - 1] x; } while (m--) { int l, r; cin l r; cout pre[r] - pre[l - 1] \n; } return 0; }处理好两个细节第一数组开n1下标从1开始这样l等于1时pre[l-1]是pre[0]正好是0不需要特判。第二累加和可能超过int必须用long long否则数据一大就溢出成负数。这题的变体是二维矩阵的矩形和查询做法是维护二维前缀和四块加减原理完全一样。3.3 t51 排序优化交换次数与冒泡的局限假设题面是给定数组输出将数组按升序排列所需的最少相邻元素交换次数。很多人第一反应是模拟冒泡计数确实可以但n到10^5时就崩了。冒泡排序虽然直观但时间复杂度是O(n^2)。带标志位的优化版在基本有序时能提前退出但最坏仍是O(n^2)所以这里真正适合的是归并排序求逆序对long long merge_sort(vectorint a, int l, int r) { if (l r) return 0; int mid (l r) / 2; long long ans merge_sort(a, l, mid) merge_sort(a, mid 1, r); vectorint tmp(r - l 1); int i l, j mid 1, k 0; while (i mid j r) { if (a[i] a[j]) tmp[k] a[i]; else { tmp[k] a[j]; ans mid - i 1; // 左边剩余元素都比a[j]大 } } while (i mid) tmp[k] a[i]; while (j r) tmp[k] a[j]; for (int p 0; p tmp.size(); p) a[l p] tmp[p]; return ans; }核心是归并排序里右半边的某个元素落到前面去时左半边剩下多少个元素就形成多少个逆序对也就是多少个相邻交换。掌握这个写法后遇到“最少交换次数”相关题不用再逐对模拟。当然如果题目只是让你展示冒泡排序过程那就直接用最朴素的版本但也要加一个swapped标志位。我建议这类题在笔试阶段练习一下机试则优先选O(n log n)方案。3.4 t52 下一个更大元素单调栈的典型应用假设题面是给定一个数组返回一个新数组每个位置存储右边第一个比它大的元素如果没有则填-1。暴力写法是双重循环但n到10^5就超时。单调栈的关键在于利用栈维护一个从栈底到栈顶递减的序列。遍历过程中如果当前元素比栈顶元素大说明当前元素就是栈顶右侧第一个更大的数此时弹出并记录vectorint nextGreater(vectorint nums) { int n nums.size(); vectorint ans(n, -1); stackint stk; for (int i 0; i n; i) { while (!stk.empty() nums[stk.top()] nums[i]) { ans[stk.top()] nums[i]; stk.pop(); } stk.push(i); } return ans; }栈里存的是下标不是值因为你还得知道这个元素在ans中的位置。整个过程每个元素最多入栈一次、出栈一次所以时间复杂度O(n)空间O(n)。这题变式很多比如求“每日温度”要等待几天才能遇到更高温度代码几乎一样只是ans里存的是下标差值。3.5 t53 快速幂取模把大指数拆成二进制假设题面是求a的b次方对m取模a、b、m都可能达到10^18。直接用pow函数或循环相乘都会溢出或超时。快速幂的本质是把b拆成若干个2的幂的和然后边乘边模long long mod_pow(long long a, long long b, long long m) { a % m; long long res 1 % m; while (b 0) { if (b 1) { res (__int128)res * a % m; } a (__int128)a * a % m; b 1; } return res; }这里我用了__int128来做中间乘法防止两个long long相乘溢出。如果你的评测环境不支持__int128可以把乘法替换成“快速乘”原理和快速幂类似只是把乘法拆成加法long long mul_mod(long long a, long long b, long long m) { long long res 0; a % m; while (b 0) { if (b 1) res (res a) % m; a (a a) % m; b 1; } return res; }另一个常被忽略的边界是m等于1任何数对1取模都是0所以res初始化成1 % m这样即使循环不执行返回值也是0而不是1。还有a一开始要取一次模否则后续乘法可能带着大数计算增加溢出风险。3.6 t54 链表反转指针操作的经典假设题面是给定单链表头指针head反转链表并返回新头。这题在数据结构题目里属于“看一遍就会写一遍就错”的典型。主要错误包括忘记保存后继指针、空链表直接访问cur-next以及反转后头指针没有更新。迭代版本的完整代码struct ListNode { int val; ListNode* next; ListNode(int x) : val(x), next(nullptr) {} }; ListNode* reverseList(ListNode* head) { ListNode* pre nullptr; ListNode* cur head; while (cur ! nullptr) { ListNode* nxt cur-next; cur-next pre; pre cur; cur nxt; } return pre; }每次循环第一步必须先保存nxt因为一旦执行cur-next pre原来的next就找不回来了。最后返回值是pre而不是cur因为循环结束后cur是nullptrpre才指向原链表的最后一个节点也就是新链表的头。这个题还可以玩递归版本但递归深度受栈空间限制链表达几万层就比较危险机试建议只用迭代。3.7 t55 迷宫最短路径BFS的无权图最短距离假设题面是给定n*m迷宫S是起点E是终点.是空地#是墙每次能上下左右移动一格求从S到E的最短步数。BFS是这类题的标准解法。它天然满足无权图上最短路径的性质因为队列是先进先出的先压入的节点步数一定不会比后压入的大。我惯用的模板#include bits/stdc.h using namespace std; const int dx[4] {1, -1, 0, 0}; const int dy[4] {0, 0, 1, -1}; int bfs(vectorstring grid, int sx, int sy) { int n grid.size(), m grid[0].size(); vectorvectorint dist(n, vectorint(m, -1)); queuepairint, int q; q.push({sx, sy}); dist[sx][sy] 0; while (!q.empty()) { auto cur q.front(); q.pop(); int x cur.first, y cur.second; if (grid[x][y] E) return dist[x][y]; for (int k 0; k 4; k) { int nx x dx[k]; int ny y dy[k]; if (nx 0 || nx n || ny 0 || ny m) continue; if (grid[nx][ny] #) continue; if (dist[nx][ny] ! -1) continue; dist[nx][ny] dist[x][y] 1; q.push({nx, ny}); } } return -1; }这里的dist数组同时承担“是否访问过”和“最短步数”两个职责。千万不要只用bool数组标记因为你还得知道步数。另外起点终点重合的情况在最开始加判断“如果起点就是终点直接返回0”可以少走一整个队列。这个模板应付普通迷宫题绰绰有余变体包括“可以传送”和“钥匙开门”本质都是在dist基础上多加一层状态。4. 考场常见问题与排查技巧实录4.1 最容易让人抓狂的几个崩溃点我把自己在机试中掉过的坑和常见的症状整理成了一张表遇到类似问题可以直接对号入座症状表现可能原因快速排查方法输出空白或少了第一行cin与getline混用换行符残留在getline前加cin.ignore()或统一用getline程序运行超时数据规模大用了O(n^2)甚至更高先估算数据量立刻换成更优算法段错误或数组越界前缀和下标写成负数链表访问空指针统一从1开始编号操作前检查空指针输出负数或异常大数整型溢出把int换成long long中间乘法用__int128死循环BFS没有标记访问链表反转忘记保存后继打印循环中的关键变量核对终止条件结果差1但思路对边界场景没覆盖比如起点终点重合手推最小样例尤其是单元素或空输入这张表不是罗列而是我每次做完题都会扫一遍的检查清单。宁可多花两分钟检查也别在评测倒计时后懊悔。4.2 一次真实的调试记录拿t55迷宫题来说我第一次实现时把“访问标记”写在了入队之后结果队列里出现大量重复节点随着层数增加程序越来越慢。排查时我先是打印队列大小发现它呈指数增长立刻意识到重复入队接着检查dist[nx][ny]的判断发现自己少写了dist[nx][ny] ! -1。补上这个条件后队列大小立刻恢复正常。这个经验很有代表性BFS里“标记访问”的时机非常关键。最安全的做法是在把节点压入队列的同时更新dist而不是在弹出时更新。因为如果不小心走了一步先回到之前路径等它弹出时发现访问过才丢弃那后面可能已经压入了很多无效节点。机试调试不像平时IDE里可以慢慢打断点我建议多用“打印关键变量”这个手段。比如在循环开头加一行cerr标记一下当前状态等定位后再删掉。4.3 时间复杂度的提前估算方法“会不会超时”这个问题应该在动手写代码前回答。我总结了三条经验第一看数据范围。看到n10^5O(n^2)基本就废了至少要优化到O(n log n)或O(n)。看到n1000O(n^2)反而可能是标准解法不必盲目炫技。第二看循环层数。两层循环嵌套通常意味着O(n^2)三层O(n^3)一旦嵌套层数超过数据规模先想想有没有更优做法。第三用简单运算量估算。现代评测机一秒大约能跑10^8次简单操作10^9可能危险10^10基本必超时。举个例子t53的b是10^18你写一个for循环从1加到b那就算到世界末日也跑不完看到这种数据立马换快速幂。这组题里t50和t53最考验这种估算能力。学会在编码前花30秒算复杂度比写完再优化节省得多。5. 备赛建议从这套题里带走什么本来想再从环境配置讲起比如VSCode里怎么配置C环境、如何设置编译参数但机试真正决定结果的还是题感和模板熟练度。t49到t55这七道题覆盖了字符串、前缀和、排序、单调栈、快速幂、链表、BFS恰好是C机试中最高频的七个基础模块。如果你能把每一类模板默写出来并且知道每个模板的适用边界那大多数机试题目都能稳住。我觉得最有效的备赛路径是先按这套题的顺序逐个写一遍写完之后不看模板再默写一遍重点检查边界处理。然后给每道题想一个变体自己改一改。比如t50改成二维前缀和t52改成“每日温度”t54改成反转前k个节点。这样的变式训练能让你真正掌握底层思想而不只是背代码。还有个小技巧平时刷题时把“易错点”单独记一个文档。比如“前缀和数组要开long long”“BFS入队时就标记访问”“链表反转先保存next”。机试前翻一遍这些短句比临时翻算法书有用得多。个人经验是你写在文档里的警示大概率是上次考试丢分的地方考前看一遍能明显降低重复犯错概率。如果你现在时间有限那就优先把t50、t52、t53、t55这四道题的模板练熟它们是后面进阶算法的基础。t49和t51相对偏基础但也不能掉以轻心因为送分题往往是通过率陷阱越是简单越容易在输入输出上翻车。最后说一件我自己的习惯考场上遇到没思路的题先跳过去做后面的别死磕。t49到t55一共七道顺序做下来如果卡在t52先去做t54、t55可能写着写着就找到感觉了。机试本质是“有限时间内稳定输出”心态越稳发挥越准。希望这篇复盘对你备考有帮助也祝你在下一次机试里顺利拿下每一道题。