2025年清华大学计算机考研复试机试真题
本文整理清华大学计算机考研机试真题，并提供详细解析与代码实现，帮助同学们了解保研机试的难度与题型分
字符串
题目描述
给出一个长度为 $N$ 的 $01$ 字符串，问其中一共有多少个全为 $1$ 且长度至少为 $M$ 的连续子串。
输入格式
从标准输入读入数据。
输入的第一行包含两个正整数 $N$ ，$M$ ， 保证 $1 \leq N \leq 10^5$，$1 \leq M \leq N$ 。
输入的第二行包含一个长度为 $N$ 的 $01$ 字符串。
输出格式
输出到标准输出。
输出一个正整数，表示对应的答案。
输入样例
10 3
0111011110
输出样例
4
Combine
问题描述
学校一年级有3个班级：A班、B班和C班。每个班级都有$ n $个学生，编号为$ 1, 2, \ldots, n $。班级内学生的编号是唯一的，但不同班级间的编号可能重复（即每个班级都有各自的1号学生）。
A班和B班的每个学生有一个称为“人气值”的属性：
-
A班$ i $号学生的人气值为$ a_i $；
-
B班$ j $号学生的人气值为$ b_j $。
现在需要按照一定的规则组织A班和B班的学生，在C班学生的帮助下进行合作。合作规则由正整数参数$ p $（$ 1 \leq p \leq 10 $）决定，具体如下：
| $ p $ | 条件 |
|--------|------|
| $ p = 1 $ | $ i + j = k $ |
| $ p = 2 $ | $ i - j = k $ |
| $ p = 3 $ | $ i \times j = k $ |
| $ p = 4 $ | $ i / j = k $（即$ i = j \times k $） |
| $ p = 5 $ | $ \lfloor i / j \rfloor = k $（即$ i $整除$ j $，忽略余数） |
| $ p = 6 $ | $ i \text{ and } j = k $（按位与运算） |
| $ p = 7 $ | $ i \text{ or } j = k $（按位或运算） |
| $ p = 8 $ | $ i \text{ xor } j = k $（按位异或运算） |
| $ p = 9 $ | $ \min(i, j) = k $ |
| $ p = 10 $ | $ \max(i, j) = k $ |
对于C班的每个学生，需要计算其“合作值”$ c_k $。合作值的定义是：对于所有满足条件的$ (i, j) $对，将对应的$ a_i \cdot b_j $累加。即：
[
c_k = \sum_{\substack{1 \leq i, j \leq n \ \text{judge}(i, j, k) \text{为真}}} a_i \cdot b_j
]
其中，$ \text{judge}(i, j, k) $根据$ p $的不同而不同，具体如上表所示。
输入格式
从标准输入读入数据。
第一行输入两个正整数 $n$ 和 $p$。
第二行输入 $n$ 个整数 $a_1, a_2, ..., a_n$。
第三行输入 $n$ 个整数 $b_1, b_2, ..., b_n$。
相邻整数之间用一个空格隔开。
对于所有的测试点，输入的 $a_1, a_2, ..., a_n$ 和 $b_1, b_2, ..., b_n$ 均为不大于 $10$ 的正整数。
数据范围：$n <= 262143$，$1 <= p <= 10$
输出格式
输出到标准输出。
输出一行，包含 $n$ 个整数 $c_1, c_2, ..., c_n$。
相邻整数之间用一个空格隔开。
输入样例
7 1
1 2 3 4 5 6 7
2 3 4 5 6 7 8
输出样例
0 2 7 16 30 50 77
Friend
题目描述
F 学校有 $ n $ 个学生，编号为 $ 1, 2, \ldots, n $。这些学生之间存在 $ m $ 对好友关系。每对好友关系形如：$ u_j $ 号学生与 $ v_j $ 号学生互为好友（$ 1 \leq j \leq m $）。好友关系是双向的，这意味着 $ u_j $ 号学生是 $ v_j $ 号学生的好友，同时 $ v_j $ 号学生也是 $ u_j $ 号学生的好友。
F 学校要将 $ n $ 个学生均匀（等概率）随机地分为若干小组，每组 3 个学生。保证 $ n $ 是 3 的倍数，即能够恰好分完。在分组完毕后，每个组内的好友关系也会有不同的情况。现在，对于每个学生 $ i $，他希望计算他所在小组的 3 个学生当中以下每个事件发生的概率：
-
3 个学生两两均不为好友；
-
3 个学生中，除自己外的 2 个学生互为好友，不存在其他好友关系；
-
3 个学生中，自己与另外某个学生互为好友，不存在其他好友关系；
-
3 个学生中，恰好有 2 对好友关系，且有 2 个好友的那个人是自己（即：自己与另外 2 个学生分别互为好友，但他们两个不为好友）；
-
3 个学生中，恰好有 2 对好友关系，但有 2 个好友的那个人不是自己（即：存在某个学生 A 与自己和另外一个学生 B（分别）互为好友，但自己与 B 不为好友）；
-
3 个学生中两两互为好友。
请帮助每个学生计算吧！
输出格式
输出到标准输出。
输出 $n$ 行，每行 6 个最简分数，以空格隔开，表示每个学生每种情况的发生概率。
输出最简分数的形式为：先输出分子，再输出斜线 $/$，最后输出分母。
你应当输出最简分数，例如不应当输出 $3/6$，而应输出 $1/2$。
特殊地，如果所求的某个概率为 $0$，应当输出 $0/1$；概率为 $1$ 则输出 $1/1$。
输入样例
3 2
1 2
1 3
输出样例
0/1 0/1 0/1 1/1 0/1 0/1
0/1 0/1 0/1 0/1 1/1 0/1
0/1 0/1 0/1 0/1 1/1 0/1
Prime
题目描述
输入一个正整数 $X$，请你在 $X$ 后面添加若干位数字（不能不添加；添加的部分不得以数字 $0$ 开头），使得结果为质数，在这个前提下所得的结果应尽量小。
输入格式
从标准输入读入数据。
仅一行，输入一个正整数 $X$。
输入保证 $1 \leq X \leq 100$。
本题共有 $100$ 个测试点，每个测试点 $1$ 分。
输出格式
输出到标准输出。
输出一行，包含一个整数，表示所得的结果。
输入样例
1
输出样例
11
连通图的方案数
题目描述
给定一个包含 $ n $ 个点的无向图，共有 $ m $ 条边。
其中部分边已经存在于图中，其余边是可选的。要求计算有多少种加边方案使得加边后的图是连通的。
两种方案不同当且仅当至少有一条边在一种方案中被加入而在另一种方案中未被加入。
结果需要对 998244353 取模。
特殊条件：在最后一档子任务中，保证初始图的连通块个数不超过 15。
输入格式
- 第一行：两个正整数 $ n $ 和 $ m $（$ n \leq 10^5, m \leq 4 \times 10^5 $）。
- 接下来 $ m $ 行：每行三个整数 $ x, y, z $，表示 $ x $ 和 $ y $ 之间有一条边。若 $ z = 0 $，边已存在；若 $ z = 1 $，边可选。
输出格式
- 一个整数，表示方案数对 998244353 取模的结果。
样例
输入样例
5 6
1 2 0
2 5 0
2 3 1
3 4 1
2 3 0
2 4 1
输出样例
6