历年中国科学技术大学计算机保研机试真题
本文整理中国科学技术大学计算机保研机试真题，并提供详细解析与代码实现，帮助同学们了解保研机试的难度与题型分布
运动会比赛日程安排
题目描述
某运动会设立 $M$ 个比赛项目，每个运动员（共 $N$ 个运动员）可以参加多个项目，每个项目的比赛时长相同。
试问如何安排比赛日程，既可以使同一运动员参加的项目不安排在同一单位时间进行，又使总的竞赛日程最短。
输入格式
第一行包含两个整数 $N$ 和 $M$，分别表示运动员的数量和比赛项目的数量。
接下来的 $N$ 行，每行包含若干个整数，表示该运动员参加的比赛项目编号。
输出格式
输出一个整数，表示最短的竞赛日程（单位时间数）。
输入样例
3 4
1 2 3
2 3
3 4
输出样例
3
卷积运算
题目描述
卷积运算在数学、信号处理、深度学习等诸多领域中均有广泛应用，深度学习中的卷积神经网络模型 $CNN$ 为使用卷积运算的代表模型之一。
对一个高为 $h$、宽为 $w$ 的矩阵 $I$，和一个边长为 $k$ 的方形卷积核 $K$，经基本正向卷积运算得到的矩阵 $S$ 满足：
$$ S(i,j) = \sum_{0 \leq m < k} \sum_{0 \leq n < k} I(i+m,j+n) \cdot K(m,n) $$
其中 $0 \leq i \leq h-k$, $0 \leq j \leq w-k$。
在 $CNN$ 中，有时为了缩小特征尺寸，卷积运算中会指定步幅 $s$ 进行下采样，使经过卷积运算的矩阵缩小约 $s$ 倍，即：
$$ S(i,j) = \sum_{0 \leq m < k} \sum_{0 \leq n < k} I(s \cdot i+m, s \cdot j+n) \cdot K(m,n) $$
此时宜对 $i,j,m,n$ 限制 $s \cdot i+m < h$, $s \cdot j+n < w$，从而矩阵 $S$ 的大小确定。
现在给定一个高为 $h$、宽为 $w$ 的矩阵 $I$，和一个边长为 $k$ 的方形卷积核 $K$，并设置步幅为 $s$，求经正向卷积运算得到的矩阵 $S$。
输入格式
输入第一行四个正整数 $h$, $w$, $k$, $s$。
接下来输入矩阵 $I$，共计 $h$ 行，每行包含 $w$ 个整数。
接下来输入卷积核 $K$，共计 $k$ 行，每行包含 $k$ 个整数。
输出格式
输出运算后得到的矩阵 $S$。
数据范围
对于 $100\%$ 数据，满足 $0 < s \leq k \leq \min(h,w) \leq 100$。
矩阵 $I$ 和 $K$ 中各元素的绝对值不超过 $100$。
输入样例
4 4 2 1
1 2 3 4
2 3 4 1
3 4 1 2
4 1 2 3
1 0
0 -1
输出样例
-2 -2 2
-2 2 2
2 2 -2
马走棋盘问题
题目描述
给定一个 $m \times n$ 大小的棋盘，给定一个初始位置 $(a, b)$。
输入一个数代表棋盘上不能走的点的个数 $t$，给出 $t$ 个点的坐标。
问一个马（马走日）从 $(a, b)$ 出发，能否不重复地把棋盘上（除不能走的点之外）的所有点都走一遍。
若能走，则输出有多少种走完的方式；若不能，则输出 $0$。
输入格式
第一行包含四个整数 $m$, $n$, $a$, $b$，分别表示棋盘的行数、列数、初始位置的行坐标和列坐标。
第二行包含一个整数 $t$，表示不能走的点的个数。
接下来的 $t$ 行，每行包含两个整数 $x_i$, $y_i$，表示不能走的点的坐标。
输出格式
输出一个整数，表示有多少种走完的方式；若不能走完，则输出 $0$。
输入样例
3 3 1 1
1
2 2
输出样例
2
最大公约数
题目描述
读入 $n$ 个正整数，求出这 $n$ 个数的最小值、最大值以及它们两的最大公约数，并输出。
输入中第一行为 $n$，接下来为 $n$ 个大于零的整数。
输入格式
第一行为 $n$。
第二行是 $n$ 个大于零的整数，用空格隔开。
输出格式
分别输出最小值、最大值和它们两的最大公约数，用空格隔开。
输入样例
3
4 6 8
输出样例
4 8 4
摸球
题目描述
箱子里有 $n$ 个红球和 $m$ 个黑球。
现采用不放回的方式随机依次从箱子里摸球，求摸到第一个黑球时，已摸到红球的期望数量。
输入格式
输入一行两个正整数 $n$, $m$，分别表示红球数和黑球数。
输出格式
输出一行一个实数，表示所要求的期望答案，结果四舍五入保留 $3$ 位小数。
数据范围
-
对于 $30\%$ 的数据，$1 \leq n \leq 2$。
-
对于 $60\%$ 的数据，$1 \leq n, m \leq 10^5$。
-
对于 $100\%$ 的数据，$1 \leq n, m \leq 10^9$。
输入样例
1 3
输出样例
0.250