华东师大计算机保研机试2020题解：字符串、BFS、单调队列通关指南

每年保研季，华东师大计算机学院的机试都会刷掉一批准备不充分的同学。2020年那套题我印象很深，整体难度不算高，但坑点相当密集：有人挂在字符串展开，有人挂在连通块查询的输入读法上，还有人连滑动窗口的暴力写法都交了，最后T到怀疑人生。这篇题解不打算用“放个AC代码完事”的方式写，而是把每道题背后的思考过程、考场上的判断依据和容易错的地方都拉出来讲一遍，适合正在准备保研机试、考研复试上机，或者单纯想刷OJ题的朋友。

1. 先搞清华师大机试考什么：试卷结构与备考侧重点

华师大的机试和很多学校不太一样，它没有特别偏难怪的算法题，但很考验“在有限时间内把会做的题稳稳写完”的能力。从近几年的回忆版题目来看，一场考试一般是4道题左右，难度有明显的梯度：前一到两题属于模拟和字符串处理，第三题开始上搜索或数据结构，最后一题基本就是综合题，可能混着DP或图论。2020年这套题基本也是这个套路。

为什么这是关键信息？因为备考策略会完全不同。如果你按ACM区域赛的标准去刷那些思维量极大的构造题，考场上很容易陷入“这题见过类似的但就是写不完”的状态。华师大机试更贴近“工程型算法题”：题目描述直白，数据范围给得清楚，没有隐藏的题意陷阱，但你写得够不够快、够不够稳，直接决定你能不能拿满。很多人LeetCode刷了几百题，到机试现场还是翻车，原因就在这里——OJ题和面试题的环境差别太大。

备考侧重点也该跟着这个表走：字符串处理和栈相关必须熟练，BFS框架要能闭着眼睛敲出来，单调队列这种看起来“高大上”的东西反而需要多练，最后那类排序模拟虽然简单，但排序条件写反的大有人在。这套题的整体定位就是“中档题居多，细节定生死”，所以我下面按题目逐题拆，重点放在那些容易丢分的位置。

1.1 考场环境与输入输出习惯

华师大机试一般用Dev-C++或CodeBlocks，C++11标准是默认的。开发环境比较老旧，所以代码里尽量别用C++17甚至C++20的特性，比如结构化绑定虽然C++17就有，但为了稳妥，我都写成传统形式。另外我强烈建议养成用scanf/printf的习惯，不是cin不行，而是你不知道评测数据有多大。如果有一组输入是几十万甚至上百万的序列，cin不关同步的情况下很容易超时，关了同步又容易忘了写。直接用scanf就没这个心理负担。

还有一个很多新手会忽略的点：全局变量会自动初始化为0，但局部数组不会。机试里我喜欢把地图、队列、标记数组全开成全局变量，既省去memset的麻烦，也能避免递归深度大的时候栈溢出。这些习惯不是考试时临时想起来的，是平时刷题就得练成肌肉记忆。

2. 字符串按规则展开：栈模拟的底层直觉

先看这道典型的字符串题，题意大致是这样：给定一个字符串，里面的数字表示后面括号内容重复的次数，括号可以嵌套，比如3[a2[c]]，展开后应该是accaccacc。括号外层也可能有普通字母，比如2[ab]d展开后是ababd。所有输入保证格式合法，数字只表示正整数。

这道题在LeetCode上有原题，但机试版更倾向于让你处理完全部输入后一次性输出，而不是只写一个函数返回值。核心就一个数据结构：栈。而且是两个栈——一个存当前已经拼好的前缀字符串，一个存需要重复的次数。

推演一下3[a2[c]]的处理过程：

1. 读到数字3，累计num=3。
2. 读到[，把3压入次数栈，把当前字符串cur（此时为空串）压入前缀栈，然后num清零、cur清零。
3. 读到字母a，cur="a"。
4. 读到数字2，num=2。
5. 读到[，把2压入次数栈，把cur="a"压入前缀栈，然后num清零、cur清零。
6. 读到字母c，cur="c"。
7. 读到]，次数栈弹出一个2，前缀栈弹出一个"a"，把"c"重复2次变成"cc"，拼到"a"后面，cur="acc"。
8. 读到]，次数栈弹出一个3，前缀栈弹出一个空串，把"acc"重复3次，cur="accaccacc"。

