2025年北京大学计算机考研复试机试真题
本文整理北京大学计算机考研机试真题，并提供详细解析与代码实现，帮助同学们了解保研机试的难度与题型分
01 最小生成树
题目描述
给定一张 $n$ 个点的完全图。
图中所有边的边权均为 $0/1$，且有且仅有 $m$ 条边边权为 $1$。
求解该完全图的最小生成树，你只需要输出最小生成树的边权和即可。
输入格式
第一行两个数字 $n$, $m$ 表示点数，以及边权为 $1$ 的边数。
$(m \leq \min{200000, \frac{n(n-1)}{2}})$
接下来 $m$ 行，一行两个数字 $a[i]$, $b[i]$，表示连接 $a[i]$, $b[i]$ 的边，其边权为 $1$ $(1 \leq a[i] < b[i] \leq n)$。
保证输入的边两两不同。
输出格式
一行一个数字，表示最小生成树的边权和。
输入样例
6 11
1 3
1 4
1 5
1 6
2 3
2 4
2 5
2 6
3 4
3 5
3 6
输出样例
2
打怪救公主
题目描述
公主被魔王抓起来关在了迷宫的某处，骑士想要拯救公主，也进入了迷宫。
但是魔王不会轻易让骑士拯救公主，魔王在迷宫中安排了许多怪兽。
每个怪兽都有血量，骑士也有初始血量 $ t $，骑士打败怪兽后血量的减少量为怪物的血量值，血量减到 $ 0 $，骑士会死去。
迷宫由 $ m \times n $ 个方块组成，每个方块有墙或者路或者怪物，骑士在其中一个方块上，他每个时间单位可以四个方向（上、下、左、右）走到相邻方格，若遇到怪物，必须打败怪物才能继续前进。
请帮忙判断骑士能否成功拯救公主，如果能，给出骑士还剩的最大血量。
输入格式
第一行为三个整数 $ m $、$ n $ 和 $ t $，$ t $ 表示骑士的初始血量。
第 $ 2 $ 至 $ m+1 $ 行描述了迷宫，迷宫以 $ m $ 行 $ n $ 列的方格组成，若方格为 $ . $ 则表示骑士可以通过，若方格为 $ # $ 则表示墙，骑士不能通过，若方格为数字则表示怪物，数字为怪物的血量，保证怪物的血量小于 $ 10 $（一位数）。
$ * $ 表示了骑士当前所在的位置，$ + $ 表示公主被囚禁的位置。
输出格式
若骑士能成功拯救公主，则输出骑士走到公主所囚禁方格所剩最大血量，否则输出 $ 0 $。
输入样例
5 6 10
..*...
.#2###
5#..4#
.##9.#
.#+..#
输出样例
4
最低通行费
题目描述
一个商人穿过一个 $N \times N$ 的正方形的网格，去参加一个非常重要的商务活动。
他要从网格的左上角进，右下角出，每穿越中间 $1$ 个小方格，都要花费 $1$ 个单位时间。
商人必须在 $(2N-1)$ 个单位时间穿越出去。
而在经过中间的每个小方格时，都需要缴纳一定的费用。
这个商人期望在规定时间内用最少费用穿越出去。
请问至少需要多少费用？
注意：不能对角穿越各个小方格（即，只能向上下左右四个方向移动且不能离开网格）。
输入格式
第一行是一个整数，表示正方形的宽度 $N$ $(1 \leq N < 100)$；
后面 $N$ 行，每行 $N$ 个不大于 $100$ 的整数，为网格上每个小方格的费用。
输出格式
输出一个整数，表示至少需要的费用。
输入样例
5
1 4 6 8 10
2 5 7 15 17
6 8 9 18 20
10 11 12 19 21
20 23 25 29 33
输出样例
109
冰阔落
题目描述
老王喜欢喝 $冰阔落$。
初始时刻，桌面上有 $n$ 杯阔落，编号为 $1$ 到 $n$。
老王总想把其中一杯阔落倒到另一杯中，这样他一次性就能喝很多很多 $阔落$，假设杯子的容量是足够大的。
有 $m$ 次操作，每次操作包含两个整数 $x$ 与 $y$。
若原始编号为 $x$ 的阔落与原始编号为 $y$ 的阔落已经在同一杯，请输出 $"Yes"$；否则，我们将原始编号为 $y$ 所在杯子的所有阔落，倒往原始编号为 $x$ 中的阔落所在的杯子，并输出 $"No"$。
最后，老王想知道哪些杯子有 $冰阔落$。
输入格式
有多组测试数据，少于 $5$ 组。
每组测试数据，第一行两个整数 $n$, $m$ ($n$, $m$ <= $50000$)。
接下来 $m$ 行，每行两个整数 $x$, $y$ ($1$ <= $x$, $y$ <= $n$)。
输出格式
每组测试数据，前 $m$ 行输出 $"Yes"$ 或者 $"No"$。
第 $m+1$ 行输出一个整数，表示有 $阔落$ 的杯子数量。
第 $m+2$ 行有若干个整数，从小到大输出这些杯子的编号。
输入样例
3 2
1 2
2 1
4 2
1 2
4 3
输出样例
No
Yes
2
1 3
No
No
2
1 4
田忌赛马
题目描述
在田忌赛马的故事中，孙膑用自己的 $下等马$ 对战对手的 $上等马$，自己 $上等马$ 对阵对手的 $中等马$，自己的 $中等马$ 对阵对手的 $下等马$，从而赢得了胜利。
现在即将进行的是 $N$ 匹马的赛马比赛，双方队伍的马各分为 $N$ 等。
已知只有当我方马的等级比对方马等级高 $X$ 等以上（包含 $X$）时，我方才可以取得这场比赛的胜利。
如果在 $N$ 场比赛中我方的胜场数大于对方，则我方取得最终的胜利。
现在已知对方这 $N$ 场比赛的出战方案，请计算所有令我方最终获胜的出战方案。
输入格式
第一行两个整数，$N$ 和 $X$。
$N \leq 9$, $0 \leq X$ 第二行 $N$ 个正整数，$A(1) \ldots A(N)$。
$A(i)$ 表示第 $i$ 场比赛对方马的等级，$1 \leq i \leq N$。
等级越高越强
输出格式
按字典序输出所有我方最终获胜的方案，每个方案一行。
每行是 $N$ 个正整数，第 $i$ 个数表示我方第 $i$ 场比赛马的等级。
输入样例
3 1
3 2 1
输出样例
1 3 2