机试刷题有个分水岭。前30题练的是语法熟练度到了31~40这个区间题目开始变成“阅读理解加算法选型”同一道题你用暴力可能也能过样例一交上去才知道超时或者漏了边界。这次想聊的是机试在线训练C版第31到40题覆盖字符串处理、栈与递归、BFS、贪心和动态规划这五个高频方向。准备机试的人可以直接拿来做训练刚学完C想巩固算法的人也可以从这组题里找到适合自己的节奏。1. 先看整体这组题的考点地图与刷题顺序1.1 机试判题规则里最容易忽略的细节在线训练平台和平时自己写Demo最大的区别在于评测机只看输入输出而且测试用例远不止题目里给的样例。你本地跑一遍没问题不代表提交后能AC。超时、内存越界、多组输入没读完、输出多了个空格这些坑我都踩过一遍。平台常见的限制是1秒时间、几十到几百MB内存。1秒能跑的量级大概是n在10^7以内时O(n log n)的算法可以稳过如果n10^5O(n^2)基本就会超时。所以拿到题第一件事不是写代码而是看数据范围这直接决定你用什么思路。比如n只有100那暴力枚举和动态规划都能过一旦n10^5暴力的双循环就彻底没戏。输入输出格式也要提前确认。很多题是多组测试直到EOF写法是while (cin n)有的是单组输入那直接读就行。最容易翻车的是读含空格的字符串cin s读到空格就停了必须用getline(cin, s)。如果前面刚用cin 读过一个整数后面接getline时得先用cin.ignore()把残留的换行符清掉否则读到的就是一个空行。这个细节我见过太多人在机试现场卡了十分钟。1.2 十道题的分类与优先级我把这十道题按考法和难度排了个表方便你安排刷题顺序。需要说明的是这组题不是让你背原题机试每年都在更新按考点方向练才有意义。题号核心考点难度训练重点31字符串去重与排序简单含空格输入、有序容器选择32最长连续递增子段简单一次遍历、避免过度设计33括号匹配简单栈的标准使用与边界判断34高精度加法简单到中等字符串模拟、进位处理35完全数统计简单因子枚举到根号、防超时36单词倒排简单到中等字符串切分、标点处理37前中序重建二叉树中等递归切分、层序BFS380-1背包中等一维滚动数组、循环顺序39区间合并中等排序、贪心边界判断40迷宫最短路径中等BFS模板、状态记录我的建议顺序是先做31、32、35热身把输入输出手感找回来再做33、34、36然后进入37和40最后花精力啃38和39。字符串和模拟题能帮你熟悉各种输入陷阱栈和搜索放在中间练模板动态规划和贪心最吃逻辑留到最后脑子清醒的时候刷。2. 字符串与模拟题的三道实战去重排序、大数加法、单词倒排2.1 题31字符串去重并排序——set与标记数组怎么选题目描述差不多是这样输入一行可能包含空格的字符串去掉其中重复的字符空格不参与按ASCII码升序输出剩余字符。比如输入hello world输出就是dehlorw。看到“去重加升序”第一反应是setchar因为set天然有序且自动去重。但要注意读入方式#include iostream #include set #include string using namespace std; int main() { string s; getline(cin, s); // 必须读整行cin 读到空格就停 setchar st; for (char c : s) { if (c ! ) st.insert(c); } for (char c : st) cout c; cout endl; return 0; }set底层的红黑树让插入是O(log n)整体O(n log n)。但字符集最多就128个可见字符用bool vis[128]标记更轻量一趟扫描O(n)搞定连排序都省了因为ASCII本身就是有序的bool vis[128] {false}; string res; for (char c : s) { if (c ! !vis[c]) { vis[c] true; res.push_back(c); } } // res 本身按字符第一次出现顺序排列若要升序再 sort 一下这道题有两个非常隐蔽的坑。第一ASCII码顺序和字典序不一样大写字母在小写字母前面比如Z的ASCII是90a是97所以Z会排在a前面。题目说“按ASCII升序”就是按码值排别想当然按字典序。第二如果题目改成“去除重复后保持原顺序输出”那set完全不能用得换成上面的“标记数组加结果字符串”方案。2.2 题34高精度加法——模拟竖式的进位处理这道题给的数字可能大到几十位甚至上千位int和long long全都不够用标准做法是用字符串模拟竖式加法。输入两个字符串输出它们的和。string addStrings(string a, string b) { reverse(a.begin(), a.end()); reverse(b.begin(), b.end()); string res; int carry 0; for (int i 0; i a.size() || i b.size() || carry; i) { int sum carry; if (i a.size()) sum a[i] - 0; if (i b.size()) sum b[i] - 0; res.push_back(sum % 10 0); carry sum / 10; } reverse(res.begin(), res.end()); return res; }简单说一下思路从最低位开始逐位相加每一位的结果写进res进位保留到下一轮。循环条件里加了|| carry是因为最高一位相加后可能多出一个进位比如99 1 100最后必须多处理这个最高位的1。这里要提醒的是反转字符串后别忘了输出前再反转回来这是很多人写着写着就丢掉的步骤。另外输入可能带前导零比如00123不影响加法逻辑但如果你还写了删除前导零的代码要注意空串的情况。这类模拟题在机试里出现频率很高本质上考的就是“把现实规则转换成代码”的能力大数只是载体。2.3 题36单词倒排——字符串切分的边界问题题目给一个英文句子单词之间用空格或标点分隔要求把单词按倒序输出标点不要了。输入I am a student.输出student a am I。我的做法是先把所有非字母数字的字符替换成空格再用istringstream按空格切词#include iostream #include sstream #include vector #include string using namespace std; int main() { string line; getline(cin, line); for (char c : line) { if (!isalnum(c)) c ; } istringstream ss(line); vectorstring words; string w; while (ss w) words.push_back(w); for (int i words.size() - 1; i 0; i--) { cout words[i]; if (i 0) cout ; } cout endl; return 0; }isalnum会判断字符是否是字母或数字标点全部变成空格。连续多个空格由istringstream自己跳过不用手动处理省了很多事。真正容易失分的是输出格式。如果句子是空的或者全是标点那words是空的循环直接跳过最终输出一个换行这没问题。但如果一个单词都没有时你多打了一个空格评测系统就会判格式错误。我的习惯是提交前把“空输入”“只有标点”“单词间多个空格”这几种边界情况都本地跑一遍确认不会多输出空格。3. 线性结构与递归括号匹配和二叉树层序重建3.1 题33括号匹配——栈的经典应用与易错分支输入一串只包含()[]{}的字符串判断括号是否匹配。栈的标准用法就是为这道题准备的左括号入栈右括号弹出栈顶检查配对。#include iostream #include stack #include string using namespace std; bool isValid(string s) { stackchar st; for (char c : s) { if (c ( || c [ || c {) { st.push(c); } else { if (st.empty()) return false; char top st.top(); if ((c ) top ! () || (c ] top ! [) || (c } top ! {)) { return false; } st.pop(); } } return st.empty(); }需要注意两个失败分支一是右括号多出来了遍历到某个右括号时栈已经空了二是左括号多出来了全部遍历完栈还没空。这两个都要判false。还有一个反直觉的边界空字符串算合法匹配因为没有任何不匹配的括号直接返回true就行。如果括号只有一种比如只有小括号那可以用一个计数器遇到左括号加一右括号减一任何时候不能为负最终为0就合法空间O(1)。但括号种类一多计数就无法处理嵌套配对关系了这时候栈就是唯一正确的选择。机试里这种“看起来很简单但陷阱藏在边界”的题特别容易在紧张时翻车。3.2 题37前中序重建二叉树并层序输出——递归与队列的配合这道题把两个知识点结合在了一起给定二叉树的前序遍历和中序遍历序列重建二叉树再输出层序遍历结果。前序序列第一个节点就是根在中序序列里找到这个根左边全是左子树节点右边全是右子树节点然后递归下去。用哈希表记录中序序列每个值的位置能让每次定位根的时间从O(n)降到O(1)。核心递归代码大概是这样TreeNode* build(int pl, int pr, int il, int ir, vectorint pre, unordered_mapint,int mp) { if (pl pr) return nullptr; TreeNode* root new TreeNode(pre[pl]); int pos mp[pre[pl]]; int leftLen pos - il; root-left build(pl 1, pl leftLen, il, pos - 1, pre, mp); root-right build(pl leftLen 1, pr, pos 1, ir, pre, mp); return root; }这里最关键的一步是leftLen pos - il也就是左子树有多少个节点。很多人在推右子树前序起点时忘了加这个长度直接写pl 1导致区间错位越界。递归本身不好调试一旦下标算错运行结果就是乱序或者崩溃。建好树之后层序输出就是标准BFS队列里先放根节点每次弹出节点访问然后把左右孩子依次入队。层序的天然顺序就是队列的先进先出和递归、深搜是完全不同的遍历逻辑我经常把“前中序重建”和“层序遍历”放一起练就是为了一次同时过掉递归和队列两个点。4. 搜索与图论BFS模板和迷宫最短路径4.1 题40迷宫最短路径——为什么BFS第一次到达就是最短题目给一个M行N列的迷宫0代表可以走1代表墙从左上角(0,0)出发每次只能上下左右走一步求到达右下角(M-1,N-1)的最少步数。只要碰到“最短步数”第一选择就是BFS。BFS按层次向外扩展像水面波纹一样一圈一圈荡开。同一层的格子步数相同先碰到的格子一定比后碰到的格子更早入队。所以第一次到达终点时记录的步数就是最短路径长度。这是BFS和DFS最大的区别DFS能找出一条路径但不保证最短BFS第一次找到的一定最短。#include iostream #include queue #include cstring using namespace std; int main() { int M, N; cin M N; int grid[105][105]; int dist[105][105]; memset(dist, -1, sizeof(dist)); for (int i 0; i M; i) for (int j 0; j N; j) cin grid[i][j]; int dir[4][2] {{1,0},{-1,0},{0,1},{0,-1}}; queuepairint,int q; q.push({0, 0}); dist[0][0] 0; while (!q.empty()) { auto [x, y] q.front(); q.pop(); if (x M - 1 y N - 1) break; for (int k 0; k 4; k) { int nx x dir[k][0]; int ny y dir[k][1]; if (nx 0 || nx M || ny 0 || ny N) continue; if (grid[nx][ny] 1) continue; if (dist[nx][ny] ! -1) continue; dist[nx][ny] dist[x][y] 1; q.push({nx, ny}); } } cout dist[M - 1][N - 1] endl; return 0; }dist数组初始化为-1这样同时承担了“是否访问过”和“当前步数”两个职责少维护一个visited数组代码更干净。一定要记得在循环里判断越界和墙壁很多人写着写着把nx M写成nx M边界就漏了。如果题目要求多组输入队列和dist都要在每组数据开始前重新初始化否则上一组数据的状态会污染下一组。起点本身就是墙、起点和终点重合这两个极端情况也值得单独测一下后者应该输出0。4.2 BFS模板的变体与DFS的取舍BFS模板背熟了之后要能快速改造成不同场景。比如把四邻域改成八方向只需要把dir数组扩成8个方向如果要求输出路径本身那就加一个parent数组记录每个格子的前驱节点最后从终点逆推回起点。这些变体都是在模板上加减核心框架不变。DFS在机试里也有它的位置尤其是连通块统计、排列组合、迷宫是否存在路径这类问题。但DFS用递归实现时要注意递归深度如果迷宫有几千行几千列递归深度可能超过系统栈限制导致栈溢出这时候要么改用BFS要么手写显式栈。我的经验是问最短路径、最小步数别犹豫直接BFS问连通块数量、是否存在某种排列DFS通常更顺手两者都能做时优先写BFS因为它天然避免递归深度问题。5. 从枚举到贪心再到DP别一上来就套模板5.1 题35完全数统计——枚举到根号就能过完全数的定义是真因子之和等于自身。比如6的真因子是1、2、3加起来正好等于6。题目给一个n统计1到n范围内完全数的个数。思路并不复杂对每个数x枚举因子求和。但很多人会写成for (int i 1; i x; i)这在n稍微大一点时就直接超时。正确做法是枚举到根号x因子是成对出现的bool isPerfect(int x) { if (x 1) return false; int sum 1; // 1 是所有大于1的数的最小真因子 for (int i 2; i * i x; i) { if (x % i 0) { sum i; if (i ! x / i) sum x / i; } } return sum x; }这里有个细节如果i * i x说明i和x/i是同一个因子只能加一次。如果你写循环时加了两遍判断就错了。1的真因子和是0不等于自身所以不算完全数要单独排除。这种题不值钱但它考察的习惯很有价值机试超时很多时候不是算法不会而是“只需要枚举到根号”的地方写成了“枚举到x”。优化不一定需要高级数据结构先看能不能缩小枚举范围这个意识比背十个模板都重要。5.2 题380-1背包——一维滚动数组的循环顺序背包问题是动态规划里最经典的入门题。有N件物品每件物品有重量w[i]和价值v[i]背包容量为V求能装下的最大价值。每件物品只有拿或不拿两种状态所以叫0-1背包。二维dp的状态定义是dp[i][j]表示前i件物品在容量j下能获得的最大价值转移方程是拿或不拿取最大值。但机试更常用的是空间压缩后的一维数组vectorint dp(V 1, 0); for (int i 0; i N; i) { for (int j V; j w[i]; j--) { dp[j] max(dp[j], dp[j - w[i]] v[i]); } }这里最核心的问题是内层循环为什么必须从大到小因为一维数组复用空间时如果从前向后更新dp[j - w[i]]可能已经是第i件物品被放入后的新值这样第i件物品就可能被选多次变成完全背包。倒序更新保证dp[j - w[i]]还是上一轮循环的旧值这才是0-1背包。初始化方式也要看清题意。如果只是“求最大价值”全部初始化为0即可如果要求“恰好装满背包”那dp[0] 0其他值初始化为负无穷表示没有合法方案。这两个初始化导致的结果差异很大题目问法要反复确认。5.3 题39区间合并——贪心的排序依据和边界判断题目输入若干区间比如[1,3]、[2,6]、[8,10]输出合并后不重叠的区间列表。思路是按起点升序排序然后逐个合并。vectorpairint,int merge(vectorpairint,int intervals) { if (intervals.empty()) return {}; sort(intervals.begin(), intervals.end()); vectorpairint,int res; int curL intervals[0].first; int curR intervals[0].second; for (int i 1; i intervals.size(); i) { if (intervals[i].first curR) { res.push_back({curL, curR}); curL intervals[i].first; curR intervals[i].second; } else { curR max(curR, intervals[i].second); } } res.push_back({curL, curR}); return res; }为什么要按起点排序而不是终点合并的本质是“当前区间能否向右扩展”只有起点有序才能一次性从左到右扫描完所有可能出现重叠的区间。如果按终点排序合并逻辑就乱了。有几个边界要特别注意第一[1,4]和[5,6]严格来说没有重叠上面的代码里5 4所以不会被合并但如果题目规定“连续也算合并”那判断条件要改成。第二区间可能完全包含在另一个区间内比如[1,10]和[2,3]合并时curR max(curR, intervals[i].second)这个写法能正确处理不会把10缩小成3。第三最后一个合并区间在循环外要再push一次容易漏。区间合并经常和“活动安排”放在一起对比。活动安排是选最多不重叠的活动按结束时间排序贪心选择最早结束的活动区间合并不是选择而是全覆盖合并必须按开始时间排序。这两个问题一字之差解法完全不同我自己就曾经混淆过。5.4 题32最长连续递增子段——最长不一定要用DP输入一个序列求最长连续递增子段的长度。比如1 3 5 4 7最长连续递增的是1 3 5长度3。int ans 1, cnt 1; for (int i 1; i n; i) { if (a[i] a[i - 1]) cnt; else cnt 1; ans max(ans, cnt); }这题看起来简单但它的陷阱在于很多人一看到“最长”两个字条件反射开始写动态规划反倒把简单题做复杂了。关键要分清“连续递增”和“递增子序列”的区别。连续递增只需要一次遍历递增子序列可以不连续才需要DP或者DP加二分。机试经常用这种改一个词就换解法的题来考察你是否真正理解算法本质。如果你在做题时发现一个解法需要大量状态和转移方程不妨先停下来问自己这题真的需要吗有时候一个变量就能搞定的事上DP不是显得高级是在给自己挖坑。6. C提交机试题的常见坑与调试清单6.1 输入输出性能关掉同步再上cin机试数据量大的时候cin和cout默认比scanf和printf慢很多原因是C的IO流要和C的stdio保持同步每读一个字符都要检查一下。解决办法是加这两行ios::sync_with_stdio(false); cin.tie(nullptr);加了之后cin的速度基本能追上scanf。代价是不能再混用cin和printf也不能混用scanf和cout因为两套缓冲机制不同步可能导致输出顺序错乱。我见过有人前一行写cin n后一行写printf(%d\n, n)结果输出莫名其妙对不上排查半天才发现是混用IO的问题。多组输入读到EOF的标准写法是while (cin n)在本地测试时需要手动结束输入Windows下按CtrlZ再回车Linux和Mac下按CtrlD。很多人不知道这个本地一跑发现程序不结束还以为死循环了。6.2 STL选型的几个典型误区第一sort可以对vector、string、普通数组排序但普通数组要传指针区间sort(a, a n)vector则用sort(v.begin(), v.end())别记混。第二set和unordered_set的选择。需要有序遍历时用set只需要判断存在性时用unordered_set。机试里有些题要求“按字典序输出”这时候用unordered_set存完再排序也行但如果数据量大一遍插入时保证有序的set反而更省事。第三map和unordered_map。map底层红黑树查找O(log n)unordered_map底层哈希表查找平均O(1)。但哈希表需要计算哈希少量数据时未必更快。工程上会有各种权衡机试里多用unordered_map处理大查询量但必须记住unordered_map不保证遍历有序需要有序输出时就别用它。6.3 边界测试清单与暴力对拍代码写完之后我建议按这份清单自测一遍空输入、n等于1、最大数据规模、字符串含空格和标点、数字含前导零或大数溢出、起终点重合、全是墙或全无障碍。这几种情况不用全部跑通但至少要想清楚程序会怎么走边界条件是否成立。更好的方法是暴力对拍。写一个绝对正确但效率低的函数比如用递归枚举所有方案再写一个优化版本然后用随机数据分别跑两个版本对比结果。只要有一组数据不一样说明优化版本里有逻辑错误这时候调试比直接交上去WA再干瞪眼高效得多。本地调试时可以用freopen(in.txt, r, stdin)把输入重定向到文件但提交前务必注释掉不然OJ读不到输入直接卡住。7. 我的复盘习惯与这组题的后续用法每道题AC之后我会再多花几分钟看看题解重点不是背标准答案而是对照自己的代码看哪里绕路了。比如第36题单词倒排我第一次是先手动遍历找单词边界代码写了二十多行后来才意识到把标点替换成空格再交给istringstream处理代码短了一半。这种经验只能在对比中积累光靠自己硬写很难意识到更优解。另一个习惯是本地维护一个模板文件把BFS、DFS、栈、队列、背包、排序、高精度这些核心模板存下来每刷到一次就更新一次逐渐形成自己的版本。机试现场时间紧张模板越熟留给思考题目的时间就越多。最后是限时模拟。按真实机试的时长给自己掐表训练“先易后难”的取舍。我的策略是先把送分的字符串题、模拟题写完拿稳再去啃动态规划和图论题绝不在一道题上死磕超过二十分钟。这组31到40题刷完之后你的C手感、STL熟练度和算法选型能力应该都有一个明显的提升后续再往链表、双指针、更复杂的DP上拓展就有了一个还算扎实的地基。