为什么需要用两个栈？因为它本质上是一个“暂存现场”的过程。遇到嵌套括号时，你得把外层已经拼好的部分和对应的重复次数先存起来，等内层括号处理完再恢复。这和递归调用的栈帧是一个道理，所以这道题也可以用递归做，但递归的代码在处理多层嵌套时不如栈直观，而且机试环境里你还要担心递归层数过深会不会爆栈。直接用栈模拟是最稳的解法。

参考代码：

#include <bits/stdc++.h> using namespace std; string decodeString(string s) { stack<string> strStk; stack<int> numStk; string cur = ""; int num = 0; for (char c : s) { if (isdigit(c)) { num = num * 10 + (c - '0'); } else if (c == '[') { numStk.push(num); strStk.push(cur); num = 0; cur = ""; } else if (c == ']') { int k = numStk.top(); numStk.pop(); string pre = strStk.top(); strStk.pop(); string tmp = ""; while (k--) tmp += cur; cur = pre + tmp; } else { cur += c; } } return cur; } int main() { string s; while (cin >> s) { cout << decodeString(s) << endl; } return 0; }

2.1 最容易踩的两个坑

第一个坑是多位数。如果输入是12[a]，数字12会被逐个字符读入。如果不写num = num * 10 + ...这一步，只记录当前这一个字符，就会把12拆成1和2处理，结果完全错乱。很多人不是因为不懂栈，而是因为对“数字可能不止一位”这个条件不敏感。这里有个小习惯：写字符处理题时，默认所有连续数字都是整体，养成累加的习惯。

第二个坑是括号外的字母。像2[ab]d这个用例，最后的d是在整个结构之外的，处理完括号后，d还得跟在结果后面。所以代码里的else分支不能扔，它负责把所有既不是数字也不是括号的字符追加到cur末尾。

调试技巧：遇到字符串展开类的题，先在草稿纸上把“遇到[压栈、遇到]弹栈”这个过程推两遍，再动手写代码。不要边写边想，这种题一旦栈的入栈顺序错了，调试时间会成倍增加。

3. 地图连通块大小查询：一次BFS解决所有问题

第二题是典型的图论搜索题，描述大概是这样：给定一个n行m列的地图，#表示陆地，.表示水域。上下左右相邻的陆地视为同一个连通块。接下来有q个询问，每次给定一个坐标(x,y)，要求输出这个坐标所在连通块的面积大小。数据范围一般是n,m不超过1000，q最多10万。

这种题如果上来就“每次询问跑一次BFS”，复杂度是O(q * n * m)，在极端数据下直接爆炸。正确做法是先把全图扫一遍，给每个连通块染色编号，同时统计每个连通块的面积，之后每个询问就是一次O(1)的数组查询。这个思路叫“离线预处理”，机试里特别常用。

BFS或者DFS都能解决染色这一步，但我更推荐BFS。原因很现实：递归版DFS在OJ环境里可能因为栈空间不足而崩掉。机试环境给的栈空间很小，地图1000x1000，DFS深度可能到几十万层，虽然很多评测机开了大栈，但你不能赌这个。手写队列做BFS虽然代码长一点，但保证不会因为递归爆栈而出问题。

参考代码：

#include <bits/stdc++.h> using namespace std; const int MAXN = 1005; int n, m, q; char mp[MAXN][MAXN]; int id[MAXN][MAXN]; int sz[MAXN * MAXN]; int dir[4][2] = {{1,0},{-1,0},{0,1},{0,-1}}; void bfs(int sx, int sy, int color) { queue<pair<int,int>> qu; qu.push({sx, sy}); id[sx][sy] = color; int cnt = 0; while (!qu.empty()) { int x = qu.front().first; int y = qu.front().second; qu.pop(); cnt++; for (int d = 0; d < 4; d++) { int nx = x + dir[d][0]; int ny = y + dir[d][1]; if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue; if (mp[nx][ny] != '#') continue; if (id[nx][ny] != 0) continue; id[nx][ny] = color; qu.push({nx, ny}); } } sz[color] = cnt; } int main() { scanf("%d%d%d", &n, &m, &q); for (int i = 0; i < n; i++) { scanf("%s", mp[i]); } int color = 0; for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { if (mp[i][j] == '#' && id[i][j] == 0) { color++; bfs(i, j, color); } } } while (q--) { int x, y; scanf("%d%d", &x, &y); printf("%d\n", sz[id[x][y]]); } return 0; }

