2024年3月 GESP C++ 8级

为丰富食堂菜谱，炒菜部进行头脑风暴。肉类有鸡肉、牛肉、羊肉、猪肉 $4$ 种，切法有肉排、肉块、肉末 $3$ 种，配菜有圆白菜、油菜、豆腐 $3$ 种，辣度有麻辣、微辣、不辣 $3$ 种。不考虑口感的情况下，选 $1$ 种肉、$1$ 种切法、$1$ 种配菜、$1$ 种辣度产生一道菜（例如：麻辣牛肉片炒豆腐），这样能产生多少道菜？（ ）。

已知袋中有 $2$ 个相同的红球、$3$ 个相同的绿球、$5$ 个相同的黄球。每次取出一个不放回，全部取出。可能产生多少种序列？（ ）。

以下二维数组的初始化，哪个是符合语法的？（ ）。

下面有关 C++ 拷贝构造函数的说法，错误的是（ ）。

使用邻接表表达一个无向简单图，图中包含 $v$ 个顶点、$e$ 条边，则该表中边节点的个数为（ ）。

关于生成树的说法，错误的是（ ）。

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

在有 $n$ 个元素的二叉排序树中进行查找，其最好、最差时间复杂度分别为（ ）。

如下图所⽰，半径为 $r$ 、圆心角为 $t$ （弧度）的扇形，下面哪个表达式能够求出顶部阴影部分的面积？（ ）。

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

int fib(int n) {
    if (n <= 1)
        return 1;
    return fib(n - 1) + fib(n - 2);
}

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

int choose(int n, int m) {
    if (m == 0 || m == n)
        return 1;
    return choose(n - 1, m - 1) + choose(n - 1, m);
}

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

int primes[MAXP], num = 0;
bool isPrime[MAXN] = {false};
void sieve() {
    for (int n = 2; n <= MAXN; n++) {
        if (!isPrime[n])
            primes[num++] = n;
        for (int i = 0; i < num && n * primes[i] <= MAXN; i++) {
            isPrime[n * primes[i]] = true;
            if (n % primes[i] == 0)
                break;
        }
    }
}

下面程序的输出为（ ）。

#include <iostream>
using namespace std;
int a[10][10];
int main() {
    int m = 5, n = 4;
    for (int x = 0; x <= m; x++)
        a[x][0] = 1;
    for (int y = 1; y <= n; y++)
        a[0][y] = 1;
    for (int x = 1; x <= m; x++)
        for (int y = 1; y <= n; y++)
            a[x][y] = a[x - 1][y] + a[x][y - 1];
    cout << a[m][n] << endl;
    return 0;
}

下面程序的输出为（ ）。

#include <iostream>
using namespace std;
int main() {
    int cnt = 0;
    for (int x = 0; x <= 10; x++)
        for (int y = 0; y <= 10; y++)
            for (int z = 0; z <= 10; z++)
                if (x + y + z == 15)
                    cnt++;
    cout << cnt << endl;
    return 0;
}

下面的程序使用邻接矩阵表达的带权无向图，则从顶点 $0$ 到顶点 $3$ 的最短距离为（ ）。

int weight[4][4] = {
    { 0, 1, 7, 100},
    { 1, 0, 5, 15},
    { 7, 5, 0, 6},
    {100, 15, 6, 0}};

已知 int 类型的变量 $a$ 和 $b$，则执行语句 a, b = b, a; 后，变量 $a$ 和 $b$ 的值会互换。

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

孙子定理是求解一次同余方程组的方法，最早见于中国南北朝时期（公元5世纪）的数学著作《孙子算经》。又称中国余数定理，是中国数学史上的一项伟大成就。

$n$ 个顶点的无向完全图有 n(n−1)2\frac{n(n-1)}{2}2n(n−1)​ 条边。

为解决哈希函数冲突，在哈希表项内设置链表存储该项内的所有冲突元素，则该哈希表内查找元素的最差时间复杂度为 。

求一个包含 $v$ 个顶点、$e$ 条边的带权连通无向图的最小生成树，Prim 算法的时间复杂度为 。

已知 int 类型的变量 $a$ 、 $b$ 和 $c$ 中分别存储着一个三角形的三条边长，则这个三角形的面积可以通过表达式 (a+b+c)×(b+c−a)×(a+c−b)×(a+b−c)/4\sqrt{(a + b + c) \times (b + c - a) \times (a + c - b) \times (a + b - c)} / 4(a+b+c)×(b+c−a)×(a+c−b)×(a+b−c)​/4 求得。

可以使用深度优先搜索算法判断图的连通性。

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

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

试题名称：公倍数问题

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

题目描述

