企业官网建设流程全解析

去年备考哈工大计算机考研的时候，最让我心里没底的就是复试机试。网上能找到的所谓真题，大多来自论坛里学长的口述回忆，不少题目连输入输出格式都缺失，更别提配套的AC代码了。我把能翻到的经验帖、回忆帖全部过了一遍，再结合哈工大机试一贯的出题偏好，整理出三道高频考点还原题，配套完整的解题思路和可直接运行的C++代码，就是这篇文章的主体。如果你正在准备2025年复试，把这三道题练熟，再掌握最后一节的考场习惯，机试这关基本稳了。

先说明一个现实：机试的题目采集方式决定了很少有人能把原题完整复述出来，所以任何网上流传的"真题"都带有回忆和还原的成分。以下三道题是对近几年考生回忆中高频题型的整理，个别细节可能与考场原题有差异，但解题思路、代码模板、边界坑点都是实打实通用的。

1. 哈工大复试机试的整体盘面：题型、环境与备考重心

1.1 机试的运行规则：时长、题量、判题方式

从我了解到的近几届情况看，哈工大复试机试通常安排在3月中下旬的复试周内，时长为3小时左右，题量在3到4道之间。编程语言基本限定在C/C++，在线判题系统会自动评测并实时返回结果。和平时刷OJ最大的区别是，部分年份采用动态抽题，每个人拿到的题目可能不同，但整体难度分布会保持一致。

这里有一个很关键的建议：报名后一定去学院官网把当年的机试说明读一遍，重点确认编译器的具体版本、是否支持C++11/17语法、判题要求的输入输出格式。我见过有人因为默认使用cin/cout的同步关闭方式，和QuickIO混用后导致输出顺序异常，白白丢掉大分，这种问题完全是可以在考前规避的。

1.2 高频考点分布：一张表看懂出题偏好

结合近几年考生回忆，我整理了一张主观估算的考点分布表，注意这不是官方统计，只是帮助大家分配复习精力的参考：

从这张表能看出两个信息。第一，简单模拟题占比最高，属于必拿分项；第二，动态规划和图论几乎年年出现，是拉开差距的关键。字符串处理和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题目数要求同人同题去重，学号和题号是一对多的关系，最直接的结构就是map<long long, set<string>>。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; map<long long, set<string>> acSet; // 学号 -> 已AC的题目编号集合 map<long long, int> submitCnt; // 学号 -> 总提交次数 while (cin >> id >> pid >> result) { submitCnt[id]++; if (result == "AC") { acSet[id].insert(pid); } } vector<Student> 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一次WA），P002提交一次AC，所以AC题目数是2，AC率是2/3而不是2/2。

细节三：输出格式。题目要求保留两位小数并带百分号，用cout << fixed << setprecision(2)之后再输出数字比较稳妥。注意不要在这里混用printf和cout，具体原因会在后面第五部分展开。

3. 第二题还原：数据中心传输延迟——堆优化Dijkstra的完整模板

3.1 题面还原

N个数据中心节点，编号从1到N，M条光纤链路。每条链路给出起点u、终点v和传输延迟w。现在要从1号节点向N号节点发送数据，求最小传输延迟，如果不可达则输出-1。

输入：第一行两个整数N、M，接下来M行每行三个整数u、v、w。N最大可到10^5，M最大可到2 * 10^5，w为非负整数。输出：一个整数，表示从1到N的最小延迟，不可达输出-1。

样例输入：

4 5 1 2 1 1 3 4 2 3 2 2 4 6 3 4 2

样例输出：

5

3.2 算法选型：为什么是堆优化Dijkstra

看到数据范围，第一反应就是不能用O(N^3)的Floyd，也不能用O(N*M)的Bellman-Ford。剩下的可选方案主要是SPFA和堆优化Dijkstra。SPFA在平均情况下很快，但在复试OJ这种"故意卡数据"的场景里，它的最坏复杂度是O(N*M)，一旦出题人构造了稠密图或网状图，超时是大概率事件。堆优化Dijkstra的复杂度是O((N+M)logN)，在N=10^5、M=2*10^5的规模下完全可控。

Dijkstra能成立的本质是贪心：每次从优先队列弹出的节点，其当前距离一定是全局最小值，这个节点一旦被确定，就不会再有其他路径能把它更新得更小。这一点依赖于所有边权非负，只要题目没有负权边，Dijkstra就是最稳的选择。

3.3 Dijkstra模板与AC代码

用邻接表存图，vector<Edge> 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; }; vector<Edge> 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_queue<pair<long long, int>, vector<pair<long long, int>>, greater<pair<long 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()是C++17的结构化绑定写法，考前务必确认编译环境支持。

3.4 考场上的边界情况：重边、自环、大整数

这个题考场上的翻车点不在算法本身，而在各种边界数据的处理。

第一，源点等于终点。N=1时，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 3

4.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为例，填完整个表之后右下角的值就是答案。手动模拟一遍会加深理解：

右下角的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(); vector<vector<int>> dp(n + 1, vector<int>(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(); vector<int> 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 将成为下一轮 j+1 的 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题构造一个N=1, M=0的输入，正确输出应该是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个下标。如果你现在开始准备，把文中三道题按"独立写一遍、对照代码补细节、隔天重写一遍"的节奏练，到考场上这些坑就踩不到你了。