3.1 为什么一次BFS能回答所有查询

很多刚开始练OJ的朋友会卡在“为什么要染色”这一步。你可以这么理解：每个连通块就像一个班级，BFS的过程就是给每个班级里的学生发一个统一的班号。发完班号之后，你想知道某个学生属于哪个班，直接看他的胸牌就行，不需要重新数一遍这个班里有多少人。

这个道理延伸到很多题目里：凡是“多次询问某个区域/集合的属性”的题目，第一反应都该是“预处理一次，回答多次”。包括并查集、区间前缀和、差分数组，本质上都是同一个思路。机试里考的不只是你会不会BFS，更是你能不能看出“问题可以离线统一处理”。

另外可以注意一下id数组的两个作用：第一，防止同一个格子被反复入队，保证每个格子只被访问一次；第二，它在BFS过程中顺手完成了“给每个格子打上所属连通块编号”的任务。这两个作用合在一起，让BFS的复杂度稳定在O(n*m)，是整道题的复杂度下界。

3.2 读入地图时的经典事故

这道题的输入环节有两个高频事故。

第一个是scanf("%s", mp[i])之后，如果行末可能还有\r（在Windows本地调试常见），会串到当前行末尾，导致判断字符时永远等不到#。解决办法是在读入后手动清一下，或者评测环境正常情况下不会出现，但我在本机调试时确实遇到过。

第二个是用cin读二维字符数组时，如果不小心把cin >> mp[i]写成了cin.getline，就很容易被上一行末尾的换行符坑到。机试现场时间紧张，读入出错是最让人心态爆炸的问题。稳妥的做法是统一用scanf("%s")读每一行，它对空白字符的处理比getline干净得多。

4. 滑动窗口最大值：单调队列的正确打开方式

第三题是滑动窗口的最大值：给定长度为n的整数数组a和一个窗口大小k，窗口从左往右滑，每次移动一个位置，要求依次输出每个窗口内的最大值。n最大10^6，k不超过n。这是单调队列的模板题，也是2020年这套题里区分度最大的一道。

如果你看到n是10^6，第一反应应该立刻排除两层循环的暴力做法——那是最坏O(n*k)的复杂度，k稍微一大就超时。常见的替代方案有几种：multiset维护窗口元素，O(n log k)能过；线段树也可以O(n log n)；但最优解是单调队列，O(n)线性扫完，代码还比线段树短。

4.1 单调队列的维护原理

单调队列的思路可以这样理解：队列里存的是数组下标，并且保证在这些下标对应的元素值从左到右是严格递减的。这样队头永远指向的就是当前窗口的最大值所在位置。

为什么可以放心地把队尾那些“更小”的元素弹出？因为新来的元素比它们更大、而且在窗口里活得更久。一个又老又小的元素，在它被移出窗口之前，最大值永远不会轮到它；在新元素进入后，它更没有机会，留下来只是浪费空间。这个“将来不可能成为答案”的淘汰逻辑，就是单调队列正确性的根。

具体维护分三步：

1. 队头淘汰过期下标：如果q[head] <= i - k，说明这个下标已经滑出窗口，head前移。
2. 队尾维护递减性：只要a[q[tail-1]] <= a[i]，就不断tail前移，把劣势元素弹出。
3. 队尾插入新下标：将i压入队尾。

注意第二步用的是<=而不是<。为什么？因为如果有两个相同值的元素，旧的元素反正会被淘汰，用<=直接弹掉可以避免队列里存在多余重复值，减少判断开销。这里保留旧元素也没有正确性问题，但代码会更啰嗦。机试里用<=是约定俗成的写法。