小 A 写了一个 $N\times M$ 的矩阵 $A$，我们看不到这个矩阵，但我们可以知道，其中第 $i$ 行第 $j$ 列的元素 Ai,jA_{i,j}Ai,j​ 是 $i$ 和 $j$ 的公倍数（$i=1,\dots ,N$，$j=1,\dots ,M$）。现在有 $K$ 个小朋友，其中第 $k$ 个小朋友想知道，矩阵 $A$ 中最多有多少个元素可以是 $k$（$k=1,2,\dots ,K$）。请你帮助这些小朋友求解。

注意：每位小朋友的答案互不相关，例如，有些位置既可能是 $x$，又可能是 $y$，则它同时可以满足 $x,y$ 两名小朋友的要求。

方便起见，你只需要输出 ∑k=1Kk×ansk\sum_{k=1}^{K}{k \times \texttt{ans}_k}∑k=1K​k×ansk​ 即可，其中 ansk\texttt{ans}_kansk​ 表示第 $k$ 名小朋友感兴趣的答案。

输入格式

第一行三个正整数 $N,M,K$。

输出格式

输出一行，即 ∑k=1Kk×ansk\sum_{k=1}^{K}{k \times \texttt{ans}_k}∑k=1K​k×ansk​。

请注意，这个数可能很大，使用 C++ 语言的选手请酌情使用 long long 等数据类型存储答案。

样例输入 #1

2 5 2

样例输出 #1

9

样例输入 #2

100 100 100

样例输出 #2

185233

说明/提示

样例 1 解释

只有 A1,1A_{1,1}A1,1​ 可以是 $1$，其余都不行。

A1,1,A1,2,A2,1,A2,2A_{1,1},A_{1,2},A_{2,1},A_{2,2}A1,1​,A1,2​,A2,1​,A2,2​ 都可以是 $2$，而其余不行。

因此答案是 $1\times 1+2\times 4=9$。

数据规模

对于 $30\%$ 的测试点，保证 $N,M,K\le 10$；

对于 $60\%$ 的测试点，保证 $N,M,K\le 500$；

对于 $100\%$ 的测试点，保证 N,M≤105N,M \leq 10^5N,M≤105，K≤106K \leq 10^6K≤106。

试题名称：接竹竿

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

题目描述

小杨同学想用卡牌玩一种叫做“接竹竿”的游戏。

游戏规则是：每张牌上有一个点数 $v$，将给定的牌依次放入一列牌的末端。若放入之前这列牌中已有与这张牌点数相同的牌，则小杨同学会将这张牌和点数相同的牌之间的所有牌全部取出队列（包括这两张牌本身）。

小杨同学现在有一个长度为 $n$ 的卡牌序列 $A$，其中每张牌的点数为 AiA_iAi​（$1\le i\le n$）。小杨同学有 $q$ 次询问。第 $i$ 次（$1\le i\le q$）询问时，小杨同学会给出 li,ril_i,r_ili​,ri​ 小杨同学想知道如果用下标在 [li,ri][l_i,r_i][li​,ri​] 的所有卡牌按照下标顺序玩“接竹竿”的游戏，最后队列中剩余的牌数。

输入格式

一行包含一个正整数 $T$，表示测试数据组数。

对于每组测试数据，第一行包含一个正整数 $n$，表示卡牌序列 $A$ 的长度。

第二行包含 $n$ 个正整数 A1,A2,…,AnA_1,A_2,\dots,A_nA1​,A2​,…,An​，表示卡牌的点数 $A$。

第三行包含一个正整数 $q$，表示询问次数。

接下来 $q$ 行，每行两个正整数 li,ril_i,r_ili​,ri​ 表示一组询问。

输出格式

对于每组数据，输出 $q$ 行。第 $i$ 行（$1\le i\le q$）输出一个非负整数，表示第 $i$ 次询问的答案。

样例输入 #1

1
6
1 2 2 3 1 3
4
1 3
1 6
1 5
5 6

样例输出 #1

1
1
0
2

说明/提示

样例解释

对于第一次询问，小杨同学会按照 $1,2,2$ 的顺序放置卡牌，在放置最后一张卡牌时，两张点数为 $2$ 的卡牌会被收走，因此最后队列中只剩余一张点数为 $1$ 的卡牌。

对于第二次询问，队列变化情况为：

$\{\}\to \{1\}\to \{1,2\}\to \{1,2,2\}\to \{1\}\to \{1,3\}\to \{1,3,1\}\to \{\}\to \{3\}$。因此最后队列中只剩余一张点数为 $3$ 的卡牌。

数据范围

对于全部数据，保证有 $1\le T\le 5$，1≤n≤1.5×1041\le n\le 1.5\times 10^41≤n≤1.5×104，1≤q≤1.5×1041\le q\le 1.5\times 10^41≤q≤1.5×104，1≤Ai≤131\le A_i\le 131≤Ai​≤13。