机试刷题有个分水岭。前30题练的是语法熟练度，到了31~40这个区间，题目开始变成“阅读理解加算法选型”：同一道题，你用暴力可能也能过样例，一交上去才知道超时或者漏了边界。这次想聊的是机试在线训练C++版第31到40题，覆盖字符串处理、栈与递归、BFS、贪心和动态规划这五个高频方向。准备机试的人可以直接拿来做训练；刚学完C++想巩固算法的人，也可以从这组题里找到适合自己的节奏。

1. 先看整体：这组题的考点地图与刷题顺序

1.1 机试判题规则里最容易忽略的细节

在线训练平台和平时自己写Demo最大的区别在于：评测机只看输入输出，而且测试用例远不止题目里给的样例。你本地跑一遍没问题，不代表提交后能AC。超时、内存越界、多组输入没读完、输出多了个空格，这些坑我都踩过一遍。

平台常见的限制是1秒时间、几十到几百MB内存。1秒能跑的量级大概是：n在10^7以内时，O(n log n)的算法可以稳过；如果n=10^5，O(n^2)基本就会超时。所以拿到题第一件事不是写代码，而是看数据范围，这直接决定你用什么思路。比如n只有100，那暴力枚举和动态规划都能过；一旦n=10^5，暴力的双循环就彻底没戏。

输入输出格式也要提前确认。很多题是多组测试直到EOF，写法是while (cin >> n)；有的是单组输入，那直接读就行。最容易翻车的是读含空格的字符串，cin >> s读到空格就停了，必须用getline(cin, s)。如果前面刚用cin >>读过一个整数，后面接getline时得先用cin.ignore()把残留的换行符清掉，否则读到的就是一个空行。这个细节，我见过太多人在机试现场卡了十分钟。

1.2 十道题的分类与优先级

我把这十道题按考法和难度排了个表，方便你安排刷题顺序。需要说明的是：这组题不是让你背原题，机试每年都在更新，按考点方向练才有意义。

我的建议顺序是先做31、32、35热身，把输入输出手感找回来，再做33、34、36，然后进入37和40，最后花精力啃38和39。字符串和模拟题能帮你熟悉各种输入陷阱，栈和搜索放在中间练模板，动态规划和贪心最吃逻辑，留到最后脑子清醒的时候刷。

2. 字符串与模拟题的三道实战：去重排序、大数加法、单词倒排

2.1 题31：字符串去重并排序——set与标记数组怎么选

题目描述差不多是这样：输入一行可能包含空格的字符串，去掉其中重复的字符（空格不参与），按ASCII码升序输出剩余字符。比如输入hello world，输出就是dehlorw。

看到“去重加升序”，第一反应是set<char>，因为set天然有序且自动去重。但要注意读入方式：

#include <iostream> #include <set> #include <string> using namespace std; int main() { string s; getline(cin, s); // 必须读整行，cin >> 读到空格就停 set<char> 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是90，a是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); vector<string> 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) { stack<char> 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, vector<int>& pre, unordered_map<int,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}}; queue<pair<int,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 题38：0-1背包——一维滚动数组的循环顺序

背包问题是动态规划里最经典的入门题。有N件物品，每件物品有重量w[i]和价值v[i]，背包容量为V，求能装下的最大价值。每件物品只有拿或不拿两种状态，所以叫0-1背包。

二维dp的状态定义是dp[i][j]表示前i件物品在容量j下能获得的最大价值，转移方程是拿或不拿取最大值。但机试更常用的是空间压缩后的一维数组：

vector<int> 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]，输出合并后不重叠的区间列表。思路是按起点升序排序，然后逐个合并。

vector<pair<int,int>> merge(vector<pair<int,int>>& intervals) { if (intervals.empty()) return {}; sort(intervals.begin(), intervals.end()); vector<pair<int,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下按Ctrl+Z再回车，Linux和Mac下按Ctrl+D。很多人不知道这个，本地一跑发现程序不结束，还以为死循环了。

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上拓展，就有了一个还算扎实的地基。