手写数组模拟队列，比直接调STL的deque快不少，而且避免deque初始化带来的额外开销。

#include <bits/stdc++.h> using namespace std; const int MAXN = 1000005; int a[MAXN]; int q[MAXN]; int main() { int n, k; scanf("%d%d", &n, &k); for (int i = 0; i < n; i++) scanf("%d", &a[i]); int head = 0, tail = 0; for (int i = 0; i < n; i++) { while (head < tail && q[head] <= i - k) head++; while (head < tail && a[q[tail-1]] <= a[i]) tail--; q[tail++] = i; if (i >= k - 1) { printf("%d%c", a[q[head]], i == n-1 ? '\n' : ' '); } } return 0; }

4.2 边界条件和队列越界的排查

这道题的代码很短，但考试时踩坑的点集中在三个地方：

第一个是判断过期元素的条件。写成q[head] < i - k还是q[head] <= i - k？窗口左边界是i - k + 1，所以下标小于等于i - k的都该被丢掉。写错这个符号，输出的第一个窗口就会错。建议在草稿纸上把i=k-1这个初始窗口的边界算一遍再写。

第二个是手写队列的数组越界。如果你把tail++写在数组插入之后、却忘记tail的最大范围其实不会超过n，那就可能访问到未定义内存。只要队列是循环使用的，tail单调增加，最多到n，开MAXN足够，但这个“q[tail++] = i;”和前面两个while的配合一定要写熟。

第三个是输出格式。机试对空格和换行的要求极其严格，多一个空格或少一个换行都算Presentation Error。我习惯的方式是：前n-k个值后面跟空格，最后一个值后面跟换行，代码里我用i == n-1 ? '\n' : ' '这个三元表达式统一处理，不会漏。

如果你担心单调队列不好理解，还有一个折中方案：用multiset维护。每次插入新值、删除滑出的旧值，取*rbegin()就是最大值。这个写法逻辑简单很多，O(n log k)复杂度和单调队列在10^6数据下也还能接受。但我还是建议把单调队列练熟，因为类似“下一个更大元素”“最大矩形面积”等题目，底层都是同一个单调思想，考场上遇到变形题你会感谢自己练过。

5. 队伍榜单输出：比较器里的魔鬼细节

最后这道题属于“看起来很送分、实际翻车率极高”的类型。大致题意是：给定n支队伍的过题数和罚时，要求按过题数降序排序，过题数相同的按罚时升序，罚时也相同的按队伍编号升序，最后按排名输出队伍编号和所有字段。这类题在OJ上叫“多关键字排序”，华师大几乎每年都有一道，但每次都有不少人因为比较函数写错而WA一整场。

5.1 严格弱序和compare的写法

C++的sort要求比较函数满足“严格弱序”，简单说就是：如果cmp(a,b)为真，表示a应该排在b前面；那么cmp(b,a)必须为假。用结构体加自定义比较器是标准做法：

#include <bits/stdc++.h> using namespace std; struct Team { int id, solved, penalty; } teams[105]; bool cmp(const Team &a, const Team &b) { if (a.solved != b.solved) return a.solved > b.solved; if (a.penalty != b.penalty) return a.penalty < b.penalty; return a.id < b.id; } int main() { int n; scanf("%d", &n); for (int i = 0; i < n; i++) { scanf("%d%d", &teams[i].solved, &teams[i].penalty); teams[i].id = i; // 队伍编号从0开始 } sort(teams, teams + n, cmp); for (int i = 0; i < n; i++) { printf("%d %d %d\n", teams[i].id, teams[i].solved, teams[i].penalty); } return 0; }

这里最大的坑是：return a.solved > b.solved是降序，return a.solved < b.solved是升序。很多人在考场上一紧张就把方向搞反了。我的记忆技巧是：比较器返回true时，a排前面；升序就是“小的排前面”，所以返回值用a < b；降序就是“大的排前面”，所以返回值用a > b。写完之后，我会用一组只有两项的数据在脑子里跑一遍，看排序结果是不是预期的顺序。

