历年北京大学计算机保研机试真题
本文整理北京大学计算机保研机试真题，并提供详细解析与代码实现，帮助同学们了解保研机试的难度与题型分布
有趣的跳跃
题目描述
一个长度为 $n$（$n > 0$）的序列中存在“有趣的跳跃”当且仅当相邻元素的差的绝对值经过排序后正好是从 $1$ 到 $(n-1)$。
例如，序列 1 4 2 3 存在“有趣的跳跃”，因为相邻元素的差的绝对值分别为 $3$, $2$, $1$，排序后为 $1$, $2$, $3$，正好覆盖 $1$ 到 $(n-1)=3$ 的范围。
任何只包含单个元素的序列一定存在“有趣的跳跃”。
你需要写一个程序判定给定序列是否存在“有趣的跳跃”。
输入格式
第一行包含一个整数 $n$（$0 < n < 3000$），表示序列的长度。
第二行包含 $n$ 个整数，依次为序列中的各个元素，每个元素的绝对值不超过 $1,000,000,000$。
输出格式
如果该序列存在“有趣的跳跃”，输出 "Jolly"；否则输出 "Not jolly"。
输入样例
4 1 4 2 3
输出样例
Jolly
走迷宫
题目描述
一个迷宫由 $ R $ 行 $ C $ 列格子组成，有的格子里有障碍物，不能走；有的格子是空地，可以走。
给定一个迷宫，求从左上角走到右下角最少需要走多少步（数据保证一定能走到）。
只能在水平方向或垂直方向走，不能斜着走。
输入格式
第一行是两个整数，$ R $ 和 $ C $，代表迷宫的行数和列数。
（$ 1 \leq R, C \leq 40 $）
接下来是 $ R $ 行，每行 $ C $ 个字符，代表整个迷宫。
空地格子用 $ . $ 表示，有障碍物的格子用 $ # $ 表示。
迷宫左上角和右下角都是 $ . $。
输出格式
输出从左上角走到右下角至少要经过多少步（即至少要经过多少个空地格子）。
计算步数要包括起点和终点。
输入样例
5 5
.....
###..
.#...
.#.#.
.#...
输出样例
9
最大上升子序列和
题目描述
一个数的序列 $ b_i $，当 $ b_1 < b_2 < ... < b_S $ 的时候，我们称这个序列是上升的。
给定一个序列 $ (a_1, a_2, ..., a_N) $，我们可以得到一些上升的子序列 $ (a_{i1}, a_{i2}, ..., a_{iK}) $，这里 $ 1 \leq i1 < i2 < ... < iK \leq N $。
比如，对于序列 $ (1, 7, 3, 5, 9, 4, 8) $，它的一些上升子序列如 $ (1, 7) $、$ (3, 4, 8) $ 等等。
这些子序列中，序列和最大为 18，为子序列 $ (1, 3, 5, 9) $ 的和。
你的任务是对于给定的序列，求出最大上升子序列和。
注意，最长的上升子序列的和不一定是最大的，比如序列 $ (100, 1, 2, 3) $ 的最大上升子序列和为 100，而最长上升子序列为 $ (1, 2, 3) $。
输入格式
输入的第一行是序列的长度 $ N $（$ 1 \leq N \leq 1000 $）。
第二行给出序列中的 $ N $ 个整数，这些整数的取值范围都在 0 到 10000（可能重复）。
输出格式
输出最大上升子序列和。
输入样例
7
1 7 3 5 9 4 8
输出样例
18
Arctic Network
题目描述
The Department of National Defence (DND) wishes to connect several northern outposts using a wireless network. Two communication technologies are available:
-
Radio Transceivers: Each outpost has a radio transceiver. Two outposts can communicate via radio if the distance between them does not exceed $ D $, where $ D $ depends on the transceiver power. All transceivers must have the same $ D $.
-
Satellite Channels: Some outposts have satellite channels. Any two outposts with satellite channels can communicate directly via satellite, regardless of distance.
Your task is to determine the minimum $ D $ required such that every pair of outposts has at least one communication path (direct or indirect).
输入格式
-
First line: $ N $ (number of test cases, $ N \geq 1 $).
-
Per test case:
-
First line: $ S $ (number of satellite channels, $ 1 \leq S \leq 100 $) and $ P $ (number of outposts, $ S < P \leq 500 $).
-
Next $ P $ lines: Coordinates $ (x, y) $ of each outpost (integers between 0 and 10,000).
输出格式
For each test case, output the minimum $ D $ required, rounded to 2 decimal places.
输入样例
1
2 4
0 100
0 300
0 600
150 750
输出样例
212.13
Hopscotch
题目描述
$Hopscotch$（跳房子）是一种流行的游戏。
规则非常简单：我们在地面上画一些房子，然后扔一块石头。
根据石头的位置，我们决定跳到哪个房子。
这里，我们用 $x$ 轴上的连续正整数坐标表示房子，第 $i$ 个房子的坐标是 $i$。
我们还假设有无限多的房子。
然后，我们定义新的规则如下，每次我们扔石头时：
-
如果石头落在房子里（标记为 $H$），我们可以从当前房子 $i$ 跳到房子 $3 \times i$；
-
如果石头落在房子外（标记为 $O$），我们可以从当前房子 $i$ 跳到房子 $i/2$（向下取整）。
例如，初始时在房子 $1$，为了到达房子 $6$，我们可以用两种方式扔石头：$HHHOO$ 或 $HHOHO$。
现在，你的任务是计算从源房子 $n$ 到目标房子 $m$ 所需的最少跳跃次数（$k$）。
你还应该输出相应的扔石头的方式。
如果有多种方式，请按字典序输出最小的方式。
输入格式
有多组测试用例。
对于每组测试用例，有两个整数 $n$ 和 $m$（$1 \leq n, m \leq 1000$），表示源房子和目标房子。
输入以 $0$ $0$ 结束。
输出格式
对于每组测试用例，输出的第一行是一个整数，表示最少的跳跃次数（$k$）。
测试数据保证有解且 $k \leq 25$。
第二行输出相应的扔石头的方式。
输入样例
1 6
0 0
输出样例
5
HHHOO