每年三月下旬西电的计算机复试机试都会刷掉一批笔试成绩还不错的人。原因往往不是题目有多难而是很多人到了机房才发现机试考的从来不是“会不会做”而是能不能在规定时间内把思路变成一份不越界、不超时、格式正确的AC代码。这篇内容我把2025年复试中按多位考生回忆综合还原的高频真题整理出来从解题思路到AC代码完整拆开讲再附上考场上的输入输出处理和边界测试心得。准备计算机考研、临近复试需要刷真题找手感、或者想了解西电机试风格的人这篇都值得看完。1. 西电计算机机试的考场画像规则、环境与真题的稳定面貌1.1 大概的考核方式与在线评测环境西电复试机试通常在机房进行使用在线评测系统提交代码。考生在本地写代码调试通过后把源码提交系统用若干组测试数据判分。评测环境以Linux下的g为主支持C和C不支持Python和其他脚本语言。所以哪怕你Python写得很溜复试前也一定要把手感和调试习惯切回C/C。时间上大致是两到三个小时完成多道题目具体题量和分值每年公告会有差异以当年官网通知为准。但有个规律很稳定评分不是按题目总数算平均而是按照通过测试点的比例给分。也就是说哪怕一道大题不会做只要把暴力版本写出来拿一部分分数也比死磕某一道题然后留白划算。这一点很多人考完才反应过来但已经来不及了。另一个容易忽略的点是环境里的编译器版本。我在备赛时习惯用新特性比如auto、vector、unordered_map这些在g编译下没问题。但如果你习惯用DEV-C这种老IDE里面默认的C标准可能比较旧机房评测时偶尔会出现编译不过的情况。建议统一提交风格头文件用#include bits/stdc.h尽量避免太依赖单编译器特性的写法。1.2 近几年题型频率统计与难度坐标结合考生回忆和公开经验帖西电机试的题目类型相当集中很少出偏题怪题。我把近几年的高频考点整理成一张表难度参照大家比较熟悉的蓝桥杯省赛和CCF CSP认证考点大类出现频率难度坐标典型考察方式字符串处理很高CSP第1题到第2题之间统计字符、加密替换、子串处理模拟题很高蓝桥杯省赛简单题按规则一步步走完流程边界多搜索BFS/DFS中高图论入门题网格最短路、连通块、迷宫可行性排序与贪心中高CSP第2题区间问题、自定义排序、优先级队列基础数学中蓝桥杯省赛简单题最大公约数、素数判断、进制转换这个规律背后是学校的考察倾向复试机试更在意把算法思路转化为可运行代码的稳定度而不是竞赛式的高难度技巧。所以很多题你看着眼熟但拿满分需要把细节处理干净。下面两道还原题就很好地体现了这种风格。2. 第一道还原题字符串统计与循环偏移思路推演 AC 代码2.1 题目原貌按考场回忆还原这道题是2025年复试中多人提到的字符串处理题。按回忆综合还原后的描述如下给定一个仅由小写字母组成的字符串S长度不超过10的5次方。先统计每个字符出现的次数并按照字符在字符串中第一次出现的位置顺序输出“字符:次数”。然后对S中的每个字符进行循环替换假设当前字符为c它在原串中出现过cnt次就把c替换为字母表中往后数cnt个位置的字母。这里的“往后数”是循环的即z的后面又回到a。请输出统计结果和替换后的字符串。输入格式第一行一个整数T表示测试组数接下来T行每行一个字符串S。输出格式每组数据输出两行第一行为统计结果字符之间用英文逗号分隔第二行为替换后的字符串。样例输入2 aaba abc样例输出a:3,b:1 ddca a:1,b:1,c:1 bcd第一组里a出现3次所以替换为db出现1次替换为c原串aaba变成ddca。第二组abc三个字符各出现1次整体向后移动一位变成bcd。2.2 拿到题目后先不急着写码三种方案的推演这种题一眼看穿是“统计映射”的组合但在考场上最好先花一两分钟把流程拆清楚。我看到题的第一反应是先画处理流水线统计出现次数 → 记录首次出现顺序 → 输出统计 → 遍历原串做循环偏移。这条流水线定下来之后代码结构就不会乱。方案一可以直接用两层循环每遇到一个没处理过的字符就去遍历整个串统计次数、找首次出现位置。这样做时间复杂度和字符串长度相关单层处理还好T组数据全部上来后会达到平方量级。机试数据如果拉满10的5次方这种写法就跑不动了。字符串题考察的核心之一就是能不能想到用数组当哈希表。方案二用int cnt[26]数组统计每个字母出现次数同时用一个vectorchar按首次出现顺序记录字符种类。判断“是否已经记录过”可以用bool in[26]辅助。这个思路是正确的时间复杂度降到线性的字符长度空间上只需要常数级别。这也是我最终采用的方案。方案三可能会有同学想到用mapchar,int觉得自带排序更省事。但这里有个关键差别题目要的是首次出现顺序不是字典序。如果用map字符会按a-z输出直接和题目要求拧着来。除非额外记录首次出现位置再排序否则不如数组方案简洁。很多人在这一处翻车不是不会写而是没读懂“首次出现顺序”这五个字。2.3 AC代码与关键点逐段说明#include bits/stdc.h using namespace std; void solve(const string s) { int cnt[26] {0}; bool in[26] {false}; vectorchar firstSeen; for (char ch : s) { int idx ch - a; if (!in[idx]) { in[idx] true; firstSeen.push_back(ch); } cnt[idx]; } for (size_t i 0; i firstSeen.size(); i) { if (i) cout ,; cout firstSeen[i] : cnt[firstSeen[i] - a]; } cout \n; for (char ch : s) { int idx ch - a; int nxt (idx cnt[idx]) % 26; cout char(a nxt); } cout \n; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int T; cin T; while (T--) { string s; cin s; solve(s); } return 0; }第一段的cnt和in是配套使用的。in数组只负责标记“这种字符有没有在firstSeen里”避免后面输出统计时产生重复项。每遇到一个新字符就把它push进firstSeen这比遍历26个字母判断cnt[i] 0要更贴近“首次出现顺序”的语义。因为如果直接遍历26个字母输出就会变成字典序这是最常见的错误。第二段输出统计结果的时候用firstSeen[i] - a去取对应次数。注意这里不能直接用cnt[i]因为i是vector下标不是字母下标。第一个字符是a时两者刚好相等换成b、c之后就全乱了。这个细节我在写完自测时专门验证过。第三段替换逻辑里最核心的是(idx cnt[idx]) % 26。这里如果忘了取模字符ch的偏移会越界比如z出现10次不加取模直接加到整数上会超过122输出的字符就变成各种符号。循环字母表的题取模注定躲不掉。还有一个容易被忽视的点传入solve函数的是按引用传递的字符串函数内不修改它只读取。如果拷贝一份到函数里字符串长度10的5次方、T组1万次时拷贝开销会明显拖慢程序。这种级别的优化不需要刻意追求但“能传引用就不传值”的习惯在机试的紧张状态下能省下不少时间。2.4 这道题的变形方向与常见套路西电对字符串题的偏好在这道题上体现得很典型要求你同时处理好统计、顺序、映射、循环四件事。考场上如果觉得太简单也别放松因为它的变形可能出现在后续年份把“首次出现顺序”改成“按出现次数降序、次数相同按字典序”这时就需要自定义排序规则考察点变成排序稳定性。把“出现次数”改成“最后一次出现的位置”或“所有出现位置之和”作为偏移量代码结构不变但计算方式要跟着换。增加输出格式要求比如每组之间空一行、统计结果末尾不允许有多余逗号这种格式陷阱专门用来刷掉不仔细读题的人。准备这类题时建议把统计、首现顺序、排序三种能力分别练熟考场上就能根据题目的要求快速拼接。尤其是“按首现顺序输出”这种细节很多非竞赛选手容易默认成字典序一失手就是整题零分。3. 第二道还原题0/1 网格上的 BFS 最短路思路推演 AC 代码3.1 题目原貌按考场回忆还原搜索题在西电机试里的重要程度不用多说。下面这道是2025年复试里被多次提及的网格题按回忆综合还原如下给定一个n行m列的0/1矩阵0表示可以通过1表示障碍物。一个人从左上角(0,0)出发每次可以向上、下、左、右四个方向移动一格不能走出矩阵也不能走到障碍物上。问到达右下角(n-1,m-1)所需的最少步数如果无法到达则输出-1。输入格式第一行两个整数n和m之后n行每行m个整数每个整数为0或1。样例输入5 4 0 0 0 1 1 1 0 1 1 0 0 1 1 1 0 0 0 0 0 0样例输出7从(0,0)出发沿着能走通的通道一路绕行到(4,3)最短步数确实是7。验证路径向右到(0,1)再向右到(0,2)向下到(1,2)向下到(2,2)向下到(3,2)向下到(4,2)向右到(4,3)一共7步。3.2 为什么遇到“最少步数”优先选 BFS 而不是 DFS网格上求最短步数标准解是BFS。原因是BFS天然按层扩展起点出发先到距离1的所有点再到距离2的所有点所以第一次从队列中弹出终点时记录下来的步数一定是最小步数。这也是BFS能保证最短路的性质和边上权重为1的前提绑定。有人会问DFS能不能做当然能但DFS的“深挖到底再回头”机制决定了它首次到达终点时走过的路径不一定最短。如果要用DFS找最短路必须把所有可达路径全部遍历完再取最小值相当于暴力枚举所有路径复杂度随网格变大快速爆炸。在矩阵1000乘1000这种规模下DFS求最短路基本不可能通过全部测试点。BFS还有个额外好处它对空间的要求也可控。每个节点入队一次最多把整张图都放进队列内存上限可以提前估算。1000乘1000的矩阵有100万个格子队列里同时存活的最坏情况也不会超过节点总数内存完全够用。只要入队的同时做访问标记避免重复入队BFS的稳定性是四种常见搜索里最高的。3.3 AC代码与网格边界处理的四个关键动作#include bits/stdc.h using namespace std; struct Node { int x, y, step; }; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, m; cin n m; vectorvectorint a(n, vectorint(m, 0)); for (int i 0; i n; i) { for (int j 0; j m; j) { cin a[i][j]; } } if (a[0][0] 1 || a[n - 1][m - 1] 1) { cout -1 \n; return 0; } const int dx[4] {-1, 1, 0, 0}; const int dy[4] {0, 0, -1, 1}; vectorvectorint vis(n, vectorint(m, 0)); queueNode q; q.push({0, 0, 0}); vis[0][0] 1; while (!q.empty()) { Node cur q.front(); q.pop(); if (cur.x n - 1 cur.y m - 1) { cout cur.step \n; return 0; } for (int k 0; k 4; k) { int nx cur.x dx[k]; int ny cur.y dy[k]; if (nx 0 || nx n || ny 0 || ny m) continue; if (vis[nx][ny] || a[nx][ny] 1) continue; vis[nx][ny] 1; q.push({nx, ny, cur.step 1}); } } cout -1 \n; return 0; }代码里最关键的是起点和终点特判。如果左上角就是障碍物或者右下角是障碍物直接输出-1这一行能避免后面BFS的空转。很多人漏掉这个判断导致起点入队后立刻被弹出来最终输出错误结果。考试时不要觉得这种判断多余边界数据往往就在这里设伏。方向数组dx/dy的顺序无所谓但四个方向必须覆盖完整上、下、左、右。少一个方向某些能通行的路径就走不到。这里我用两个一维数组比存四个坐标对写起来更紧凑。移动后先检查越界再检查访问标记和障碍物顺序反了会导致访问vis[nx][ny]时代码访问越界下标出现运行时错误。访问标记放在入队时置位而不是出队时置位。这个细节非常关键。如果在弹出节点时才标记同一个节点可能被多个邻居重复入队队列中会出现大量冗余节点最坏情况下运行时间成倍增长甚至在极端数据下引发内存问题。BFS模板中“入队即标记”是必须养成的肌肉记忆。3.4 搜索题的进阶优化思路如果今年考题在网格上增加条件比如“有k点体力每走一步消耗1点某些格子上可以恢复体力”那状态就从二元组变成三元组vis需要升级成vis[x][y][power]BFS框架仍然成立只是队列节点里多一个字段。如果变成“某些格子只能走一次”那就得在状态里记录已访问集合复杂度会明显上升这种题出现在复试里的概率不大但心里有数总比毫无准备强。对于一般复试题的网格规模vectorvectorint二维数组足够。但如果你担心初始化耗时或者矩阵接近1000乘1000可以用一维数组手动映射下标idx x * m y代码稍复杂但访问更紧凑。我在考场上习惯二维写法因为可读性优先调试也直观。4. 考场键盘生存手册输入输出、边界测试与提交顺序4.1 输入输出模板与格式化陷阱机试中因为输入输出格式失分是最可惜的。常见坑位有三个cin和scanf混用、多组测试数据的残留字符、输出行尾多余空格。先看输入加速。我在代码开头固定写上两行ios::sync_with_stdio(false); cin.tie(nullptr);这两行关掉C输入输出流和C标准库的同步让cin/cout的速度接近scanf/printf。刷题量大了以后你会发现数据规模到百万级别时cin裸跑容易超时加这两行就稳得多。唯一的代价是不能混用cin和scanf否则可能出现数据错乱。再看多组数据时的读取。如果一行输入的是“字符串数字”先读字符串再读数字通常没问题。但如果上一行用cin n;读整数下一行用getline读字符串残留的换行符会被getline吃掉导致读到一个空串。这个坑我见过太多人踩了。解决办法读完整数后如果确实需要getline先调用一次getline(cin, dummy);把换行消费掉或者全部改用cin 按单词读取。输出格式方面最棘手的是“行末不能有多余空格”。比如要求输出“每个数之间用空格分隔”你可以在循环里判断for (int i 0; i n; i) { if (i) cout ; cout a[i]; }统一的处理思路是“第一个数前不输出空格其余的每一个数前都先补一个空格”。这个写法能通吃绝大多数要求。同理字符串拼接输出时逗号分隔也建议采用“先判断再输出分隔符”的模式我在第一道题代码里就是这么处理的。4.2 提交前的三个自测边界用例很多同学样例过了就直接交结果第一发就WA。我总结了一个三用例自测法针对不同类型的题都能用最小规模用例比如输入长度为1的字符串、1行1列的矩阵。这类用例能暴露数组越界、起始位置判断遗漏等基础错误。极限规模用例在本地生成一个长度10的5次方或者1000乘1000的数据。不用真把输出看完重点看程序运行时间是否肉眼可见地卡顿。如果卡顿明显说明算法复杂度有问题。无解/空数据用例矩阵题专门构造一个起点被障碍围死的例子字符串题构造全相同字符的例子。确保代码里的特判分支被真正执行到。这三个用例跑完再去提交一次AC的概率会提升很多。复试机试通常可以反复提交多次但每次提交都会留下记录在总分相同的情况下提交次数少本身也是一种优势所以尽量别“试错式提交”。4.3 做题顺序和时间分配西电机试的题目难度通常不是按顺序递增的第二题可能比第三题还难。我的建议是先花3到5分钟把所有题目都读一遍把每道题的预期难度标个号然后从最简单的题开始写。这里的“简单”定义为思路15分钟内能确定、代码量30行以内、边界情况一眼能看全。具体到时间分配上参考这个节奏时间区间任务前5分钟全部题目读一遍标注难度第6到60分钟搞定两到三道简单的题每题做完后立刻自测边界第60到90分钟集中攻剩下的一两道难题优先写暴力版本保底分最后30分钟不写新代码逐题检查格式、提交记录、特殊情况输出最后30分钟非常重要。很多人的失分不是题目不会而是输出格式不合格、变量没重置、多了空格之类的小问题。检查时可以把每道题的样例重新跑一遍再确认一下多组输入数据之间是否有需要清空的全局数组。宁可少做一道题也别让会做的题因为低级失误白丢分。5. 我复盘过的典型翻车现场以及一次上岸的机试准备建议5.1 最典型的几种致命失误我复盘过几届考生暴露的问题发现很多错误惊人地一致。第一种是全局变量多组数据间没有清空。比如全局开了cnt[26]上一组测试数据把cnt全部累加了一遍下一组进来时没有重新清零统计结果直接翻倍。这种错误在单个样例上永远不会暴露只有多组测试数据跑第二组时才出错非常隐蔽。第二种是递归爆栈。DFS题目如果用递归实现树的深度到几万层时系统栈会溢出。机试环境一般不会专门调大栈空间所以深度优先搜索优先考虑显式栈或者改成BFS。我见过有人死磕递归写法本地小数据全对OJ上一提交就Runtime Error到结束都没找到原因。第三种是只盯着样例输出做代码。题目的样例往往是最友好的数据隐藏数据会包含大量边界情况。如果你写的代码里到处是硬编码的“如果等于某个样例值就输出某个结果”这种魔法值写法一旦遇到真实数据必然崩。代码必须从算法逻辑上成立而不是针对样例拟合。第四种是看错快读快写的作用范围。ios::sync_with_stdio(false)之后再用scanf两个体系的数据缓冲会互相干扰。这属于输入输出体系混用的经典错误我在上一章提到过但每年都会扣住一批人。5.2 机试准备的两个月路线与模板库清单如果你准备复试的时间还剩八周我建议前四周主攻代码基本功后四周完全进入“限时模拟”状态。刷题范围优先选择蓝桥杯省赛真题、CCF CSP认证的前两题、华为机考的简单题这三类覆盖的题型与西电复试机试重叠度非常高。特别是CCF CSP它和西电机试同为OJ评测数据强度和判分逻辑非常接近能让你提前适应“交上去不一定AC”的真实手感。同时建立自己的代码模板库这几类高频代码建议事先写好并反复默写快读快写模板与多组输入的通用框架并查集、最小生成树、最短路径的经典实现BFS/DFS网格搜索模板含方向数组、访问标记快速幂、最大公约数、素数筛等基础数学函数自定义排序规则与priority_queue的使用模板模板的意义不是让你考场上去抄而是通过反复默写形成肌肉记忆。机试环境下人的思维速度会下降能不加思考写出来的部分越多留给难题分析的时间就越多。我当年的体会是BFS模板框架、方向数组、出入队标记这三段闭着眼都能写出来之后网格题基本就等于送分题了。最后再分享一个很多人忽略的细节复试前一定要在OJ平台上练几次提交而不是只在本地IDE里编译运行。本地IDE不会检查格式错、不会给你超时反馈更不会因为数组越界而报而是直接Runtime Error。一场机试的差距往往不在算法智商而在谁更早适应了“提交-评测-反馈”的这个节奏。提前熟悉了流程的人坐在考场里心态都不一样写起来自然顺。
西电计算机考研复试机试真题解析：字符串处理与BFS最短路AC代码
每年三月下旬西电的计算机复试机试都会刷掉一批笔试成绩还不错的人。原因往往不是题目有多难而是很多人到了机房才发现机试考的从来不是“会不会做”而是能不能在规定时间内把思路变成一份不越界、不超时、格式正确的AC代码。这篇内容我把2025年复试中按多位考生回忆综合还原的高频真题整理出来从解题思路到AC代码完整拆开讲再附上考场上的输入输出处理和边界测试心得。准备计算机考研、临近复试需要刷真题找手感、或者想了解西电机试风格的人这篇都值得看完。1. 西电计算机机试的考场画像规则、环境与真题的稳定面貌1.1 大概的考核方式与在线评测环境西电复试机试通常在机房进行使用在线评测系统提交代码。考生在本地写代码调试通过后把源码提交系统用若干组测试数据判分。评测环境以Linux下的g为主支持C和C不支持Python和其他脚本语言。所以哪怕你Python写得很溜复试前也一定要把手感和调试习惯切回C/C。时间上大致是两到三个小时完成多道题目具体题量和分值每年公告会有差异以当年官网通知为准。但有个规律很稳定评分不是按题目总数算平均而是按照通过测试点的比例给分。也就是说哪怕一道大题不会做只要把暴力版本写出来拿一部分分数也比死磕某一道题然后留白划算。这一点很多人考完才反应过来但已经来不及了。另一个容易忽略的点是环境里的编译器版本。我在备赛时习惯用新特性比如auto、vector、unordered_map这些在g编译下没问题。但如果你习惯用DEV-C这种老IDE里面默认的C标准可能比较旧机房评测时偶尔会出现编译不过的情况。建议统一提交风格头文件用#include bits/stdc.h尽量避免太依赖单编译器特性的写法。1.2 近几年题型频率统计与难度坐标结合考生回忆和公开经验帖西电机试的题目类型相当集中很少出偏题怪题。我把近几年的高频考点整理成一张表难度参照大家比较熟悉的蓝桥杯省赛和CCF CSP认证考点大类出现频率难度坐标典型考察方式字符串处理很高CSP第1题到第2题之间统计字符、加密替换、子串处理模拟题很高蓝桥杯省赛简单题按规则一步步走完流程边界多搜索BFS/DFS中高图论入门题网格最短路、连通块、迷宫可行性排序与贪心中高CSP第2题区间问题、自定义排序、优先级队列基础数学中蓝桥杯省赛简单题最大公约数、素数判断、进制转换这个规律背后是学校的考察倾向复试机试更在意把算法思路转化为可运行代码的稳定度而不是竞赛式的高难度技巧。所以很多题你看着眼熟但拿满分需要把细节处理干净。下面两道还原题就很好地体现了这种风格。2. 第一道还原题字符串统计与循环偏移思路推演 AC 代码2.1 题目原貌按考场回忆还原这道题是2025年复试中多人提到的字符串处理题。按回忆综合还原后的描述如下给定一个仅由小写字母组成的字符串S长度不超过10的5次方。先统计每个字符出现的次数并按照字符在字符串中第一次出现的位置顺序输出“字符:次数”。然后对S中的每个字符进行循环替换假设当前字符为c它在原串中出现过cnt次就把c替换为字母表中往后数cnt个位置的字母。这里的“往后数”是循环的即z的后面又回到a。请输出统计结果和替换后的字符串。输入格式第一行一个整数T表示测试组数接下来T行每行一个字符串S。输出格式每组数据输出两行第一行为统计结果字符之间用英文逗号分隔第二行为替换后的字符串。样例输入2 aaba abc样例输出a:3,b:1 ddca a:1,b:1,c:1 bcd第一组里a出现3次所以替换为db出现1次替换为c原串aaba变成ddca。第二组abc三个字符各出现1次整体向后移动一位变成bcd。2.2 拿到题目后先不急着写码三种方案的推演这种题一眼看穿是“统计映射”的组合但在考场上最好先花一两分钟把流程拆清楚。我看到题的第一反应是先画处理流水线统计出现次数 → 记录首次出现顺序 → 输出统计 → 遍历原串做循环偏移。这条流水线定下来之后代码结构就不会乱。方案一可以直接用两层循环每遇到一个没处理过的字符就去遍历整个串统计次数、找首次出现位置。这样做时间复杂度和字符串长度相关单层处理还好T组数据全部上来后会达到平方量级。机试数据如果拉满10的5次方这种写法就跑不动了。字符串题考察的核心之一就是能不能想到用数组当哈希表。方案二用int cnt[26]数组统计每个字母出现次数同时用一个vectorchar按首次出现顺序记录字符种类。判断“是否已经记录过”可以用bool in[26]辅助。这个思路是正确的时间复杂度降到线性的字符长度空间上只需要常数级别。这也是我最终采用的方案。方案三可能会有同学想到用mapchar,int觉得自带排序更省事。但这里有个关键差别题目要的是首次出现顺序不是字典序。如果用map字符会按a-z输出直接和题目要求拧着来。除非额外记录首次出现位置再排序否则不如数组方案简洁。很多人在这一处翻车不是不会写而是没读懂“首次出现顺序”这五个字。2.3 AC代码与关键点逐段说明#include bits/stdc.h using namespace std; void solve(const string s) { int cnt[26] {0}; bool in[26] {false}; vectorchar firstSeen; for (char ch : s) { int idx ch - a; if (!in[idx]) { in[idx] true; firstSeen.push_back(ch); } cnt[idx]; } for (size_t i 0; i firstSeen.size(); i) { if (i) cout ,; cout firstSeen[i] : cnt[firstSeen[i] - a]; } cout \n; for (char ch : s) { int idx ch - a; int nxt (idx cnt[idx]) % 26; cout char(a nxt); } cout \n; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int T; cin T; while (T--) { string s; cin s; solve(s); } return 0; }第一段的cnt和in是配套使用的。in数组只负责标记“这种字符有没有在firstSeen里”避免后面输出统计时产生重复项。每遇到一个新字符就把它push进firstSeen这比遍历26个字母判断cnt[i] 0要更贴近“首次出现顺序”的语义。因为如果直接遍历26个字母输出就会变成字典序这是最常见的错误。第二段输出统计结果的时候用firstSeen[i] - a去取对应次数。注意这里不能直接用cnt[i]因为i是vector下标不是字母下标。第一个字符是a时两者刚好相等换成b、c之后就全乱了。这个细节我在写完自测时专门验证过。第三段替换逻辑里最核心的是(idx cnt[idx]) % 26。这里如果忘了取模字符ch的偏移会越界比如z出现10次不加取模直接加到整数上会超过122输出的字符就变成各种符号。循环字母表的题取模注定躲不掉。还有一个容易被忽视的点传入solve函数的是按引用传递的字符串函数内不修改它只读取。如果拷贝一份到函数里字符串长度10的5次方、T组1万次时拷贝开销会明显拖慢程序。这种级别的优化不需要刻意追求但“能传引用就不传值”的习惯在机试的紧张状态下能省下不少时间。2.4 这道题的变形方向与常见套路西电对字符串题的偏好在这道题上体现得很典型要求你同时处理好统计、顺序、映射、循环四件事。考场上如果觉得太简单也别放松因为它的变形可能出现在后续年份把“首次出现顺序”改成“按出现次数降序、次数相同按字典序”这时就需要自定义排序规则考察点变成排序稳定性。把“出现次数”改成“最后一次出现的位置”或“所有出现位置之和”作为偏移量代码结构不变但计算方式要跟着换。增加输出格式要求比如每组之间空一行、统计结果末尾不允许有多余逗号这种格式陷阱专门用来刷掉不仔细读题的人。准备这类题时建议把统计、首现顺序、排序三种能力分别练熟考场上就能根据题目的要求快速拼接。尤其是“按首现顺序输出”这种细节很多非竞赛选手容易默认成字典序一失手就是整题零分。3. 第二道还原题0/1 网格上的 BFS 最短路思路推演 AC 代码3.1 题目原貌按考场回忆还原搜索题在西电机试里的重要程度不用多说。下面这道是2025年复试里被多次提及的网格题按回忆综合还原如下给定一个n行m列的0/1矩阵0表示可以通过1表示障碍物。一个人从左上角(0,0)出发每次可以向上、下、左、右四个方向移动一格不能走出矩阵也不能走到障碍物上。问到达右下角(n-1,m-1)所需的最少步数如果无法到达则输出-1。输入格式第一行两个整数n和m之后n行每行m个整数每个整数为0或1。样例输入5 4 0 0 0 1 1 1 0 1 1 0 0 1 1 1 0 0 0 0 0 0样例输出7从(0,0)出发沿着能走通的通道一路绕行到(4,3)最短步数确实是7。验证路径向右到(0,1)再向右到(0,2)向下到(1,2)向下到(2,2)向下到(3,2)向下到(4,2)向右到(4,3)一共7步。3.2 为什么遇到“最少步数”优先选 BFS 而不是 DFS网格上求最短步数标准解是BFS。原因是BFS天然按层扩展起点出发先到距离1的所有点再到距离2的所有点所以第一次从队列中弹出终点时记录下来的步数一定是最小步数。这也是BFS能保证最短路的性质和边上权重为1的前提绑定。有人会问DFS能不能做当然能但DFS的“深挖到底再回头”机制决定了它首次到达终点时走过的路径不一定最短。如果要用DFS找最短路必须把所有可达路径全部遍历完再取最小值相当于暴力枚举所有路径复杂度随网格变大快速爆炸。在矩阵1000乘1000这种规模下DFS求最短路基本不可能通过全部测试点。BFS还有个额外好处它对空间的要求也可控。每个节点入队一次最多把整张图都放进队列内存上限可以提前估算。1000乘1000的矩阵有100万个格子队列里同时存活的最坏情况也不会超过节点总数内存完全够用。只要入队的同时做访问标记避免重复入队BFS的稳定性是四种常见搜索里最高的。3.3 AC代码与网格边界处理的四个关键动作#include bits/stdc.h using namespace std; struct Node { int x, y, step; }; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, m; cin n m; vectorvectorint a(n, vectorint(m, 0)); for (int i 0; i n; i) { for (int j 0; j m; j) { cin a[i][j]; } } if (a[0][0] 1 || a[n - 1][m - 1] 1) { cout -1 \n; return 0; } const int dx[4] {-1, 1, 0, 0}; const int dy[4] {0, 0, -1, 1}; vectorvectorint vis(n, vectorint(m, 0)); queueNode q; q.push({0, 0, 0}); vis[0][0] 1; while (!q.empty()) { Node cur q.front(); q.pop(); if (cur.x n - 1 cur.y m - 1) { cout cur.step \n; return 0; } for (int k 0; k 4; k) { int nx cur.x dx[k]; int ny cur.y dy[k]; if (nx 0 || nx n || ny 0 || ny m) continue; if (vis[nx][ny] || a[nx][ny] 1) continue; vis[nx][ny] 1; q.push({nx, ny, cur.step 1}); } } cout -1 \n; return 0; }代码里最关键的是起点和终点特判。如果左上角就是障碍物或者右下角是障碍物直接输出-1这一行能避免后面BFS的空转。很多人漏掉这个判断导致起点入队后立刻被弹出来最终输出错误结果。考试时不要觉得这种判断多余边界数据往往就在这里设伏。方向数组dx/dy的顺序无所谓但四个方向必须覆盖完整上、下、左、右。少一个方向某些能通行的路径就走不到。这里我用两个一维数组比存四个坐标对写起来更紧凑。移动后先检查越界再检查访问标记和障碍物顺序反了会导致访问vis[nx][ny]时代码访问越界下标出现运行时错误。访问标记放在入队时置位而不是出队时置位。这个细节非常关键。如果在弹出节点时才标记同一个节点可能被多个邻居重复入队队列中会出现大量冗余节点最坏情况下运行时间成倍增长甚至在极端数据下引发内存问题。BFS模板中“入队即标记”是必须养成的肌肉记忆。3.4 搜索题的进阶优化思路如果今年考题在网格上增加条件比如“有k点体力每走一步消耗1点某些格子上可以恢复体力”那状态就从二元组变成三元组vis需要升级成vis[x][y][power]BFS框架仍然成立只是队列节点里多一个字段。如果变成“某些格子只能走一次”那就得在状态里记录已访问集合复杂度会明显上升这种题出现在复试里的概率不大但心里有数总比毫无准备强。对于一般复试题的网格规模vectorvectorint二维数组足够。但如果你担心初始化耗时或者矩阵接近1000乘1000可以用一维数组手动映射下标idx x * m y代码稍复杂但访问更紧凑。我在考场上习惯二维写法因为可读性优先调试也直观。4. 考场键盘生存手册输入输出、边界测试与提交顺序4.1 输入输出模板与格式化陷阱机试中因为输入输出格式失分是最可惜的。常见坑位有三个cin和scanf混用、多组测试数据的残留字符、输出行尾多余空格。先看输入加速。我在代码开头固定写上两行ios::sync_with_stdio(false); cin.tie(nullptr);这两行关掉C输入输出流和C标准库的同步让cin/cout的速度接近scanf/printf。刷题量大了以后你会发现数据规模到百万级别时cin裸跑容易超时加这两行就稳得多。唯一的代价是不能混用cin和scanf否则可能出现数据错乱。再看多组数据时的读取。如果一行输入的是“字符串数字”先读字符串再读数字通常没问题。但如果上一行用cin n;读整数下一行用getline读字符串残留的换行符会被getline吃掉导致读到一个空串。这个坑我见过太多人踩了。解决办法读完整数后如果确实需要getline先调用一次getline(cin, dummy);把换行消费掉或者全部改用cin 按单词读取。输出格式方面最棘手的是“行末不能有多余空格”。比如要求输出“每个数之间用空格分隔”你可以在循环里判断for (int i 0; i n; i) { if (i) cout ; cout a[i]; }统一的处理思路是“第一个数前不输出空格其余的每一个数前都先补一个空格”。这个写法能通吃绝大多数要求。同理字符串拼接输出时逗号分隔也建议采用“先判断再输出分隔符”的模式我在第一道题代码里就是这么处理的。4.2 提交前的三个自测边界用例很多同学样例过了就直接交结果第一发就WA。我总结了一个三用例自测法针对不同类型的题都能用最小规模用例比如输入长度为1的字符串、1行1列的矩阵。这类用例能暴露数组越界、起始位置判断遗漏等基础错误。极限规模用例在本地生成一个长度10的5次方或者1000乘1000的数据。不用真把输出看完重点看程序运行时间是否肉眼可见地卡顿。如果卡顿明显说明算法复杂度有问题。无解/空数据用例矩阵题专门构造一个起点被障碍围死的例子字符串题构造全相同字符的例子。确保代码里的特判分支被真正执行到。这三个用例跑完再去提交一次AC的概率会提升很多。复试机试通常可以反复提交多次但每次提交都会留下记录在总分相同的情况下提交次数少本身也是一种优势所以尽量别“试错式提交”。4.3 做题顺序和时间分配西电机试的题目难度通常不是按顺序递增的第二题可能比第三题还难。我的建议是先花3到5分钟把所有题目都读一遍把每道题的预期难度标个号然后从最简单的题开始写。这里的“简单”定义为思路15分钟内能确定、代码量30行以内、边界情况一眼能看全。具体到时间分配上参考这个节奏时间区间任务前5分钟全部题目读一遍标注难度第6到60分钟搞定两到三道简单的题每题做完后立刻自测边界第60到90分钟集中攻剩下的一两道难题优先写暴力版本保底分最后30分钟不写新代码逐题检查格式、提交记录、特殊情况输出最后30分钟非常重要。很多人的失分不是题目不会而是输出格式不合格、变量没重置、多了空格之类的小问题。检查时可以把每道题的样例重新跑一遍再确认一下多组输入数据之间是否有需要清空的全局数组。宁可少做一道题也别让会做的题因为低级失误白丢分。5. 我复盘过的典型翻车现场以及一次上岸的机试准备建议5.1 最典型的几种致命失误我复盘过几届考生暴露的问题发现很多错误惊人地一致。第一种是全局变量多组数据间没有清空。比如全局开了cnt[26]上一组测试数据把cnt全部累加了一遍下一组进来时没有重新清零统计结果直接翻倍。这种错误在单个样例上永远不会暴露只有多组测试数据跑第二组时才出错非常隐蔽。第二种是递归爆栈。DFS题目如果用递归实现树的深度到几万层时系统栈会溢出。机试环境一般不会专门调大栈空间所以深度优先搜索优先考虑显式栈或者改成BFS。我见过有人死磕递归写法本地小数据全对OJ上一提交就Runtime Error到结束都没找到原因。第三种是只盯着样例输出做代码。题目的样例往往是最友好的数据隐藏数据会包含大量边界情况。如果你写的代码里到处是硬编码的“如果等于某个样例值就输出某个结果”这种魔法值写法一旦遇到真实数据必然崩。代码必须从算法逻辑上成立而不是针对样例拟合。第四种是看错快读快写的作用范围。ios::sync_with_stdio(false)之后再用scanf两个体系的数据缓冲会互相干扰。这属于输入输出体系混用的经典错误我在上一章提到过但每年都会扣住一批人。5.2 机试准备的两个月路线与模板库清单如果你准备复试的时间还剩八周我建议前四周主攻代码基本功后四周完全进入“限时模拟”状态。刷题范围优先选择蓝桥杯省赛真题、CCF CSP认证的前两题、华为机考的简单题这三类覆盖的题型与西电复试机试重叠度非常高。特别是CCF CSP它和西电机试同为OJ评测数据强度和判分逻辑非常接近能让你提前适应“交上去不一定AC”的真实手感。同时建立自己的代码模板库这几类高频代码建议事先写好并反复默写快读快写模板与多组输入的通用框架并查集、最小生成树、最短路径的经典实现BFS/DFS网格搜索模板含方向数组、访问标记快速幂、最大公约数、素数筛等基础数学函数自定义排序规则与priority_queue的使用模板模板的意义不是让你考场上去抄而是通过反复默写形成肌肉记忆。机试环境下人的思维速度会下降能不加思考写出来的部分越多留给难题分析的时间就越多。我当年的体会是BFS模板框架、方向数组、出入队标记这三段闭着眼都能写出来之后网格题基本就等于送分题了。最后再分享一个很多人忽略的细节复试前一定要在OJ平台上练几次提交而不是只在本地IDE里编译运行。本地IDE不会检查格式错、不会给你超时反馈更不会因为数组越界而报而是直接Runtime Error。一场机试的差距往往不在算法智商而在谁更早适应了“提交-评测-反馈”的这个节奏。提前熟悉了流程的人坐在考场里心态都不一样写起来自然顺。