另一个常见问题是直接在比较器里写<=或>=。这是严格弱序的禁忌，因为当a和b相等时，a <= b和b <= a同时为真，sort会认为两者等价，但在某些STL实现里可能导致未定义行为甚至死循环。比较器里永远只用<和>，相等情况留到最后的编号比较再处理。

5.2 输出格式这类不起眼的罚时来源

这道题的考查重心其实是“你能不能把排序条件完整地表达出来”，而不是排序本身。我见过太多人栽在这些地方：

• 队伍编号从1开始还是从0开始没读清楚，最后输出编号全部偏移一位；
• 罚时和过题数的优先级搞反，先按罚时排了；
• 输入数据不保证编号按序，有些题会故意打乱输入顺序；
• 输出要求“编号之间用空格分隔”或“每行末尾允许有多余空格”，不同OJ要求不一样，必须看题。

这些细节单看都不难，但在考场上的叠加效应非常致命。我的建议是，拿到排序模拟题先花30秒读清楚三件事：排序字段的优先级、编号起始值、输出格式。确认完再动手写，看似多花了时间，实际是在帮你避免返工。

6. 考场时间分配与代码模板清单

机试不是“做出所有题”才算赢，而是在有限时间内拿最多的分。以2020年这套题来说，如果让我排策略，我会给自己定一个明确的时间线：前20分钟扫完四道题，把每道题的数据范围、算法类型和难度打上标签。字符串题和榜单题属于“必拿分”，各给20到30分钟；连通块题30分钟；滑动窗口题如果5分钟内没有思路，先写暴力拿部分分，最后再回头优化。

为什么这么分配？因为华师大机试的总分是按通过多少组测试数据算的，不是只有0和1的区别。一道暴力解法可能能过60%的数据，拿到60%的分值，这比死磕一个最优解导致最后两道题没时间写要划算得多。很多同学觉得“暴力分丢人”，实际上在机试里，能拿AC当然最好，拿不到AC用暴力蹭分也是最理智的行为。

6.1 值得背下来的板子

我整理的机试模板清单大概是这些：

// 快读模板（scanf还不够快时用） int read() { int x = 0, f = 1; char c = getchar(); while (c < '0' || c > '9') { if (c == '-') f = -1; c = getchar(); } while (c >= '0' && c <= '9') { x = x * 10 + c - '0'; c = getchar(); } return x * f; }

// 手写队列 int qu[MAXN], head = 0, tail = 0; // qu[tail++] = x; 入队 // qu[head++]; 出队

// 并查集 int fa[MAXN]; int find(int x) { return fa[x] == x ? x : fa[x] = find(fa[x]); } void merge(int a, int b) { int ra = find(a), rb = find(b); if (ra != rb) fa[ra] = rb; }

// Dijkstra + 堆优化 priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> pq; dist[st] = 0; pq.push({0, st}); while (!pq.empty()) { int d = pq.top().first, u = pq.top().second; pq.pop(); if (d != dist[u]) continue; for (auto &e : g[u]) { int v = e.first, w = e.second; if (dist[v] > dist[u] + w) { dist[v] = dist[u] + w; pq.push({dist[v], v}); } } }

这些模板不需要多，但每一个都应该是你写过错题、调过bug之后沉淀下来的版本，而不是考前临时抄上去的。我个人的习惯是考前把板子手抄一遍再默敲一遍，重点在“默”字。考场上不给你翻笔记的时间，只有形成肌肉记忆，才能在紧张状态下不出错。

调试技巧方面，printf断点大法仍然是最快的定位方式，不要过度依赖IDE的断点调试。写完一段关键逻辑后，在循环里打印中间变量，确认输出符合预期再继续往下写。如果发现某一步的结果和手算的不一致，优先怀疑边界条件和数组下标，这两类bug在机试里占了绝大多数。

最后分享一个小习惯：每次提交前，把题目条件和自己的代码逐条对照一遍。数据范围数组开够没有，多组输入的循环有没有把所有变量重置，输出格式是不是严格匹配。别小看这几分钟的检查，我在考场上靠这个习惯救回过很多次。希望这份题解能帮你少踩一些坑，也祝你机试顺利。