去年备考哈工大计算机考研的时候最让我心里没底的就是复试机试。网上能找到的所谓真题大多来自论坛里学长的口述回忆不少题目连输入输出格式都缺失更别提配套的AC代码了。我把能翻到的经验帖、回忆帖全部过了一遍再结合哈工大机试一贯的出题偏好整理出三道高频考点还原题配套完整的解题思路和可直接运行的C代码就是这篇文章的主体。如果你正在准备2025年复试把这三道题练熟再掌握最后一节的考场习惯机试这关基本稳了。先说明一个现实机试的题目采集方式决定了很少有人能把原题完整复述出来所以任何网上流传的真题都带有回忆和还原的成分。以下三道题是对近几年考生回忆中高频题型的整理个别细节可能与考场原题有差异但解题思路、代码模板、边界坑点都是实打实通用的。1. 哈工大复试机试的整体盘面题型、环境与备考重心1.1 机试的运行规则时长、题量、判题方式从我了解到的近几届情况看哈工大复试机试通常安排在3月中下旬的复试周内时长为3小时左右题量在3到4道之间。编程语言基本限定在C/C在线判题系统会自动评测并实时返回结果。和平时刷OJ最大的区别是部分年份采用动态抽题每个人拿到的题目可能不同但整体难度分布会保持一致。这里有一个很关键的建议报名后一定去学院官网把当年的机试说明读一遍重点确认编译器的具体版本、是否支持C11/17语法、判题要求的输入输出格式。我见过有人因为默认使用cin/cout的同步关闭方式和QuickIO混用后导致输出顺序异常白白丢掉大分这种问题完全是可以在考前规避的。1.2 高频考点分布一张表看懂出题偏好结合近几年考生回忆我整理了一张主观估算的考点分布表注意这不是官方统计只是帮助大家分配复习精力的参考考点类别估算占比典型题型模拟与字符串处理30% - 40%日期计算、进制转换、日志统计、格式解析数据结构应用15% - 20%map/set去重、栈与队列模拟、堆排序图论15% - 20%最短路、最小生成树、拓扑排序动态规划15% - 20%背包问题、LIS、编辑距离数学与数论5% - 10%最大公约数、素数筛、矩阵快速幂从这张表能看出两个信息。第一简单模拟题占比最高属于必拿分项第二动态规划和图论几乎年年出现是拉开差距的关键。字符串处理和STL容器的熟练度直接决定了前面简单题做得快不快而简单题做得快后面才有充足时间啃硬骨头。1.3 针对2025年备考的三轮复习节奏如果初试结束后才开始准备机试时间其实是够的但必须按节奏来。第一轮1月中下旬到2月初把《王道机试指南》的常见题型刷完或者用牛客网的考研机试题库练基础。这一轮不求AC速度目标是把模拟、排序、查找、图论、DP的常见套路过一遍确保看到题目能识别出考点。第二轮2月初到2月底集中做目标院校的回忆版真题。这一轮重点不是做对而是做一张错题表记录每道题的考点、出错原因、正确思路。我自己的经验是这一轮最容易暴露问题比如知道是DP但想不到状态定义、写Dijkstra时忘了处理重边这些问题越早暴露越好。第三轮考前10天到考前每天限时3小时做一套完整模拟题必须用机试同款编译器必须全程敲键盘不能一看不会就翻题解。这一轮练的是考场的节奏感和临场反应手速和判断力的提升往往比刷题量更明显。2. 第一题还原学生提交记录统计——map与set的组合拳2.1 题面还原先看题面。某在线评测系统记录了所有学生的提交行为请你统计每个学生的最终成绩。输入多行记录每行包含三个字段学号整数、题目编号形如P001的字符串、提交结果AC、WA、RE、TLE之一所有记录以EOF结束。输出按AC题目数降序若AC题目数相同则按总提交次数升序若仍相同则按学号升序输出每个学生的学号、AC题目数、总提交次数、AC率百分数保留两位小数。样例输入2023001 P001 AC 2023002 P001 WA 2023001 P002 AC 2023001 P001 WA 2023002 P001 AC 2023003 P003 WA样例输出2023001 2 3 66.67% 2023002 1 2 50.00% 2023003 0 1 0.00%注意同一个人同一道题即使AC过多次AC题目数也只计一次。2.2 破题思路去重计数是核心这道题从算法难度上说不算难题真正的考察点在于你能不能精炼地用STL完成去重和排序两件事。AC题目数要求同人同题去重学号和题号是一对多的关系最直接的结构就是maplong long, setstring。set天然去重不需要你手动判断这道题之前是否AC过。很多同学第一反应是用二维bool数组做去重比如bool ac[学号范围][题号范围]。但这个思路有两个硬伤一是题号是字符串不是连续整数二是学号和题号范围都不固定开数组很容易开小或开大。map/set这种动态结构才是正解。这里不必特意用unordered_map普通map的O(logN)查找在几千条记录的量级下毫无压力代码也更稳定。另一个容易踩的坑是遍历对象。如果你的循环只遍历存了AC记录的map就会漏掉那些交过WA但从未AC的学生。这道题要统计的对象是所有出现过提交记录的学生所以必须在外层遍历submitCnt这个记录总提交次数的map再用acSet.count(id)去判断该学生是否有AC记录。2.3 AC代码与逐段讲解#include bits/stdc.h using namespace std; struct Student { long long id; int solved; int total; }; int main() { ios::sync_with_stdio(false); cin.tie(0); long long id; string pid, result; maplong long, setstring acSet; // 学号 - 已AC的题目编号集合 maplong long, int submitCnt; // 学号 - 总提交次数 while (cin id pid result) { submitCnt[id]; if (result AC) { acSet[id].insert(pid); } } vectorStudent v; for (auto itr : submitCnt) { long long sid itr.first; int total itr.second; int solved acSet.count(sid) ? (int)acSet[sid].size() : 0; v.push_back({sid, solved, total}); } sort(v.begin(), v.end(), [](const Student a, const Student b) { if (a.solved ! b.solved) return a.solved b.solved; if (a.total ! b.total) return a.total b.total; return a.id b.id; }); cout fixed setprecision(2); for (auto stu : v) { double rate stu.total 0 ? 0.0 : (double)stu.solved / stu.total * 100.0; cout stu.id stu.solved stu.total rate %\n; } return 0; }代码的核心逻辑分三个部分。读入阶段用while循环处理EOF结尾的多行数据每次读到一条记录就累加submitCnt如果是AC再往acSet里插入题目编号。统计阶段遍历submitCnt对每个学生通过acSet取去重后的AC题数。排序阶段用lambda表达式实现自定义规则先比AC题数降序再比总提交次数升序最后比学号升序。2.4 这道题最容易丢分的三个细节细节一多组输入不能写死循环次数。我在练习时见过不少同学先读一个n再循环n次但机试这题没有给出总记录数必须以EOF结束也就是必须用while (cin id pid result)这种写法。细节二AC率的计算方式。AC率等于AC题目数除以总提交次数而不是AC提交次数除以总提交次数。以样例中的2023001为例总提交3次其中P001提交了两次一次AC一次WAP002提交一次AC所以AC题目数是2AC率是2/3而不是2/2。细节三输出格式。题目要求保留两位小数并带百分号用cout fixed setprecision(2)之后再输出数字比较稳妥。注意不要在这里混用printf和cout具体原因会在后面第五部分展开。3. 第二题还原数据中心传输延迟——堆优化Dijkstra的完整模板3.1 题面还原N个数据中心节点编号从1到NM条光纤链路。每条链路给出起点u、终点v和传输延迟w。现在要从1号节点向N号节点发送数据求最小传输延迟如果不可达则输出-1。输入第一行两个整数N、M接下来M行每行三个整数u、v、w。N最大可到10^5M最大可到2 * 10^5w为非负整数。输出一个整数表示从1到N的最小延迟不可达输出-1。样例输入4 5 1 2 1 1 3 4 2 3 2 2 4 6 3 4 2样例输出53.2 算法选型为什么是堆优化Dijkstra看到数据范围第一反应就是不能用O(N^3)的Floyd也不能用O(N*M)的Bellman-Ford。剩下的可选方案主要是SPFA和堆优化Dijkstra。SPFA在平均情况下很快但在复试OJ这种故意卡数据的场景里它的最坏复杂度是O(N*M)一旦出题人构造了稠密图或网状图超时是大概率事件。堆优化Dijkstra的复杂度是O((NM)logN)在N10^5、M2*10^5的规模下完全可控。Dijkstra能成立的本质是贪心每次从优先队列弹出的节点其当前距离一定是全局最小值这个节点一旦被确定就不会再有其他路径能把它更新得更小。这一点依赖于所有边权非负只要题目没有负权边Dijkstra就是最稳的选择。3.3 Dijkstra模板与AC代码用邻接表存图vectorEdge graph[MAXN]的方式在稀疏图下比邻接矩阵省内存得多。10^5个节点的邻接矩阵根本开不出来邻接表是唯一合理的选择。#include bits/stdc.h using namespace std; const int MAXN 100005; const long long INF 0x3f3f3f3f3f3f3f3fLL; struct Edge { int to, w; }; vectorEdge graph[MAXN]; long long dist[MAXN]; bool vis[MAXN]; int main() { ios::sync_with_stdio(false); cin.tie(0); int n, m; cin n m; for (int i 0; i m; i) { int u, v, w; cin u v w; graph[u].push_back({v, w}); } fill(dist, dist n 1, INF); dist[1] 0; priority_queuepairlong long, int, vectorpairlong long, int, greaterpairlong long, int pq; pq.push({0, 1}); while (!pq.empty()) { auto [d, u] pq.top(); pq.pop(); if (vis[u]) continue; vis[u] true; if (u n) break; for (auto e : graph[u]) { if (!vis[e.to] dist[e.to] d e.w) { dist[e.to] d e.w; pq.push({dist[e.to], e.to}); } } } if (dist[n] INF) cout -1 \n; else cout dist[n] \n; return 0; }判题逻辑是优先队列每次弹出距离最小的节点vis[u]确保每个节点只被真正处理一次。当弹出终点n时可以提前退出节约时间。这里用auto [d, u] pq.top()是C17的结构化绑定写法考前务必确认编译环境支持。3.4 考场上的边界情况重边、自环、大整数这个题考场上的翻车点不在算法本身而在各种边界数据的处理。第一源点等于终点。N1时dist[1]初始为0循环可能根本不会进入直接输出0。如果你把输出条件写成dist[n] INF判断不可达就不会出错。第二重边。同一对节点之间可能出现多条不同权值的边Dijkstra不需要特殊处理松弛操作只会保留最小的那个距离。前提是你不要在加边时自作聪明地只保留最小边那就可能把考场上的判题逻辑搞复杂了。第三自环。自环边的权值如果为正松弛不成立不影响结果如果为0松弛会让dist[e.to]等于自己本身也没有问题。第四INF的取值。如果用int INF 0x7fffffff一旦计算d e.w就可能溢出成负数导致距离被错误更新。稳妥做法是const long long INF 0x3f3f3f3f3f3f3f3fLL这个值在long long范围内足够大而且两个这样的数相加不会溢出。4. 第三题还原字符串编辑距离——从转移方程到滚动数组4.1 题面还原给定两个字符串s和t每次可以对s进行三种操作之一插入一个字符删除一个字符替换一个字符。求把s变成t的最少操作次数。输入多组测试用例每组一行包含两个字符串中间用空格分隔。字符串长度不超过2000。输出每组用例输出一个整数表示最小编辑距离。样例输入cat cut horse ros样例输出1 34.2 状态推导把编辑操作翻译成转移方程这类题的经典思路是定义二维DP状态dp[i][j]表示字符串s的前i个字符变成字符串t的前j个字符所需的最少操作次数。为什么要用两个维度因为两个字符串的前缀互相独立子问题的维度天然是两个字符串的长度。接下来把三种操作和转移方程一一对应。如果最后一步是插入操作说明s的前i个字符已经变成了t的前j-1个字符然后再在末尾插入一个字符补上t的第j个字符所以转移是dp[i][j-1] 1。如果最后一步是删除操作说明s的前i-1个字符变成t的前j个字符然后把s的第i个字符删掉转移是dp[i-1][j] 1。如果最后一步是替换操作那要看第i个字符和第j个字符是否相等——相等就不需要操作不相等就替换一次转移是dp[i-1][j-1] (s[i-1] t[j-1] ? 0 : 1)。初始化也很直观dp[0][j] j表示空串变成t的前j个字符需要逐字符插入j次dp[i][0] i表示s的前i个字符变成空串需要删除i次。填表顺序是从上到下、从左到右因为每个dp[i][j]只依赖左方、上方和左上方的值。以样例cat到cut为例填完整个表之后右下角的值就是答案。手动模拟一遍会加深理解dpcut0123c1012a2112t3221右下角的1就是最终答案因为只需要把中间的a替换成u。4.3 AC代码从二维数组到滚动数组首先写最直观的二维DP版本长度2000的字符串开2001 * 2001的int数组占内存约16MB完全能接受#include bits/stdc.h using namespace std; int minDistance(const string s, const string t) { int n s.size(), m t.size(); vectorvectorint dp(n 1, vectorint(m 1, 0)); for (int i 0; i n; i) dp[i][0] i; for (int j 0; j m; j) dp[0][j] j; for (int i 1; i n; i) { for (int j 1; j m; j) { int insertCost dp[i][j - 1] 1; int deleteCost dp[i - 1][j] 1; int replaceCost dp[i - 1][j - 1] (s[i - 1] t[j - 1] ? 0 : 1); dp[i][j] min({insertCost, deleteCost, replaceCost}); } } return dp[n][m]; } int main() { string s, t; while (cin s t) { cout minDistance(s, t) \n; } return 0; }如果题目把字符串长度提到10^5级别二维数组就不行了这时候用滚动数组把空间压到O(m)。滚动数组的精髓是我们只关心当前行和上一行所以只需要两个一维数组甚至一个一维数组加两个临时变量。int minDistance_roll(const string s, const string t) { int n s.size(), m t.size(); vectorint dp(m 1, 0); for (int j 0; j m; j) dp[j] j; for (int i 1; i n; i) { int prev dp[0]; // prev 相当于 dp[i-1][j-1]初始时是 dp[i-1][0] dp[0] i; // dp[i][0] i for (int j 1; j m; j) { int temp dp[j]; // 先保存 dp[i-1][j]因为马上要被覆盖 int insertCost dp[j - 1] 1; int deleteCost temp 1; int replaceCost prev (s[i - 1] t[j - 1] ? 0 : 1); prev temp; // 这个 temp 将成为下一轮 j1 的 prev即 dp[i-1][j] dp[j] min({insertCost, deleteCost, replaceCost}); } } return dp[m]; }这里最容易出错的是deleteCost到底该用哪个值。如果写成dp[j] 1那么dp[j]在当前行的更新循环里已经被新值覆盖了已经不是上一行的dp[i-1][j]。所以必须在覆盖前用temp保存旧值再在之后把temp传给prev确保下一轮的replaceCost拿到的是真正的dp[i-1][j-1]。4.4 为什么编辑距离是复试机试的高频常客编辑距离这个模型在机试里出现频率高原因有三。第一它考察的是动态规划最核心的思想——状态定义和转移方程的推导这一能力是复试筛选的关键。第二它的实现复杂度不高只要思路清晰十五分钟之内写完完整代码并不难适合作为中等难度的拉开差距题。第三它可以延伸出空间优化、路径回溯、不同操作代价等多种变体一道题就能考察出考生的基本功是否扎实。我自己的经验是很多同学在考场上不是不会DP而是对滚动数组不熟或者下标从0开始还是从1开始搞混。建议平时练习时就固定一套自己熟悉的状态定义和初始化写法考场上不要临时换思路。5. 从读题到AC机试现场的提分习惯与代码模板5.1 我固定的读题与自测流程机试时间有限但不能因为赶时间而跳过读题。我给自己定的流程是拿到题目先看数据范围N、M、字符串长度直接决定了该用什么复杂度的算法然后拿样例走一遍流程搞清楚输入字段之间的对应关系最后才动键盘写代码。写完之后不要急着提交先跑一遍样例再自己构造2到3组边界数据。举几个我常用的自测例子。Dijkstra题构造一个N1, M0的输入正确输出应该是0。编辑距离题构造两个空字符串正确输出是0。模拟统计题构造一个全部提交都是WA的学生确认它能正常输出而不是被漏掉。这些边界数据跑通之后提交的通过率会大幅提升。5.2 两个能救命的小模板快速IO与INF取值机试里IO处理是第一个坑。C的标准做法是保留cin但必须关闭同步ios::sync_with_stdio(false); cin.tie(0);这两行写在main函数开头能让cin的读入速度接近scanf。但注意关闭同步之后就不能再混用printf和scanf了否则输出顺序可能错乱。我在模拟训练时见过太多人写着写着就混用了这个习惯要刻意改掉。第二个模板是INF取值。0x3f3f3f3f是int长度的经典选择两个0x3f3f3f3f相加约等于8.1亿不会超过int上限21亿做松弛时不会溢出。long long版本则是0x3f3f3f3f3f3f3f3fLL。把这个值背下来比用INT_MAX或LLONG_MAX安全得多。5.3 考场时间分配和心态管理拿到题目后切忌直接扑向第一题闷头写。先把3到4道题全部读一遍在心里快速给每道题打难度标签。我的分配策略是先做最有把握的题拿到稳稳的分数遇到卡壳超过20分钟的题果断跳过先把其他题做完最后还剩时间再回头啃硬题。机试的判分是按通过情况给分把会的题写对远比死磕一道不会的题划算。心态上要接受一个事实不可能每道题都能AC。我考完最大的感触是很多失分不是不会做而是细节处理不到位——比如多组输入的终止条件没处理好比如排序规则写反比如数组开小了1个下标。如果你现在开始准备把文中三道题按独立写一遍、对照代码补细节、隔天重写一遍的节奏练到考场上这些坑就踩不到你了。
哈工大计算机考研复试机试高频题精讲：STL、Dijkstra与编辑距离
去年备考哈工大计算机考研的时候最让我心里没底的就是复试机试。网上能找到的所谓真题大多来自论坛里学长的口述回忆不少题目连输入输出格式都缺失更别提配套的AC代码了。我把能翻到的经验帖、回忆帖全部过了一遍再结合哈工大机试一贯的出题偏好整理出三道高频考点还原题配套完整的解题思路和可直接运行的C代码就是这篇文章的主体。如果你正在准备2025年复试把这三道题练熟再掌握最后一节的考场习惯机试这关基本稳了。先说明一个现实机试的题目采集方式决定了很少有人能把原题完整复述出来所以任何网上流传的真题都带有回忆和还原的成分。以下三道题是对近几年考生回忆中高频题型的整理个别细节可能与考场原题有差异但解题思路、代码模板、边界坑点都是实打实通用的。1. 哈工大复试机试的整体盘面题型、环境与备考重心1.1 机试的运行规则时长、题量、判题方式从我了解到的近几届情况看哈工大复试机试通常安排在3月中下旬的复试周内时长为3小时左右题量在3到4道之间。编程语言基本限定在C/C在线判题系统会自动评测并实时返回结果。和平时刷OJ最大的区别是部分年份采用动态抽题每个人拿到的题目可能不同但整体难度分布会保持一致。这里有一个很关键的建议报名后一定去学院官网把当年的机试说明读一遍重点确认编译器的具体版本、是否支持C11/17语法、判题要求的输入输出格式。我见过有人因为默认使用cin/cout的同步关闭方式和QuickIO混用后导致输出顺序异常白白丢掉大分这种问题完全是可以在考前规避的。1.2 高频考点分布一张表看懂出题偏好结合近几年考生回忆我整理了一张主观估算的考点分布表注意这不是官方统计只是帮助大家分配复习精力的参考考点类别估算占比典型题型模拟与字符串处理30% - 40%日期计算、进制转换、日志统计、格式解析数据结构应用15% - 20%map/set去重、栈与队列模拟、堆排序图论15% - 20%最短路、最小生成树、拓扑排序动态规划15% - 20%背包问题、LIS、编辑距离数学与数论5% - 10%最大公约数、素数筛、矩阵快速幂从这张表能看出两个信息。第一简单模拟题占比最高属于必拿分项第二动态规划和图论几乎年年出现是拉开差距的关键。字符串处理和STL容器的熟练度直接决定了前面简单题做得快不快而简单题做得快后面才有充足时间啃硬骨头。1.3 针对2025年备考的三轮复习节奏如果初试结束后才开始准备机试时间其实是够的但必须按节奏来。第一轮1月中下旬到2月初把《王道机试指南》的常见题型刷完或者用牛客网的考研机试题库练基础。这一轮不求AC速度目标是把模拟、排序、查找、图论、DP的常见套路过一遍确保看到题目能识别出考点。第二轮2月初到2月底集中做目标院校的回忆版真题。这一轮重点不是做对而是做一张错题表记录每道题的考点、出错原因、正确思路。我自己的经验是这一轮最容易暴露问题比如知道是DP但想不到状态定义、写Dijkstra时忘了处理重边这些问题越早暴露越好。第三轮考前10天到考前每天限时3小时做一套完整模拟题必须用机试同款编译器必须全程敲键盘不能一看不会就翻题解。这一轮练的是考场的节奏感和临场反应手速和判断力的提升往往比刷题量更明显。2. 第一题还原学生提交记录统计——map与set的组合拳2.1 题面还原先看题面。某在线评测系统记录了所有学生的提交行为请你统计每个学生的最终成绩。输入多行记录每行包含三个字段学号整数、题目编号形如P001的字符串、提交结果AC、WA、RE、TLE之一所有记录以EOF结束。输出按AC题目数降序若AC题目数相同则按总提交次数升序若仍相同则按学号升序输出每个学生的学号、AC题目数、总提交次数、AC率百分数保留两位小数。样例输入2023001 P001 AC 2023002 P001 WA 2023001 P002 AC 2023001 P001 WA 2023002 P001 AC 2023003 P003 WA样例输出2023001 2 3 66.67% 2023002 1 2 50.00% 2023003 0 1 0.00%注意同一个人同一道题即使AC过多次AC题目数也只计一次。2.2 破题思路去重计数是核心这道题从算法难度上说不算难题真正的考察点在于你能不能精炼地用STL完成去重和排序两件事。AC题目数要求同人同题去重学号和题号是一对多的关系最直接的结构就是maplong long, setstring。set天然去重不需要你手动判断这道题之前是否AC过。很多同学第一反应是用二维bool数组做去重比如bool ac[学号范围][题号范围]。但这个思路有两个硬伤一是题号是字符串不是连续整数二是学号和题号范围都不固定开数组很容易开小或开大。map/set这种动态结构才是正解。这里不必特意用unordered_map普通map的O(logN)查找在几千条记录的量级下毫无压力代码也更稳定。另一个容易踩的坑是遍历对象。如果你的循环只遍历存了AC记录的map就会漏掉那些交过WA但从未AC的学生。这道题要统计的对象是所有出现过提交记录的学生所以必须在外层遍历submitCnt这个记录总提交次数的map再用acSet.count(id)去判断该学生是否有AC记录。2.3 AC代码与逐段讲解#include bits/stdc.h using namespace std; struct Student { long long id; int solved; int total; }; int main() { ios::sync_with_stdio(false); cin.tie(0); long long id; string pid, result; maplong long, setstring acSet; // 学号 - 已AC的题目编号集合 maplong long, int submitCnt; // 学号 - 总提交次数 while (cin id pid result) { submitCnt[id]; if (result AC) { acSet[id].insert(pid); } } vectorStudent v; for (auto itr : submitCnt) { long long sid itr.first; int total itr.second; int solved acSet.count(sid) ? (int)acSet[sid].size() : 0; v.push_back({sid, solved, total}); } sort(v.begin(), v.end(), [](const Student a, const Student b) { if (a.solved ! b.solved) return a.solved b.solved; if (a.total ! b.total) return a.total b.total; return a.id b.id; }); cout fixed setprecision(2); for (auto stu : v) { double rate stu.total 0 ? 0.0 : (double)stu.solved / stu.total * 100.0; cout stu.id stu.solved stu.total rate %\n; } return 0; }代码的核心逻辑分三个部分。读入阶段用while循环处理EOF结尾的多行数据每次读到一条记录就累加submitCnt如果是AC再往acSet里插入题目编号。统计阶段遍历submitCnt对每个学生通过acSet取去重后的AC题数。排序阶段用lambda表达式实现自定义规则先比AC题数降序再比总提交次数升序最后比学号升序。2.4 这道题最容易丢分的三个细节细节一多组输入不能写死循环次数。我在练习时见过不少同学先读一个n再循环n次但机试这题没有给出总记录数必须以EOF结束也就是必须用while (cin id pid result)这种写法。细节二AC率的计算方式。AC率等于AC题目数除以总提交次数而不是AC提交次数除以总提交次数。以样例中的2023001为例总提交3次其中P001提交了两次一次AC一次WAP002提交一次AC所以AC题目数是2AC率是2/3而不是2/2。细节三输出格式。题目要求保留两位小数并带百分号用cout fixed setprecision(2)之后再输出数字比较稳妥。注意不要在这里混用printf和cout具体原因会在后面第五部分展开。3. 第二题还原数据中心传输延迟——堆优化Dijkstra的完整模板3.1 题面还原N个数据中心节点编号从1到NM条光纤链路。每条链路给出起点u、终点v和传输延迟w。现在要从1号节点向N号节点发送数据求最小传输延迟如果不可达则输出-1。输入第一行两个整数N、M接下来M行每行三个整数u、v、w。N最大可到10^5M最大可到2 * 10^5w为非负整数。输出一个整数表示从1到N的最小延迟不可达输出-1。样例输入4 5 1 2 1 1 3 4 2 3 2 2 4 6 3 4 2样例输出53.2 算法选型为什么是堆优化Dijkstra看到数据范围第一反应就是不能用O(N^3)的Floyd也不能用O(N*M)的Bellman-Ford。剩下的可选方案主要是SPFA和堆优化Dijkstra。SPFA在平均情况下很快但在复试OJ这种故意卡数据的场景里它的最坏复杂度是O(N*M)一旦出题人构造了稠密图或网状图超时是大概率事件。堆优化Dijkstra的复杂度是O((NM)logN)在N10^5、M2*10^5的规模下完全可控。Dijkstra能成立的本质是贪心每次从优先队列弹出的节点其当前距离一定是全局最小值这个节点一旦被确定就不会再有其他路径能把它更新得更小。这一点依赖于所有边权非负只要题目没有负权边Dijkstra就是最稳的选择。3.3 Dijkstra模板与AC代码用邻接表存图vectorEdge graph[MAXN]的方式在稀疏图下比邻接矩阵省内存得多。10^5个节点的邻接矩阵根本开不出来邻接表是唯一合理的选择。#include bits/stdc.h using namespace std; const int MAXN 100005; const long long INF 0x3f3f3f3f3f3f3f3fLL; struct Edge { int to, w; }; vectorEdge graph[MAXN]; long long dist[MAXN]; bool vis[MAXN]; int main() { ios::sync_with_stdio(false); cin.tie(0); int n, m; cin n m; for (int i 0; i m; i) { int u, v, w; cin u v w; graph[u].push_back({v, w}); } fill(dist, dist n 1, INF); dist[1] 0; priority_queuepairlong long, int, vectorpairlong long, int, greaterpairlong long, int pq; pq.push({0, 1}); while (!pq.empty()) { auto [d, u] pq.top(); pq.pop(); if (vis[u]) continue; vis[u] true; if (u n) break; for (auto e : graph[u]) { if (!vis[e.to] dist[e.to] d e.w) { dist[e.to] d e.w; pq.push({dist[e.to], e.to}); } } } if (dist[n] INF) cout -1 \n; else cout dist[n] \n; return 0; }判题逻辑是优先队列每次弹出距离最小的节点vis[u]确保每个节点只被真正处理一次。当弹出终点n时可以提前退出节约时间。这里用auto [d, u] pq.top()是C17的结构化绑定写法考前务必确认编译环境支持。3.4 考场上的边界情况重边、自环、大整数这个题考场上的翻车点不在算法本身而在各种边界数据的处理。第一源点等于终点。N1时dist[1]初始为0循环可能根本不会进入直接输出0。如果你把输出条件写成dist[n] INF判断不可达就不会出错。第二重边。同一对节点之间可能出现多条不同权值的边Dijkstra不需要特殊处理松弛操作只会保留最小的那个距离。前提是你不要在加边时自作聪明地只保留最小边那就可能把考场上的判题逻辑搞复杂了。第三自环。自环边的权值如果为正松弛不成立不影响结果如果为0松弛会让dist[e.to]等于自己本身也没有问题。第四INF的取值。如果用int INF 0x7fffffff一旦计算d e.w就可能溢出成负数导致距离被错误更新。稳妥做法是const long long INF 0x3f3f3f3f3f3f3f3fLL这个值在long long范围内足够大而且两个这样的数相加不会溢出。4. 第三题还原字符串编辑距离——从转移方程到滚动数组4.1 题面还原给定两个字符串s和t每次可以对s进行三种操作之一插入一个字符删除一个字符替换一个字符。求把s变成t的最少操作次数。输入多组测试用例每组一行包含两个字符串中间用空格分隔。字符串长度不超过2000。输出每组用例输出一个整数表示最小编辑距离。样例输入cat cut horse ros样例输出1 34.2 状态推导把编辑操作翻译成转移方程这类题的经典思路是定义二维DP状态dp[i][j]表示字符串s的前i个字符变成字符串t的前j个字符所需的最少操作次数。为什么要用两个维度因为两个字符串的前缀互相独立子问题的维度天然是两个字符串的长度。接下来把三种操作和转移方程一一对应。如果最后一步是插入操作说明s的前i个字符已经变成了t的前j-1个字符然后再在末尾插入一个字符补上t的第j个字符所以转移是dp[i][j-1] 1。如果最后一步是删除操作说明s的前i-1个字符变成t的前j个字符然后把s的第i个字符删掉转移是dp[i-1][j] 1。如果最后一步是替换操作那要看第i个字符和第j个字符是否相等——相等就不需要操作不相等就替换一次转移是dp[i-1][j-1] (s[i-1] t[j-1] ? 0 : 1)。初始化也很直观dp[0][j] j表示空串变成t的前j个字符需要逐字符插入j次dp[i][0] i表示s的前i个字符变成空串需要删除i次。填表顺序是从上到下、从左到右因为每个dp[i][j]只依赖左方、上方和左上方的值。以样例cat到cut为例填完整个表之后右下角的值就是答案。手动模拟一遍会加深理解dpcut0123c1012a2112t3221右下角的1就是最终答案因为只需要把中间的a替换成u。4.3 AC代码从二维数组到滚动数组首先写最直观的二维DP版本长度2000的字符串开2001 * 2001的int数组占内存约16MB完全能接受#include bits/stdc.h using namespace std; int minDistance(const string s, const string t) { int n s.size(), m t.size(); vectorvectorint dp(n 1, vectorint(m 1, 0)); for (int i 0; i n; i) dp[i][0] i; for (int j 0; j m; j) dp[0][j] j; for (int i 1; i n; i) { for (int j 1; j m; j) { int insertCost dp[i][j - 1] 1; int deleteCost dp[i - 1][j] 1; int replaceCost dp[i - 1][j - 1] (s[i - 1] t[j - 1] ? 0 : 1); dp[i][j] min({insertCost, deleteCost, replaceCost}); } } return dp[n][m]; } int main() { string s, t; while (cin s t) { cout minDistance(s, t) \n; } return 0; }如果题目把字符串长度提到10^5级别二维数组就不行了这时候用滚动数组把空间压到O(m)。滚动数组的精髓是我们只关心当前行和上一行所以只需要两个一维数组甚至一个一维数组加两个临时变量。int minDistance_roll(const string s, const string t) { int n s.size(), m t.size(); vectorint dp(m 1, 0); for (int j 0; j m; j) dp[j] j; for (int i 1; i n; i) { int prev dp[0]; // prev 相当于 dp[i-1][j-1]初始时是 dp[i-1][0] dp[0] i; // dp[i][0] i for (int j 1; j m; j) { int temp dp[j]; // 先保存 dp[i-1][j]因为马上要被覆盖 int insertCost dp[j - 1] 1; int deleteCost temp 1; int replaceCost prev (s[i - 1] t[j - 1] ? 0 : 1); prev temp; // 这个 temp 将成为下一轮 j1 的 prev即 dp[i-1][j] dp[j] min({insertCost, deleteCost, replaceCost}); } } return dp[m]; }这里最容易出错的是deleteCost到底该用哪个值。如果写成dp[j] 1那么dp[j]在当前行的更新循环里已经被新值覆盖了已经不是上一行的dp[i-1][j]。所以必须在覆盖前用temp保存旧值再在之后把temp传给prev确保下一轮的replaceCost拿到的是真正的dp[i-1][j-1]。4.4 为什么编辑距离是复试机试的高频常客编辑距离这个模型在机试里出现频率高原因有三。第一它考察的是动态规划最核心的思想——状态定义和转移方程的推导这一能力是复试筛选的关键。第二它的实现复杂度不高只要思路清晰十五分钟之内写完完整代码并不难适合作为中等难度的拉开差距题。第三它可以延伸出空间优化、路径回溯、不同操作代价等多种变体一道题就能考察出考生的基本功是否扎实。我自己的经验是很多同学在考场上不是不会DP而是对滚动数组不熟或者下标从0开始还是从1开始搞混。建议平时练习时就固定一套自己熟悉的状态定义和初始化写法考场上不要临时换思路。5. 从读题到AC机试现场的提分习惯与代码模板5.1 我固定的读题与自测流程机试时间有限但不能因为赶时间而跳过读题。我给自己定的流程是拿到题目先看数据范围N、M、字符串长度直接决定了该用什么复杂度的算法然后拿样例走一遍流程搞清楚输入字段之间的对应关系最后才动键盘写代码。写完之后不要急着提交先跑一遍样例再自己构造2到3组边界数据。举几个我常用的自测例子。Dijkstra题构造一个N1, M0的输入正确输出应该是0。编辑距离题构造两个空字符串正确输出是0。模拟统计题构造一个全部提交都是WA的学生确认它能正常输出而不是被漏掉。这些边界数据跑通之后提交的通过率会大幅提升。5.2 两个能救命的小模板快速IO与INF取值机试里IO处理是第一个坑。C的标准做法是保留cin但必须关闭同步ios::sync_with_stdio(false); cin.tie(0);这两行写在main函数开头能让cin的读入速度接近scanf。但注意关闭同步之后就不能再混用printf和scanf了否则输出顺序可能错乱。我在模拟训练时见过太多人写着写着就混用了这个习惯要刻意改掉。第二个模板是INF取值。0x3f3f3f3f是int长度的经典选择两个0x3f3f3f3f相加约等于8.1亿不会超过int上限21亿做松弛时不会溢出。long long版本则是0x3f3f3f3f3f3f3f3fLL。把这个值背下来比用INT_MAX或LLONG_MAX安全得多。5.3 考场时间分配和心态管理拿到题目后切忌直接扑向第一题闷头写。先把3到4道题全部读一遍在心里快速给每道题打难度标签。我的分配策略是先做最有把握的题拿到稳稳的分数遇到卡壳超过20分钟的题果断跳过先把其他题做完最后还剩时间再回头啃硬题。机试的判分是按通过情况给分把会的题写对远比死磕一道不会的题划算。心态上要接受一个事实不可能每道题都能AC。我考完最大的感触是很多失分不是不会做而是细节处理不到位——比如多组输入的终止条件没处理好比如排序规则写反比如数组开小了1个下标。如果你现在开始准备把文中三道题按独立写一遍、对照代码补细节、隔天重写一遍的节奏练到考场上这些坑就踩不到你了。