2023年12月 GESP C++ 8级

小杨要从 $A$ 城到 $B$ 城，又想顺路游览一番。他有两个选项：$1$、坐高铁路到 $C$ 城游览，再坐高铁或飞机到 $B$ 城；$2$、坐船到 $D$ 城游览，再坐船、高铁或飞机到 $B$ 城。请问小杨从 $A$ 城到 $B$ 城共有几种交通方案可以选择？（ ）。

以下哪个函数声明是符合语法的，且在调用时可以将二维数组的名字作为实际参数传递给形式参数 $a$？（ ）。

下面有关 C++ 类和对象的说法，错误的是（ ）。

使用邻接矩阵表达 $n$ 个顶点的有向图，则该矩阵的大小为（ ）。

$5$ 位同学排队，其中一位同学不能排在第一位，则共有多少种可能的排队方式？（ ）。

一个无向图包含 $n$ 个顶点，则其最小生成树包含多少条边？（ ）。

已知三个 double 类型的变量 $a$ 、 $b$ 和 $theta$ 分别表示一个三角形的两条边长及二者的夹角（弧度），则下列哪个表达式可以计算这个三角形的面积？（ ）。

对有 $n$ 个元素的二叉排序树进行中序遍历，其时间复杂度是（ ）。

假设输入参数 $m$ 和 $n$ 满足 $m\ge 1$ 且 $n\ge 1$，则下面程序的最差情况的时间复杂度为（ ）。

下面程序的时间复杂度为（ ）。

下面程序的时间复杂度为（ ）。

下面的程序使用出边的邻接表表达有向图，则下列选项中哪个是它表达的图？（ ）。

下面程序的输出为（ ）。

下面程序的输出为（ ）。

下面的程序中，二维数组 h 和 v 分别代表如下图所示的网格中的水平边的时间消耗和垂直边的时间消耗。 程序使用动态规划计算从左下角到右上角的最小时间消耗，则横线处应该填写下列哪个选项的代码？（ ）。

C++ 语言非常强大，可以用来求解方程的解。例如，如果变量 $x$ 为 double 类型的变量，则执行语句 x * 2 - 4 = 0; 后，变量 $x$ 的值会变为 $2.0$。

一个袋子中有 $3$ 个完全相同的红色小球、$2$ 个完全相同的蓝色小球。每次从中取出 $1$ 个，且不放回袋子，这样进行 $3$ 次后，将取出的小球依次排列，则可能的颜色顺序有 $7$ 种。

杨辉三角，是二项式系数的一种三角形排列，在中国南宋数学家杨辉 $1261$ 年所著的《详解九章算法》一书中出现，是中国数学史上的一项伟大成就。

$n$ 个顶点的有向完全图（不带自环）有 $n(n-1)$ 条边。

如果待查找的元素确定，只要哈希表的大小不小于查找元素的个数，就一定存在不会产生冲突的哈希函数。

动态规划算法的时间复杂度一般为：必要状态的数量，乘以计算一次状态转移方程的时间复杂度。

已知 int 类型的变量 $a$ 、$b$ 和 $h$ 中分别存储着一个梯形的顶边长、底边长和高，则这个梯形的面积可以通过表达式 (a + b) * h / 2 求得。

判断图是否连通只能用广度优先搜索算法实现。

在 $n$ 个元素的二叉排序树中查找一个元素，最好情况的时间复杂度是 $O(1)$。

给定 double 类型的变量 $x$，且其值大于等于 $0$，我们可以通过二分法求出 x\sqrt{x}x​ 的近似值。

试题名称：奖品分配

时间限制：1.0 s | 内存限制：512.0 MB

题目描述

班上有 $N$ 名同学，学号从 $0$ 到 $N-1$。有 $M$ 种奖品要分给这些同学，其中，第 $i$ 种奖品总共有 aia_iai​ 个 （$i=0,1,\cdots ,M-1$）。

巧合的是，奖品的数量不多不少，每位同学都可以恰好分到一个奖品，且最后剩余的奖品不超过 $1$ 个（即：N≤a0+a1+⋯+aM−1≤N+1N\le a_0+a_1+ \cdots +a_{M-1}\le N+1N≤a0​+a1​+⋯+aM−1​≤N+1）。

现在，请你求出每个班级礼物分配的方案数，所谓方案，指的是为每位同学都分配一个种类的奖品。

只要有一位同学获得了不同种类的奖品，即视为不同的方案。方便起见，你只需要输出方案数对 109+710^{9}+7109+7 取模后的结果即可。

共有 $T$ 个班级都面临着奖品分配的问题，你需要依次为他们解答。

输入格式

第一行一个整数 $T$，表示班级数量。

