历年清华大学计算机保研机试真题
本文整理清华大学计算机保研机试真题，并提供详细解析与代码实现，帮助同学们了解保研机试的难度与题型分布
理发店
题目描述
理发店同时来了 $n$ 名顾客，你作为理发店的店长，需要为每名顾客先洗发再剪发。已知服务第 $i$ 名顾客洗发需要 $a_i$ 分钟，剪发需要 $b_i$ 分钟。
你需要遵循如下限制：
-
由于人手有限，同时只有最多一位顾客在洗发；同样地，同时只有至多一位顾客在剪发
-
对于某一位顾客，必须在洗发结束后才能开始剪发。
另外，由于这些顾客都是同时来的，你可以按照任意顺序为他们服务，没有先来后到的区别。请求出完成所有服务的最少时间。
输入格式
从标准输入读入数据。
一个输入文件中会包含多个输入数据。输入文件的第一行为一个正整数 $T$，表示输入数据的组数。
每个输入数据的第一行包含一个整数 $n$，表示顾客的数量。接下来 $n$ 行，每行包含两个正整数 $a_i$ 和 $b_i$，表示第 $i$ 位顾客洗发和剪发所需的时间。
输出格式
输出到标准输出。
输出 $T$ 行，每行包含一个整数，表示你对该输入数据求出的最少时间。
数据范围
对于所有输入数据，保证 $1 \leq T \leq 100$，每个数据的 $0 \leq n \leq 5$，且 $1 \leq a_i, b_i \leq 100$。
输入样例1
2
3
10 20
25 40
20 30
3
30 35
25 25
25 30
输出样例1
100
115
飞镖
小 $R$ 在一个 $n * m$ 的网格中玩飞镖游戏，其中的每个格子可以用二维坐标 $(x,y)$ 指定（其中 $1 <= x <=n, 1 <= y <= n$），X 轴以向下为递增正方向，而 Y 轴以向右为递增正方向。网格中每个格子上都可以有至多一个标记，初始时所有各自均没有标记。
小 $R￥ 会依次投掷 $q$ 枚飞镖，每一枚飞镖由三个参数 $x, y, t$ 指定，其中 $(x, y)$ 表示其投掷位置， $t$ 为飞镖类型，为 + , x , * 三者之一，具体说明如下：
对于所有类型的飞镖，都会在投掷向 $(x, y)$ 位置写入一个对应标记（如 + 型飞镖会在 位置写入 +） 。如果此位置原本已有标记，则会将其覆盖。
对于 + 类型飞镖，投掷时会向投掷位置的上、下、左、右的四个方向各发射一只小飞镖。这些小飞镖会沿着各自的方向以每秒 1 格的速度一直飞行，直到其中之一碰撞到了某个已有的标记或者超出网格边界。当碰撞或出界发生时，所有的小飞镖会同时停止飞行。对于发生碰撞的小飞镖，会将其所在位置的标记清除。对于未发生碰撞也未出界的小飞镖，会将其所在位置标记为 +。
对于 x 类型飞镖，投掷时会向投掷位置的左上、左下、右上、右下的四个方向各发射一只小飞镖，速度为每秒 $\sqrt{2}$ 格。其余规则同上，但对于未发生碰撞也未出界的小飞镖，会将其所在位置标记为 x。
对于 * 类型飞镖，投掷时会向投掷位置的上、下、左、右、左上、左下、右上、右下的八个方向各发射一只小飞镖。上下左右方向的速度为每秒 $\sqrt{2}$ 格，而斜线方向的速度为每秒 $1$ 格。其余规则同上，但对于未发生碰撞也未出界的小飞镖，会将其所在位置标记为 *。
下面将举例说明：
例如 $n = 5, m = 6$ ，初始时棋盘为空，我们用 . 表示一个空位置。
......
......
......
......
......
假设向 $(2,2)$ 投掷一枚 + 类型的飞镖，则会先在 $(2,2)$ 位置写入 +：
......
.+....
......
......
......
然后，会向上、下、左、右四个方向各发射一只小飞镖，它们会以每秒 $1$ 格的速度飞行。向上、向左的两只小飞镖会在 $2$ 秒后出界，而此时向下、向右的两只小飞镖会停止飞行并将其所在位置标记为 +：
......
.+.+..
......
.+....
......
假设在此基础上，向 $(3,3)$ 投掷一枚 x 类型的飞镖，则会先在 $(3,3)$ 位置写入 x：
......
.+.+..
..x...
.+....
......
然后，会向左上、左下、右上、右下四个方向各发射一只小飞镖，它们会以每秒 $\sqrt{2}$ 格的速度飞行。向左上、左下、右上的三只小飞镖会在 秒后碰撞到已有的标记，而此时向右下的一只小飞镖会停止飞行并将其所在位置标记为 x：
......
......
..x...
...x..
......
假设在此基础上，向位置 $(5,4)$ 投掷一枚 * 类型的飞镖，则会先在 $(5,4)$ 位置写入 *：
......
......
..x...
...x..
...*..
然后，会向上、下、左、右、左上、左下、右上、右下八个方向各发射一只小飞镖，它们会以每秒 $1$ 格或 $\sqrt{2}$ 格的速度飞行。向上的小飞镖会在 秒后碰撞到已有的标记，与此同时向下、左下、右下的三只小飞镖会出界，其余方向的小飞镖会停止移动，最终棋盘状态如下：
......
......
..x...
..*.*.
..***.
假设在此基础上，向位置 $(3,3)$ 投掷一枚 x 类型的飞镖，则最终状态如下（注意覆盖了该位置的原有标记）：
x...x.
......
..x...
..*.*.
x.**..
本题目将会给出 $n, m, q$ 和 $q$ 个飞镖的信息，你需要对于投掷的每个飞镖回答：
-
该飞镖是否覆盖了投掷位置 $(x,y)$ 的原有标记？如果覆盖了，原有的标记是什么？
-
该飞镖产生的小飞镖飞行了多少秒的时间？
-
产生的每个小飞镖的最终状态是什么？（碰撞到了标记/出界/未碰撞也未出界）
输入格式
从标准输入读入数据。
第一行输入三个整数 $n,m,q$，以空格分隔。
接下来 $q$ 行，每行输入三个元素 $x,y,t$，以空格分隔，表示一枚飞镖的信息。
输出格式
输出到标准输出。
输出 $q$ 行，每行输出三个元素，以空格分隔，表示一枚飞镖的信息：
-
如果该飞镖覆盖了投掷位置 $(x, y)$ 的原有标记，则输出原有的标记字符，否则输出
.； -
输出该飞镖产生的小飞镖飞行了多少秒时间；
-
输出产生的每个小飞镖的最终状态，为 4 个或 8 个字符，
+型飞镖按照上、下、左、右的顺序输出，x型飞镖按照左上、左下、右上、右下的顺序输出，*型飞镖按照上、下、左、右、左上、左下、右上、右下的顺序输出，如果该小飞镖碰撞到了标记则输出标记字符，如果该小飞镖出界则输出o，如果该小飞镖未碰撞也未出界则输出.。
输入样例
5 6 4
2 2 +
3 3 x
5 4 *
3 3 x
输出样例
. 2 o.o.
. 1 +++.
. 1 xo...o.o
x 2 ...*
最小值网络
题目描述
最小值网络是由若干个比较操作 $\text{Compare}(a_x, a_y)$（其中 $1 \leq x < y \leq n$）组成的程序，这个程序满足，无论 $n$ 个变量 $a_1, a_2, \cdots, a_n$ 的取值如何，按照程序的运行方式（依次考虑每个比较操作，若 $a_x > a_y$ 则交换 $a_x$ 与 $a_y$），程序运行完成后 $a_1$ 对应所有变量中的最小值。
称一个最小值网络是可靠的当且仅当对于任意一个网络中的比较操作，删除这个操作保留其他操作及它们的顺序，得到的网络仍然是个最小值网络。
现在给定小明已经搭好的一些比较器（即一些比较操作），你只能在这些比较操作之后加入若干操作。问至少要加多少个比较操作才能让网络变成可靠的。
输入格式
从标准输入读入数据。
输入的第一行两个整数 $n,m$，表示变量的数量和小明决定好的比较操作数量。
接下来 $m$ 行每行两个整数 $x,y$，表示一个比较操作 $\text{Compare}(a_x, a_y)$。
输出格式
输出到标准输出。
输出一行一个整数表示最少需要在已经决定的比较操作后添加多少个比较操作才能让这个网络变为可靠的。
输入样例1
3 3
1 2
1 2
2 3
输出样例1
3
树上计数
题目描述
给一棵N个点的有根树，所有点从1到N标号，且以1号点为根。
问树上有多少个点满足其子树内（包含该点本身）的节点数大于等于L且小于等于R。
输入格式
从标准输入读入数据。
输入的第一行包含三个正整数N, L, R, 保证N ≤ $10^5$, L ≤ R ≤ N。
接下来的N - 1行，第i行包含一个正整数$p_{i+1}$, 表示点i + 1的父亲节点编号。输入保证合法。
输出格式
输出到标准输出。
输出一个正整数，表示对应的答案。
输入样例1
7 2 4
3
1
1
3
4
6
输出样例1
3
众数
题目描述
有 $n$ 个序列（依次编号为 $0, 1, \ldots, n-1$），初始时各个序列都为空，你的任务是维护这 $n$ 个序列，需要进行的各种操作的表示与意义如下：
-
$1$ $i$ $k$ $x$：在第 $i$ 个序列的末尾插入 $k$ 个值都为 $x$ 的数；
-
$2$ $i$ $k$ $x$：删除第 $i$ 个序列末尾的 $k$ 个数，若该序列已不足 $k$ 个数，则删除序列中全部的数；
-
$3$ $i$：询问第 $i$ 个序列的众数（出现次数最多的数，若出现次数最多的数有多种，取其中数值最小的数）。
输入格式
从标准输入读入数据。
输入的第一行为两个正整数 $n, q$，表示序列的个数与操作次数。
接下来 $q$ 行描述依次进行的操作，每行描述一个操作，每个操作的输入方式同题目描述。
输出格式
输出到标准输出。
对于每个询问操作，输出询问时对应序列中出现次数最多的数中数值最小者，并换行。如果没有，输出-1。
数据范围
$1 \leq n \leq 10^5, 1 \leq q \leq 10^6$，任何出现的序列编号 $i$ 都满足 $0 \leq i < n$，序列中出现的任何数值 $x$ 均满足 $0 \leq x \leq 10^9$，插入和删除操作中的数目 $k$ 满足 $1 \leq k \leq 10^9$。
输入样例1
2 6
1 0 2 1
1032
3 0
2 0 1
3 0
3 1
输出样例1
2
1
-1