先聊个真实感受每年复试结束网上能搜到的机试经验要么是零散的“考了什么题”要么是只有代码没有思路的“答案帖”真正能把题目还原、把思路讲透、把代码写到能直接跑的太少。这篇就是冲着“真题还原 解题思路 AC 代码”三件套来的内容基于 2025 年中国海洋大学计算机考研复试机试结束后多位考生的复盘记忆整理题面不是官方原卷但题型分布、考点风格、难度梯度和今年实际考试相当贴近。不管你是 26 考研正在择校观望还是已经拿到复试通知在突击机试又或者是单纯想看看海大机试到底考到什么程度这篇都可以当一份“考前对照清单”用。我会把每道题的思考过程、边界条件、复杂度分析全部展开代码统一用 C17附详细注释。1. 2025 年机试考了什么题型分布与考察风格1.1 今年机试的基本情况海大计算机学硕和专硕的复式机试通常安排在笔试和面试之间用的是机房本地部署的 OJ 判题系统现场提交现场判分。题目数量一般在四道左右考试时长两到两个半小时满分通常按 100 分或按题面分值折算。今年考生反馈比较一致的点是整体难度比 2024 年略有提升但依然没有偏离“基础算法 经典模型 一点思维”的主线第一题偏简单最后一题开始上强度中间两题是区分度所在。环境方面官方一般提前说明支持 C/C部分年份开放 Java 和 Python从实际考情看绝大多数人还是用 C/C 提交毕竟手速和稳定性最重要。我自己的建议是不要抱着“我用 Python 更熟”的心态去复试机试除非你熟悉判题系统的 Python 版本、输入输出性能限制否则现场用 C 写经典算法是最稳的。1.2 今年机试的知识点分布从复盘来看今年题目集中在这几个方向进制转换与字符串模拟、区间贪心、二维动态规划、图论最短路。这四个方向几乎是海大复试机试的“钉子户”往年也反复出现。它们有一个共同特点都有非常固定的套路但每年都会在题目描述上换一层壳我见过不少基础不错的同学因为没读懂题面里“补零”“施工封闭”“输出路径”这些附加条件白白丢了分。所以这篇文章我不会只给结论而是把每道题从读题到 AC 的完整链路走一遍包括那些题目里没说但你必须自己处理的细节。比如进制转换的负数、0 的特殊情况区间贪心的排序依据为什么是右端点而不是左端点DP 输出路径的倒推逻辑Dijkstra 遇到重边和封闭边的处理方式。这些点单个拿出来都不难但组合在一起就是考场上能不能一次 AC 的分水岭。2. 真题一进制转换与字符串模拟2.1 题目还原与样例说明题面大意是给定一个十进制整数 nn 的绝对值不超过 2^31也就是 int 范围和一个进制 b2 ≤ b ≤ 16要求输出 n 的 b 进制表示。如果转换结果只有一位数字则在高位补一个 0使输出长度至少为 2。负数需要先输出负号再输出绝对值转换后的结果。保证最终输出长度不超过 8。输入格式是两行第一行为 n第二行为 b。输出一行字符串。我举个例子说明补零的逻辑如果 n 是 5b 是 2转换结果是 101长度三位不需要补零直接输出 101。如果 n 是 3b 是 2转换结果是 11长度两位也不用补。真正需要补零的是 n 为 1、b 为 2 时转换结果是 1此时需要输出 01。n 为 0 时转换结果是 0长度为一位需要输出 00。这个细节看着小但很容易被忽略。2.2 解题思路别小看这道“签到题”这道题的核心是“除 b 取余法”属于进制转换最基础的实现。我见过很多同学能写出 10 进制转 2 进制的代码但一旦进制超过 10就忘了把余数 10 到 15 转成 A 到 F一旦遇到负数就忘了先输出负号一旦遇到 0就忘了特判。这些“忘了”不是能力问题而是平时刷题时没有把边界情况当成题目的一部分。考场上要想一次 AC代码里必须显式处理三件事n 为 0 的情况、n 为负数的情况、余数大于等于 10 时转字母的情况。另外虽然题目保证 n 在 int 范围内但我在代码里把 n 读成 long long这是从“输入数据范围可能被临时调整”的角度做的防御竞赛老手都懂这个习惯能避免 INT_MIN 取绝对值时溢出的经典坑。2.3 AC 代码与逐段注释#include bits/stdc.h using namespace std; string convert(long long n, int b) { if (n 0) return 00; bool neg false; if (n 0) { neg true; n -n; } string res; while (n 0) { int digit n % b; if (digit 10) { res.push_back(char(0 digit)); } else { res.push_back(char(A digit - 10)); } n / b; } if (res.size() 1) { res.push_back(0); } reverse(res.begin(), res.end()); if (neg) { return - res; } return res; } int main() { long long n; int b; cin n b; cout convert(n, b) endl; return 0; }注意补零的时机我先把一位的情况补一个 0 在末尾最后统一反转。这样 1 转二进制时先得到字符串 1补 0 后为 10反转后是 01正好符合题意。如果你先反转再补零就变成在左边补 0正确性没问题但我觉得先补后反转更符合“从低位生成”的自然逻辑不容易出错。2.4 这类题现场要注意的两个细节第一个是负数与零的组合。n 为 0 时我的代码直接返回 00不会进入负数分支这是对的。如果你把负数分支放在所有处理之前也要小心 n 0 时不要输出 -00。第二个是输出长度不超过 8 的保证。这个条件给得很宽松最大的 int 负值转成 2 进制也不到 32 位为什么限制 8我猜测是为了让某些同学的“先转成字符串再补长”的解法也能过但同时也是提醒不要因为觉得简单就忽略格式。复试机试的判题往往严格比对字符串多一个空格、少一个前导零都是 WA。3. 真题二区间贪心——最少删除区间数3.1 题目还原与样例说明题面给定 n 个闭区间 [start_i, end_i]1 ≤ n ≤ 10^50 ≤ start_i end_i ≤ 10^9代表 n 门课程的上课时间段。你需要在时间上互不冲突的前提下删掉尽量少的课程使得剩下的课程之间没有重叠。输出最少删除数量。注意端点重合也算冲突也就是一个课程的结束时间等于另一个课程的开始时间时它们不能同时保留。输入第一行是 n接下来 n 行每行两个整数 start 和 end。输出一个整数。这个题是前两年的“活动安排”加了反转问法活动安排是选最多不重叠区间这里是问最少删几个。本质上是一回事因为“最少删除数 总区间数 - 最多可选不重叠区间数”。3.2 解题思路为什么按右端点排序是对的选择区间贪心有两类经典排序按左端点排序或者按右端点排序。这个题正确的做法是按右端点升序排序然后从左到右扫描能选就选不能选就跳过。不能选的标准是当前区间的 start 小于上一个被选中区间的 end即发生重叠。为什么非按右端点不可我用一个简单的例子说明。三个区间 [1, 4]、[2, 3]、[3, 5]如果按左端点排序会得到 [1, 4]、[2, 3]、[3, 5]贪心选完 [1, 4] 后后面两个都不能选最多选 1 个。但如果按右端点排序顺序是 [2, 3]右端点 3、[1, 4]右端点 4、[3, 5]右端点 5贪心选 [2, 3] 后[1, 4] 与它重叠跳过[3, 5] 与它右端点 3 重合也算重叠所以只能选 1 个。这里两种排序得到相同结果但换一组区间就不同了。区间 [1, 5]、[2, 3]、[4, 6]按左端点排序选 [1, 5]后面两个都不能选只能选 1 个按右端点排序选 [2, 3]再选 [4, 6]能选 2 个。差距立刻显现。背后的直觉是每次选择当前结束最早的区间能最大程度避免占用后续区间的可用时间这样后续能选择的区间数量就有保障。如果选择结束晚的区间哪怕它开始得很早也会挡住中间一大片时间。3.3 AC 代码与复杂度分析#include bits/stdc.h using namespace std; int main() { int n; cin n; vectorpairint, int seg(n); for (int i 0; i n; i) { cin seg[i].first seg[i].second; } sort(seg.begin(), seg.end(), [](const pairint, int a, const pairint, int b) { return a.second b.second; }); int lastEnd -1; int keep 0; for (auto p : seg) { if (p.first lastEnd) { keep; lastEnd p.second; } } cout n - keep endl; return 0; }lastEnd 初始化成 -1 是为了应对左端点从 0 开始的情况保证第一个区间一定能被选中。如果题目改成 start_i 可以为负那应该用 INT_MIN 或更小的值但本题给了 0 ≤ start_i-1 就够用。复杂度很舒服排序 O(n log n)扫描 O(n)总耗时不到 0.1 秒。要注意的是 n 最大 1e5输入量中等用 cin 加 ios::sync_with_stdio(false) 足够如果你对性能有执念可以写快读但没必要。3.4 现场容易被卡的隐蔽点这个题最常见的错误是把闭合区间当成开区间处理。题面明确说端点和端点重合也算冲突也就是说判断重叠的条件是 p.first lastEnd 才可保留而不是 p.first lastEnd。我见过有同学在练习平台上做过标准“活动安排”题那边允许端点相接于是直接把条件写成大于号结果在这个题上 WA 到怀疑人生。另一个容易忽视的是题目问的是“最少删除几个”而不是“最多保留几个”。虽然两者只差一个减法但真的有人输出 keep 而不是 n - keep只能说太紧张了。这类改问法的题目在复试机试里越来越常见读题时建议把“删”“留”“最少”“最多”这几个词圈出来。4. 真题三二维动态规划——收集贝壳最大数量并输出路径4.1 题目还原与样例说明题面海大校园里有一片 n × m 的沙滩网格1 ≤ n, m ≤ 100每个格子里有一定数量的贝壳第 i 行第 j 列的贝壳数为 a[i][j]0 ≤ a[i][j] ≤ 1000。你从左上角 (1,1) 出发走到右下角 (n,m)每次只能向右或向下移动一格。沿途收集经过格子里的贝壳起点和终点的贝壳也算收集。求能收集到的最大贝壳数量并按路径输出经过的格子坐标。输入第一行两个整数 n m接下来 n 行每行 m 个整数。输出第一行为最大贝壳数第二行按顺序输出路径上的坐标坐标用 (行,列) 表示中间用 - 连接。这个题的本质是数字三角形 / 网格路径最大和的变体但因为加了路径输出很多只会求最值的同学会卡住。我把它还原成贝壳主题是因为当年海大实际上也喜欢把算法题包装成“校园生活”背景这种做法现在很常见。4.2 思路拆解状态转移和路径记录的先后顺序最大值的状态转移很简单设 dp[i][j] 表示从起点走到 (i, j) 能收集到的最大贝壳数那么由于只能向右和向下走到达 (i, j) 的前一步要么是 (i-1, j)从上方来要么是 (i, j-1)从左方来所以dp[i][j] max(dp[i-1][j], dp[i][j-1]) a[i][j]边界情况是第一行只能从左往右走第一列只能从上往下走所以先把 dp[1][1] 到 dp[1][m] 和 dp[1][1] 到 dp[n][1] 初始化好再按行从上到下、从左到右递推。路径输出有两种思路。第一种是正推记录“从哪来”开一个二维数组 pre[i][j]值为 0 表示从上方来值为 1 表示从左方来。填 dp 的时候同步记录最后从 (n, m) 反推回 (1, 1)把坐标放进 vector 再反转输出。第二种是输出时递归回溯从终点往起点倒着找每次都看 dp[i][j] 减去 a[i][j] 后是等于 dp[i-1][j] 还是等于 dp[i][j-1]从而决定走向哪个格子。第二种不需要额外存储但递归深度最坏到 nm200 以内没问题不过现场我建议用第一种逻辑更直接。注意一个隐藏的陷阱当 dp[i-1][j] 和 dp[i][j-1] 相等时选哪条路径都不影响最大值但会影响路径的具体输出序列。判题系统对这类输出通常是特判或者允许任意合法路径但如果你按自己的顺序实现必须保证路径确实是按照你的 pre 数组回溯得到的不能在输出时临时换方向。4.3 AC 代码带上路径输出的完整实现#include bits/stdc.h using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, m; cin n m; vectorvectorint a(n 1, vectorint(m 1, 0)); for (int i 1; i n; i) { for (int j 1; j m; j) { cin a[i][j]; } } vectorvectorlong long dp(n 1, vectorlong long(m 1, 0)); vectorvectorint pre(n 1, vectorint(m 1, 0)); dp[1][1] a[1][1]; for (int j 2; j m; j) { dp[1][j] dp[1][j-1] a[1][j]; pre[1][j] 1; // 从左边来 } for (int i 2; i n; i) { dp[i][1] dp[i-1][1] a[i][1]; pre[i][1] 0; // 从上方来 } for (int i 2; i n; i) { for (int j 2; j m; j) { if (dp[i-1][j] dp[i][j-1]) { dp[i][j] dp[i-1][j] a[i][j]; pre[i][j] 0; } else { dp[i][j] dp[i][j-1] a[i][j]; pre[i][j] 1; } } } cout dp[n][m] \n; vectorpairint, int path; int x n, y m; while (x ! 1 || y ! 1) { path.push_back({x, y}); if (pre[x][y] 0) x--; else y--; } path.push_back({1, 1}); reverse(path.begin(), path.end()); for (int i 0; i (int)path.size(); i) { if (i) cout - ; cout ( path[i].first , path[i].second ); } cout \n; return 0; }dp 用 long long 是因为 100 × 100 个格子每个最多 1000最大和能到 1e7int 其实也放得下但我用 long long 是为了让你形成“看到求和就自动考虑上限”的肌肉记忆这个习惯在高考研复试里救过我很多次。4.4 输出路径的调试心得路径回溯最怕的是一边回溯一边发现走到了死路。我调试这个题的时候会故意用全 0 矩阵和全相同数字矩阵来测全 0 时无论路径怎么走最大和都是 0路径输出必须仍然是一条从左上到右下的完整路线全相同数字时dp 值每步都能算对但路径可能因为 if 分支的选择出现非预期走向没关系只要满足只向右向下且终点正确即可。另一个是坐标输出的空格问题题目要求用 “(行,列)” 的格式注意括号内逗号后面不要加空格路径之间用 “ - ”箭头前后各一个空格。判题机对格式字符很敏感我见过因为多打一个空格丢掉整题的情况。这种冤罪可不想再经历第二次。5. 真题四图论最短路——校园道路施工封闭5.1 题目还原与样例说明题面学校有 n 栋建筑1 ≤ n ≤ 1000m 条双向道路1 ≤ m ≤ 50000第 i 条道路连接 u_i 和 v_i通行时间为 w_i1 ≤ w_i ≤ 10000。你要从宿舍楼 s 出发去实验室 t。现在有 k 次施工查询1 ≤ k ≤ 1000每次查询给出一个道路编号 id表示该道路在本次查询中临时封闭只影响本次查询你需要输出封闭这条道路后从 s 到 t 的最短通行时间如果无法到达输出 -1。注意道路编号从 1 开始查询之间的封闭状态互不影响。输入先读 n m再读 m 行道路信息并记录编号然后读起点 s 终点 t再读 k最后 k 行每行一个 id。这个题是 2025 年机试中区分度最高的一道。因为它不是单纯的最短路模板题而是“最短路 多条查询”。如果每来一个封闭查询都跑一遍完整 Dijkstrak 最多 1000Dijkstra 用堆优化复杂度 O((n m) log n)总复杂度约 1000 × 50000也就是 5e7 级别在 C 下勉强可过但如果 m 再大一倍或者现场机器性能差一些就非常悬。5.2 思路拆解直接重跑还是先做预处理这个题最稳妥的现场做法是每次查询把对应边的权值临时改成 INF一个很大的数跑一遍 Dijkstra然后恢复。为什么不在查询前把原最短路径找出来然后只处理影响原路径的边因为一旦封闭的边不在原最短路上答案就是原最短路长度可以直接输出这是一个很大的优化。但实现时要小心如果原最短路有多条某条边不在你求出的那一条上但它可能在另一条同样长度的最短路上封闭它并不会改变答案而你的程序可能误判为“需要重新计算”。处理这个问题需要对每条边记录“是否被原最短路树使用”最短路树的选择会影响正确性现场很容易想漏。我建议基础一般的同学直接用“每次查询重跑 Dijkstra”的写法配合堆优化。n 只有 1000m 最多 5e4即使 k1000 也稳过因为每次 Dijkstra 实际访问的边数远小于 m。基础扎实、想冲满分的同学可以用“原路径不受影响直接输出原答案”的优化但必须以“封闭边是否在所有最短路上”为判断依据不能以“是否在其中一条最短路上”为依据。5.3 AC 代码重跑 Dijkstra 的稳健写法#include bits/stdc.h using namespace std; const long long INF 1e18; struct Edge { int u, v, w; }; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, m; cin n m; vectorEdge edges(m 1); vectorvectorpairint, int graph(n 1); for (int i 1; i m; i) { cin edges[i].u edges[i].v edges[i].w; graph[edges[i].u].push_back({edges[i].v, i}); graph[edges[i].v].push_back({edges[i].u, i}); } int s, t; cin s t; int k; cin k; auto dijkstra [](int blockId) - long long { vectorlong long dist(n 1, INF); priority_queuepairlong long, int, vectorpairlong long, int, greaterpairlong long, int pq; dist[s] 0; pq.push({0, s}); while (!pq.empty()) { auto [d, u] pq.top(); pq.pop(); if (d ! dist[u]) continue; if (u t) break; for (auto [v, edgeId] : graph[u]) { if (edgeId blockId) continue; long long w edges[edgeId].w; if (dist[v] dist[u] w) { dist[v] dist[u] w; pq.push({dist[v], v}); } } } return dist[t]; }; while (k--) { int id; cin id; long long ans dijkstra(id); if (ans INF / 2) { cout -1 \n; } else { cout ans \n; } } return 0; }这里图里存的是边编号而不是直接存权值是为了快速跳过被封闭的那条边。你在考场上一旦养成这种“边编号”的存储习惯处理边删除、边更新这类问题会非常顺手。5.4 为什么这道题容易翻车重边、INF、提前退出三个地方最容易出错。第一是重边题目没说没有重边那就要假设有。存边编号后即使两个结点间有多条边每条边都有独立编号封掉其中一个编号另一条还能正常走这是存编号的天然优势如果你直接把邻接矩阵存成最短权值封路后就会把好的边一起封掉。第二是 INF 的判断。我设置 INF 1e18判断不可达时用 ans INF / 2 而不是 ans INF这是因为 Dijkstra 过程中可能出现 INF 加上一个负数虽然本题不会严谨一点总没错。第三是提前退出的位置。我在 u t 时 break这时 dist[t] 已经是确定的不会影响正确性。但要注意如果你需要在路径输出时用到前驱数组就不能在第一次弹出 t 时直接 break因为多条等长路径的情况下前驱也许还没被最优方案更新完。这个题只问距离break 没问题。6. 实战复盘从准备到考场的经验清单6.1 编译环境和 OJ 使用提前确认四件事海大机试的判题系统每年环境细节可能微调我建议复试前一周就查清楚四点支持的编译器版本是否支持 C17比如结构体绑定 auto [d, u] 这类语法在旧版 GCC 下可能编不过系统是否自动开启 O2 优化main 函数返回值要求提交时是否要选择语言而不是靠文件后缀识别。这些都是很小的点但考场上编译器直接 RE 的感觉我不想你再体验一次。如果对本地环境不熟考前至少用学校的 OJ 或公开 OJ 练十道题熟悉标准输入输出、多组数据处理和错误反馈风格。尤其是多组数据很多机试题目是单组但一旦遇到多组而你没写 while 循环直接只过第一个样例。6.2 数据范围读题法从 int 到 long long我给自己定的规矩是任何题先看数据范围再动笔。a[i][j] 最大 1000、n m 最大 100dp 用 long long 不是必须但稳妥区间长度到 1e9排序用 long long 存也常见Dijkstra 的距离松弛可能超过 int必须用 long long。复试机试不可能在数据范围上故意坑你但它也不会保证“所有中间结果都不超过 int”所以把能开的都开成 long long 是最便宜的保险。另一个和读题相关的注意点是“单测还是多测”。今年海大机试四道题都是单组测试比较简单但往年有过最后一道题多组输入的情况题面会写“输入包含多组数据以 EOF 结束”这时候你必须把核心逻辑包在 while (cin ...) 里。不仔细看题是考场上最大的杀手。6.3 时间分配60 分钟的节奏建议两小时四道题我的节奏是前 15 分钟搞定第一题并完成一次本地样例和边界样例测试第二题和第三题各花 20 到 25 分钟包括写代码和调试最后一道题留 20 到 30 分钟如果做不完就把 Dijkstra 模板写上至少能过部分测试点。不要在一道题上死磕超过 40 分钟。机试判分通常按通过的数据点给分哪怕你的代码复杂度不对只要小数据能过也能拿一部分分。我见过太多人在最后一题上耗尽时间前面的题反而没有检查边界最后分数不理想。先保住确定能拿的分再考虑冲击难题这是复试现场最务实的策略。6.4 心态与习惯动手前先写 5 行注释最后分享一个我自己的小习惯读题后不管多简单先在代码最上方用注释写下“题目在求什么、输入范围、我用什么算法、复杂度是多少”。这四行注释不会直接帮你 AC但能强迫你在写代码前把思路固定下来避免写着写着发现方向错了推倒重来。今年有个同学跟我说他做完第三题输出路径时卡了很久就是因为没先想清楚 pre 数组回溯的方向我说这题如果你在代码前写两行“pre[x][y]0 上边来1 左边来”至少能少 10 分钟调试时间。机试考的不只是你会不会算法更是你在压力下能不能有条理地把会的东西写对。四道题复盘下来我对今年海大机试的总体评价是典型、不偏、但需要真实功夫。如果你能把这篇里的每一道题独立在纸上推导一遍再不看代码自己手敲一遍 AC你的复试机试准备就比大多数人扎实了。后面有时间我再结合其他院校的复试题做一个横向对比看看海大出题风格在同类 985 中处于什么水准。
2025中国海洋大学计算机考研复试机试真题复盘与AC代码解析
先聊个真实感受每年复试结束网上能搜到的机试经验要么是零散的“考了什么题”要么是只有代码没有思路的“答案帖”真正能把题目还原、把思路讲透、把代码写到能直接跑的太少。这篇就是冲着“真题还原 解题思路 AC 代码”三件套来的内容基于 2025 年中国海洋大学计算机考研复试机试结束后多位考生的复盘记忆整理题面不是官方原卷但题型分布、考点风格、难度梯度和今年实际考试相当贴近。不管你是 26 考研正在择校观望还是已经拿到复试通知在突击机试又或者是单纯想看看海大机试到底考到什么程度这篇都可以当一份“考前对照清单”用。我会把每道题的思考过程、边界条件、复杂度分析全部展开代码统一用 C17附详细注释。1. 2025 年机试考了什么题型分布与考察风格1.1 今年机试的基本情况海大计算机学硕和专硕的复式机试通常安排在笔试和面试之间用的是机房本地部署的 OJ 判题系统现场提交现场判分。题目数量一般在四道左右考试时长两到两个半小时满分通常按 100 分或按题面分值折算。今年考生反馈比较一致的点是整体难度比 2024 年略有提升但依然没有偏离“基础算法 经典模型 一点思维”的主线第一题偏简单最后一题开始上强度中间两题是区分度所在。环境方面官方一般提前说明支持 C/C部分年份开放 Java 和 Python从实际考情看绝大多数人还是用 C/C 提交毕竟手速和稳定性最重要。我自己的建议是不要抱着“我用 Python 更熟”的心态去复试机试除非你熟悉判题系统的 Python 版本、输入输出性能限制否则现场用 C 写经典算法是最稳的。1.2 今年机试的知识点分布从复盘来看今年题目集中在这几个方向进制转换与字符串模拟、区间贪心、二维动态规划、图论最短路。这四个方向几乎是海大复试机试的“钉子户”往年也反复出现。它们有一个共同特点都有非常固定的套路但每年都会在题目描述上换一层壳我见过不少基础不错的同学因为没读懂题面里“补零”“施工封闭”“输出路径”这些附加条件白白丢了分。所以这篇文章我不会只给结论而是把每道题从读题到 AC 的完整链路走一遍包括那些题目里没说但你必须自己处理的细节。比如进制转换的负数、0 的特殊情况区间贪心的排序依据为什么是右端点而不是左端点DP 输出路径的倒推逻辑Dijkstra 遇到重边和封闭边的处理方式。这些点单个拿出来都不难但组合在一起就是考场上能不能一次 AC 的分水岭。2. 真题一进制转换与字符串模拟2.1 题目还原与样例说明题面大意是给定一个十进制整数 nn 的绝对值不超过 2^31也就是 int 范围和一个进制 b2 ≤ b ≤ 16要求输出 n 的 b 进制表示。如果转换结果只有一位数字则在高位补一个 0使输出长度至少为 2。负数需要先输出负号再输出绝对值转换后的结果。保证最终输出长度不超过 8。输入格式是两行第一行为 n第二行为 b。输出一行字符串。我举个例子说明补零的逻辑如果 n 是 5b 是 2转换结果是 101长度三位不需要补零直接输出 101。如果 n 是 3b 是 2转换结果是 11长度两位也不用补。真正需要补零的是 n 为 1、b 为 2 时转换结果是 1此时需要输出 01。n 为 0 时转换结果是 0长度为一位需要输出 00。这个细节看着小但很容易被忽略。2.2 解题思路别小看这道“签到题”这道题的核心是“除 b 取余法”属于进制转换最基础的实现。我见过很多同学能写出 10 进制转 2 进制的代码但一旦进制超过 10就忘了把余数 10 到 15 转成 A 到 F一旦遇到负数就忘了先输出负号一旦遇到 0就忘了特判。这些“忘了”不是能力问题而是平时刷题时没有把边界情况当成题目的一部分。考场上要想一次 AC代码里必须显式处理三件事n 为 0 的情况、n 为负数的情况、余数大于等于 10 时转字母的情况。另外虽然题目保证 n 在 int 范围内但我在代码里把 n 读成 long long这是从“输入数据范围可能被临时调整”的角度做的防御竞赛老手都懂这个习惯能避免 INT_MIN 取绝对值时溢出的经典坑。2.3 AC 代码与逐段注释#include bits/stdc.h using namespace std; string convert(long long n, int b) { if (n 0) return 00; bool neg false; if (n 0) { neg true; n -n; } string res; while (n 0) { int digit n % b; if (digit 10) { res.push_back(char(0 digit)); } else { res.push_back(char(A digit - 10)); } n / b; } if (res.size() 1) { res.push_back(0); } reverse(res.begin(), res.end()); if (neg) { return - res; } return res; } int main() { long long n; int b; cin n b; cout convert(n, b) endl; return 0; }注意补零的时机我先把一位的情况补一个 0 在末尾最后统一反转。这样 1 转二进制时先得到字符串 1补 0 后为 10反转后是 01正好符合题意。如果你先反转再补零就变成在左边补 0正确性没问题但我觉得先补后反转更符合“从低位生成”的自然逻辑不容易出错。2.4 这类题现场要注意的两个细节第一个是负数与零的组合。n 为 0 时我的代码直接返回 00不会进入负数分支这是对的。如果你把负数分支放在所有处理之前也要小心 n 0 时不要输出 -00。第二个是输出长度不超过 8 的保证。这个条件给得很宽松最大的 int 负值转成 2 进制也不到 32 位为什么限制 8我猜测是为了让某些同学的“先转成字符串再补长”的解法也能过但同时也是提醒不要因为觉得简单就忽略格式。复试机试的判题往往严格比对字符串多一个空格、少一个前导零都是 WA。3. 真题二区间贪心——最少删除区间数3.1 题目还原与样例说明题面给定 n 个闭区间 [start_i, end_i]1 ≤ n ≤ 10^50 ≤ start_i end_i ≤ 10^9代表 n 门课程的上课时间段。你需要在时间上互不冲突的前提下删掉尽量少的课程使得剩下的课程之间没有重叠。输出最少删除数量。注意端点重合也算冲突也就是一个课程的结束时间等于另一个课程的开始时间时它们不能同时保留。输入第一行是 n接下来 n 行每行两个整数 start 和 end。输出一个整数。这个题是前两年的“活动安排”加了反转问法活动安排是选最多不重叠区间这里是问最少删几个。本质上是一回事因为“最少删除数 总区间数 - 最多可选不重叠区间数”。3.2 解题思路为什么按右端点排序是对的选择区间贪心有两类经典排序按左端点排序或者按右端点排序。这个题正确的做法是按右端点升序排序然后从左到右扫描能选就选不能选就跳过。不能选的标准是当前区间的 start 小于上一个被选中区间的 end即发生重叠。为什么非按右端点不可我用一个简单的例子说明。三个区间 [1, 4]、[2, 3]、[3, 5]如果按左端点排序会得到 [1, 4]、[2, 3]、[3, 5]贪心选完 [1, 4] 后后面两个都不能选最多选 1 个。但如果按右端点排序顺序是 [2, 3]右端点 3、[1, 4]右端点 4、[3, 5]右端点 5贪心选 [2, 3] 后[1, 4] 与它重叠跳过[3, 5] 与它右端点 3 重合也算重叠所以只能选 1 个。这里两种排序得到相同结果但换一组区间就不同了。区间 [1, 5]、[2, 3]、[4, 6]按左端点排序选 [1, 5]后面两个都不能选只能选 1 个按右端点排序选 [2, 3]再选 [4, 6]能选 2 个。差距立刻显现。背后的直觉是每次选择当前结束最早的区间能最大程度避免占用后续区间的可用时间这样后续能选择的区间数量就有保障。如果选择结束晚的区间哪怕它开始得很早也会挡住中间一大片时间。3.3 AC 代码与复杂度分析#include bits/stdc.h using namespace std; int main() { int n; cin n; vectorpairint, int seg(n); for (int i 0; i n; i) { cin seg[i].first seg[i].second; } sort(seg.begin(), seg.end(), [](const pairint, int a, const pairint, int b) { return a.second b.second; }); int lastEnd -1; int keep 0; for (auto p : seg) { if (p.first lastEnd) { keep; lastEnd p.second; } } cout n - keep endl; return 0; }lastEnd 初始化成 -1 是为了应对左端点从 0 开始的情况保证第一个区间一定能被选中。如果题目改成 start_i 可以为负那应该用 INT_MIN 或更小的值但本题给了 0 ≤ start_i-1 就够用。复杂度很舒服排序 O(n log n)扫描 O(n)总耗时不到 0.1 秒。要注意的是 n 最大 1e5输入量中等用 cin 加 ios::sync_with_stdio(false) 足够如果你对性能有执念可以写快读但没必要。3.4 现场容易被卡的隐蔽点这个题最常见的错误是把闭合区间当成开区间处理。题面明确说端点和端点重合也算冲突也就是说判断重叠的条件是 p.first lastEnd 才可保留而不是 p.first lastEnd。我见过有同学在练习平台上做过标准“活动安排”题那边允许端点相接于是直接把条件写成大于号结果在这个题上 WA 到怀疑人生。另一个容易忽视的是题目问的是“最少删除几个”而不是“最多保留几个”。虽然两者只差一个减法但真的有人输出 keep 而不是 n - keep只能说太紧张了。这类改问法的题目在复试机试里越来越常见读题时建议把“删”“留”“最少”“最多”这几个词圈出来。4. 真题三二维动态规划——收集贝壳最大数量并输出路径4.1 题目还原与样例说明题面海大校园里有一片 n × m 的沙滩网格1 ≤ n, m ≤ 100每个格子里有一定数量的贝壳第 i 行第 j 列的贝壳数为 a[i][j]0 ≤ a[i][j] ≤ 1000。你从左上角 (1,1) 出发走到右下角 (n,m)每次只能向右或向下移动一格。沿途收集经过格子里的贝壳起点和终点的贝壳也算收集。求能收集到的最大贝壳数量并按路径输出经过的格子坐标。输入第一行两个整数 n m接下来 n 行每行 m 个整数。输出第一行为最大贝壳数第二行按顺序输出路径上的坐标坐标用 (行,列) 表示中间用 - 连接。这个题的本质是数字三角形 / 网格路径最大和的变体但因为加了路径输出很多只会求最值的同学会卡住。我把它还原成贝壳主题是因为当年海大实际上也喜欢把算法题包装成“校园生活”背景这种做法现在很常见。4.2 思路拆解状态转移和路径记录的先后顺序最大值的状态转移很简单设 dp[i][j] 表示从起点走到 (i, j) 能收集到的最大贝壳数那么由于只能向右和向下走到达 (i, j) 的前一步要么是 (i-1, j)从上方来要么是 (i, j-1)从左方来所以dp[i][j] max(dp[i-1][j], dp[i][j-1]) a[i][j]边界情况是第一行只能从左往右走第一列只能从上往下走所以先把 dp[1][1] 到 dp[1][m] 和 dp[1][1] 到 dp[n][1] 初始化好再按行从上到下、从左到右递推。路径输出有两种思路。第一种是正推记录“从哪来”开一个二维数组 pre[i][j]值为 0 表示从上方来值为 1 表示从左方来。填 dp 的时候同步记录最后从 (n, m) 反推回 (1, 1)把坐标放进 vector 再反转输出。第二种是输出时递归回溯从终点往起点倒着找每次都看 dp[i][j] 减去 a[i][j] 后是等于 dp[i-1][j] 还是等于 dp[i][j-1]从而决定走向哪个格子。第二种不需要额外存储但递归深度最坏到 nm200 以内没问题不过现场我建议用第一种逻辑更直接。注意一个隐藏的陷阱当 dp[i-1][j] 和 dp[i][j-1] 相等时选哪条路径都不影响最大值但会影响路径的具体输出序列。判题系统对这类输出通常是特判或者允许任意合法路径但如果你按自己的顺序实现必须保证路径确实是按照你的 pre 数组回溯得到的不能在输出时临时换方向。4.3 AC 代码带上路径输出的完整实现#include bits/stdc.h using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, m; cin n m; vectorvectorint a(n 1, vectorint(m 1, 0)); for (int i 1; i n; i) { for (int j 1; j m; j) { cin a[i][j]; } } vectorvectorlong long dp(n 1, vectorlong long(m 1, 0)); vectorvectorint pre(n 1, vectorint(m 1, 0)); dp[1][1] a[1][1]; for (int j 2; j m; j) { dp[1][j] dp[1][j-1] a[1][j]; pre[1][j] 1; // 从左边来 } for (int i 2; i n; i) { dp[i][1] dp[i-1][1] a[i][1]; pre[i][1] 0; // 从上方来 } for (int i 2; i n; i) { for (int j 2; j m; j) { if (dp[i-1][j] dp[i][j-1]) { dp[i][j] dp[i-1][j] a[i][j]; pre[i][j] 0; } else { dp[i][j] dp[i][j-1] a[i][j]; pre[i][j] 1; } } } cout dp[n][m] \n; vectorpairint, int path; int x n, y m; while (x ! 1 || y ! 1) { path.push_back({x, y}); if (pre[x][y] 0) x--; else y--; } path.push_back({1, 1}); reverse(path.begin(), path.end()); for (int i 0; i (int)path.size(); i) { if (i) cout - ; cout ( path[i].first , path[i].second ); } cout \n; return 0; }dp 用 long long 是因为 100 × 100 个格子每个最多 1000最大和能到 1e7int 其实也放得下但我用 long long 是为了让你形成“看到求和就自动考虑上限”的肌肉记忆这个习惯在高考研复试里救过我很多次。4.4 输出路径的调试心得路径回溯最怕的是一边回溯一边发现走到了死路。我调试这个题的时候会故意用全 0 矩阵和全相同数字矩阵来测全 0 时无论路径怎么走最大和都是 0路径输出必须仍然是一条从左上到右下的完整路线全相同数字时dp 值每步都能算对但路径可能因为 if 分支的选择出现非预期走向没关系只要满足只向右向下且终点正确即可。另一个是坐标输出的空格问题题目要求用 “(行,列)” 的格式注意括号内逗号后面不要加空格路径之间用 “ - ”箭头前后各一个空格。判题机对格式字符很敏感我见过因为多打一个空格丢掉整题的情况。这种冤罪可不想再经历第二次。5. 真题四图论最短路——校园道路施工封闭5.1 题目还原与样例说明题面学校有 n 栋建筑1 ≤ n ≤ 1000m 条双向道路1 ≤ m ≤ 50000第 i 条道路连接 u_i 和 v_i通行时间为 w_i1 ≤ w_i ≤ 10000。你要从宿舍楼 s 出发去实验室 t。现在有 k 次施工查询1 ≤ k ≤ 1000每次查询给出一个道路编号 id表示该道路在本次查询中临时封闭只影响本次查询你需要输出封闭这条道路后从 s 到 t 的最短通行时间如果无法到达输出 -1。注意道路编号从 1 开始查询之间的封闭状态互不影响。输入先读 n m再读 m 行道路信息并记录编号然后读起点 s 终点 t再读 k最后 k 行每行一个 id。这个题是 2025 年机试中区分度最高的一道。因为它不是单纯的最短路模板题而是“最短路 多条查询”。如果每来一个封闭查询都跑一遍完整 Dijkstrak 最多 1000Dijkstra 用堆优化复杂度 O((n m) log n)总复杂度约 1000 × 50000也就是 5e7 级别在 C 下勉强可过但如果 m 再大一倍或者现场机器性能差一些就非常悬。5.2 思路拆解直接重跑还是先做预处理这个题最稳妥的现场做法是每次查询把对应边的权值临时改成 INF一个很大的数跑一遍 Dijkstra然后恢复。为什么不在查询前把原最短路径找出来然后只处理影响原路径的边因为一旦封闭的边不在原最短路上答案就是原最短路长度可以直接输出这是一个很大的优化。但实现时要小心如果原最短路有多条某条边不在你求出的那一条上但它可能在另一条同样长度的最短路上封闭它并不会改变答案而你的程序可能误判为“需要重新计算”。处理这个问题需要对每条边记录“是否被原最短路树使用”最短路树的选择会影响正确性现场很容易想漏。我建议基础一般的同学直接用“每次查询重跑 Dijkstra”的写法配合堆优化。n 只有 1000m 最多 5e4即使 k1000 也稳过因为每次 Dijkstra 实际访问的边数远小于 m。基础扎实、想冲满分的同学可以用“原路径不受影响直接输出原答案”的优化但必须以“封闭边是否在所有最短路上”为判断依据不能以“是否在其中一条最短路上”为依据。5.3 AC 代码重跑 Dijkstra 的稳健写法#include bits/stdc.h using namespace std; const long long INF 1e18; struct Edge { int u, v, w; }; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, m; cin n m; vectorEdge edges(m 1); vectorvectorpairint, int graph(n 1); for (int i 1; i m; i) { cin edges[i].u edges[i].v edges[i].w; graph[edges[i].u].push_back({edges[i].v, i}); graph[edges[i].v].push_back({edges[i].u, i}); } int s, t; cin s t; int k; cin k; auto dijkstra [](int blockId) - long long { vectorlong long dist(n 1, INF); priority_queuepairlong long, int, vectorpairlong long, int, greaterpairlong long, int pq; dist[s] 0; pq.push({0, s}); while (!pq.empty()) { auto [d, u] pq.top(); pq.pop(); if (d ! dist[u]) continue; if (u t) break; for (auto [v, edgeId] : graph[u]) { if (edgeId blockId) continue; long long w edges[edgeId].w; if (dist[v] dist[u] w) { dist[v] dist[u] w; pq.push({dist[v], v}); } } } return dist[t]; }; while (k--) { int id; cin id; long long ans dijkstra(id); if (ans INF / 2) { cout -1 \n; } else { cout ans \n; } } return 0; }这里图里存的是边编号而不是直接存权值是为了快速跳过被封闭的那条边。你在考场上一旦养成这种“边编号”的存储习惯处理边删除、边更新这类问题会非常顺手。5.4 为什么这道题容易翻车重边、INF、提前退出三个地方最容易出错。第一是重边题目没说没有重边那就要假设有。存边编号后即使两个结点间有多条边每条边都有独立编号封掉其中一个编号另一条还能正常走这是存编号的天然优势如果你直接把邻接矩阵存成最短权值封路后就会把好的边一起封掉。第二是 INF 的判断。我设置 INF 1e18判断不可达时用 ans INF / 2 而不是 ans INF这是因为 Dijkstra 过程中可能出现 INF 加上一个负数虽然本题不会严谨一点总没错。第三是提前退出的位置。我在 u t 时 break这时 dist[t] 已经是确定的不会影响正确性。但要注意如果你需要在路径输出时用到前驱数组就不能在第一次弹出 t 时直接 break因为多条等长路径的情况下前驱也许还没被最优方案更新完。这个题只问距离break 没问题。6. 实战复盘从准备到考场的经验清单6.1 编译环境和 OJ 使用提前确认四件事海大机试的判题系统每年环境细节可能微调我建议复试前一周就查清楚四点支持的编译器版本是否支持 C17比如结构体绑定 auto [d, u] 这类语法在旧版 GCC 下可能编不过系统是否自动开启 O2 优化main 函数返回值要求提交时是否要选择语言而不是靠文件后缀识别。这些都是很小的点但考场上编译器直接 RE 的感觉我不想你再体验一次。如果对本地环境不熟考前至少用学校的 OJ 或公开 OJ 练十道题熟悉标准输入输出、多组数据处理和错误反馈风格。尤其是多组数据很多机试题目是单组但一旦遇到多组而你没写 while 循环直接只过第一个样例。6.2 数据范围读题法从 int 到 long long我给自己定的规矩是任何题先看数据范围再动笔。a[i][j] 最大 1000、n m 最大 100dp 用 long long 不是必须但稳妥区间长度到 1e9排序用 long long 存也常见Dijkstra 的距离松弛可能超过 int必须用 long long。复试机试不可能在数据范围上故意坑你但它也不会保证“所有中间结果都不超过 int”所以把能开的都开成 long long 是最便宜的保险。另一个和读题相关的注意点是“单测还是多测”。今年海大机试四道题都是单组测试比较简单但往年有过最后一道题多组输入的情况题面会写“输入包含多组数据以 EOF 结束”这时候你必须把核心逻辑包在 while (cin ...) 里。不仔细看题是考场上最大的杀手。6.3 时间分配60 分钟的节奏建议两小时四道题我的节奏是前 15 分钟搞定第一题并完成一次本地样例和边界样例测试第二题和第三题各花 20 到 25 分钟包括写代码和调试最后一道题留 20 到 30 分钟如果做不完就把 Dijkstra 模板写上至少能过部分测试点。不要在一道题上死磕超过 40 分钟。机试判分通常按通过的数据点给分哪怕你的代码复杂度不对只要小数据能过也能拿一部分分。我见过太多人在最后一题上耗尽时间前面的题反而没有检查边界最后分数不理想。先保住确定能拿的分再考虑冲击难题这是复试现场最务实的策略。6.4 心态与习惯动手前先写 5 行注释最后分享一个我自己的小习惯读题后不管多简单先在代码最上方用注释写下“题目在求什么、输入范围、我用什么算法、复杂度是多少”。这四行注释不会直接帮你 AC但能强迫你在写代码前把思路固定下来避免写着写着发现方向错了推倒重来。今年有个同学跟我说他做完第三题输出路径时卡了很久就是因为没先想清楚 pre 数组回溯的方向我说这题如果你在代码前写两行“pre[x][y]0 上边来1 左边来”至少能少 10 分钟调试时间。机试考的不只是你会不会算法更是你在压力下能不能有条理地把会的东西写对。四道题复盘下来我对今年海大机试的总体评价是典型、不偏、但需要真实功夫。如果你能把这篇里的每一道题独立在纸上推导一遍再不看代码自己手敲一遍 AC你的复试机试准备就比大多数人扎实了。后面有时间我再结合其他院校的复试题做一个横向对比看看海大出题风格在同类 985 中处于什么水准。