接下来 $T$ 行，每行若干用单个空格隔开的正整数。首先是两个正整数$N,M$，接着是 $M$ 个正整数 a0,a1...aM−1a_0,a_1...a_{M-1}a0​,a1​...aM−1​。保证 N≤a0+a1+⋯+aM−1≤N+1N \le a_0+a_1+\cdots+a_{M-1} \le N+1 N≤a0​+a1​+⋯+aM−1​≤N+1。

输出格式

输出 $T$ 行，每行一个整数，表示该班级分配奖品的方案数对 109+710^{9}+7109+7 取模的结果。

样例输入 #1

3
3 2 1 2
3 2 1 3
5 3 1 3 1 

样例输出 #1

3
4
20

样例输入 #2

5
100 1 100
100 1 101
20 2 12 8
123 4 80 20 21 3
999 5 101 234 499 66 99

样例输出 #2

1
1
125970
895031741
307187590

说明/提示

样例解释 1

对于第 $1$ 个班级，学号为 $0,1,2$ 的同学可以依次分别获得奖品 $0,1,1$，也可以依次分别获得奖品 $1,0,1$，也可以依次分别获得奖品 $1,1,0$ ，因此共有 $3$ 种方案。

对于第 $2$ 个班级，学号为 $0,1,2$ 的同学可以依次分别获得奖品 $0,1,1$ ，也可以依次分别获得奖品 $1,0,1$，也可以依次分别获得奖品 $1,1,0$，也可以依次分别获得奖品 $1,1,1$，因此共有 $4$ 种方案。

对于第 $3$ 个班级，可以把编号为 $0$ 的奖品分配给 $5$ 名同学中的任意一名，共有 $5$ 种方案；再把编号为 $2$ 的奖品分配给剩余 $4$ 名同学中的任意一名，共有$4$ 种方案；最后给剩余 $3$ 名同学自然获得 $1$ 号奖品。因此，方案数为 $5\times 4=20$。

数据范围

对于 $30\%$ 的测试点，保证 $N\le 10$。

对于另外 $30\%$ 的测试点，保证 $M=2$。

对于所有测试点，保证 $N\le 1000$；保证 $T\le 1000$ ；保证 $M\le 1001$。

试题名称：大量的工作沟通

时间限制：1.0 s | 内存限制：512.0 MB

题目描述

某公司有 $N$ 名员工，编号从 $0$ 至 $N-1$。其中，除了 $0$ 号员工是老板，其余每名员工都有一个直接领导。我们假设编号为 $i$ 的员工的直接领导是 fif_ifi​。

该公司有严格的管理制度，每位员工只能受到本人或直接领导或间接领导的管理。具体来说，规定员工 $x$ 可以管理员工 $y$，当且仅当 $x=y$，或 x=fyx=f_yx=fy​，或 $x$ 可以管理 fyf_yfy​。特别地，$0$ 号员工老板只能自我管理，无法由其他任何员工管理。

现在，有一些同事要开展合作，他们希望找到一位同事来主持这场合作，这位同事必须能够管理参与合作的所有同事。如果有多名满足这一条件的员工，他们希望找到编号最大的员工。你能帮帮他们吗？

输入格式

第一行一个整数 $N$ ，表示员工的数量。

第二行 $N-1$ 个用空格隔开的正整数，依次为 f1,f2,…fN−1f_1, f_2, \dots f_{N-1}f1​,f2​,…fN−1​。

第三行一个整数 $Q$ ，表示共有 $Q$ 场合作需要安排。

接下来 $Q$ 行，每行描述一场合作：开头是一个整数 $m$（$2\le m\le N$），表示参与本次合作的员工数量；接着是 $m$ 个整数，依次表示参与本次合作的员工编号（保证编号合法且不重复）。

保证公司结构合法，即不存在任意一名员工，其本人是自己的直接或间接领导。

输出格式

输出 $Q$ 行，每行一个整数，依次为每场合作的主持人选。

样例输入 #1

5
0 0 2 2
3
2 3 4
3 2 3 4
2 1 4

样例输出 #1

2
2
0

样例输入 #2

7
0 1 0 2 1 2
5
2 4 6
2 4 5
3 4 5 6
4 2 4 5 6
2 3 4

样例输出 #2

2
1
1
1
0

说明/提示

样例解释 1

对于第一场合作，员工 $3,4$ 有共同领导 $2$ ，可以主持合作。

对于第二场合作，员工 $2$ 本人即可以管理所有参与者。

对于第三场合作，只有 $0$ 号老板才能管理所有员工。

数据范围

对于 $25\%$ 的测试点，保证 $N\le 50$。

对于 $50\%$ 的测试点，保证 $N\le 300$。

对于所有测试点，保证 3≤N≤1053 \leq N \leq 10^53≤N≤105，$Q\le 100$，m≤104m \leq 10^4m≤104。

2024/2/8 添加一组 hack 数据。