2025年3月 GESP C++ 8级

国家“以旧换新”政策仍在继续，小杨家决定在家里旧的冰箱、电视、洗衣机、微波炉中选两种换新。其中，冰箱有 $4$ 种型号可选，电视有 $6$ 种型号可选，洗衣机有 $3$ 种型号可选，微波炉有 $5$ 种型号可选。请问小杨家共有多少种换新的方案？（ ）。

小杨和 $3$ 位朋友约好一起去看电影“哪吒2”。打开购票软件，他们发现，已经没有同一排连续的四个座位了（图中每个方框代表一个座位，红色方框代表已经售出）。朋友们商量了一下，决定分为两组，每组两人在同一排的相邻两个座位，且两组之间至少有一对座位是前后相邻的。请问共有多少种购票方案？（ ）。

下面关于 C++ 类构造和析构函数的说法，错误的是（ ）。

下列关于树和图的说法，错误的是（ ）。

从 $1$ 到 $2025$ 这 $2025$ 个数中，包含数字 $5$ 的个数（ ）。

已定义 double 类型的变量 $r$ 和 $theta$，分别表示图中圆半径和圆心角。下列表达式中可以求出弦长 $s$ 的是（ ）。

$n$ 个节点的平衡二叉树的高为（ ）。

下列关于算法的说法，错误的是（ ）。

$9$ 是个神奇的数字，因为它是由两个数 $2$ 和 $3$ 拼接而成，而且 $2+3=5$，52=255^2 = 2552=25，$25$ 是 $9$ 的平方。小杨决定写个程序找找小于 $N$ 的正整数中共有多少这样神奇的数字。下面程序横线处应填入的是（ ）。

#include <string>
int count_miracle(int N) {
    int cnt = 0;
    for (int n = 1; n * n < N; n++) {
        int n2 = n * n;
        std::string s = std::to_string(n2);
        for (int i = 1; i < s.length(); i++)
            if (s[i] != '0') {
                std::string sl = s.substr(0, i);
                std::string sr = s.substr(i);
                int nl = std::stoi(sl);
                int nr = std::stoi(sr);
                if (_________) // 在此处填入选项
                    cnt++;
            }
    }
    return cnt;
}

n2n^2n2 是个神奇的数字，因为它是由两个数 $a$ 和 $b$ 拼接而成，而且 n2=a+bn^2 = a + bn2=a+b。小杨决定写个程序找找小于 $N$ 的正整数中共有多少这样神奇的数字。该函数的时间复杂度为（ ）。

#include <string>
int count_miracle(int N) {
    int cnt = 0;
    for (int n = 1; n * n < N; n++) {
        int n2 = n * n;
        std::string s = std::to_string(n2);
        for (int i = 1; i < s.length(); i++)
            if (s[i] != '0') {
                std::string sl = s.substr(0, i);
                std::string sr = s.substr(i);
                int nl = std::stoi(sl);
                int nr = std::stoi(sr);
                if (_________) // 在此处填入选项
                    cnt++;
            }
    }
    return cnt;
}

下面的欧氏筛法程序中，两个横线处应填入的分别是（ ）。

int primes[MAXP], num = 0;
bool isPrime[MAXN + 1] = {false};
void sieve() {
    for (int n = 2; n <= MAXN; n++) {
        if (!isPrime[n])
            primes[num++] = n;
        for (int i = 0; i < num && ________; i++) { // 在此处填入选项
            isPrime[n * primes[i]] = true;
            if (________) // 在此处填入选项
                break;
        }
    }
}

下面 Floyd 算法中，横线处应该填入的是（ ）。

#include <iostream>
using namespace std;
#define N 21
#define INF 99999999
int map[N][N];
int main() {
    int n, m, t1, t2, t3;
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (i == j)
                map[i][j] = 0;
            else
                map[i][j] = INF;
        }
    }
    for (int i = 1; i <= m; i++) {
        cin >> t1 >> t2 >> t3;
        map[t1][t2] = t3;
    }
    for (int k = 1; k <= n; k++)
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++)
                if (map[i][j] > map[i][k] + map[k][j])
                    ________; // 在此处填入选项
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            cout.width(4);
            cout << map[i][j];
        }
        cout << endl;
    }
}

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

#include <iostream>
using namespace std;
#define N 21
#define INF 99999999
int map[N][N];
int main() {
    int n, m, t1, t2, t3;
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (i == j)
                map[i][j] = 0;
            else
                map[i][j] = INF;
        }
    }
    for (int i = 1; i <= m; i++) {
        cin >> t1 >> t2 >> t3;
        map[t1][t2] = t3;
    }
    for (int k = 1; k <= n; k++)
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++)
                if (map[i][j] > map[i][k] + map[k][j])
                    ________; // 在此处填入选项
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            cout.width(4);
            cout << map[i][j];
        }
        cout << endl;
    }
}

下列程序实现了输出杨辉三角形，代码中横线部分应该填入的是（ ）。

#include <iostream>
using namespace std;
#define N 35
int a[N];
int main() {
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        a[i] = 1;
        for (int j = i - 1; j > 0; j--)
            ________; // 在此处填入选项
        for (int j = 0; j <= i; j++)
            cout << a[j] << " ";
        cout << endl;
    }
    return 0;
}

下列程序实现了输出杨辉三角形，其时间复杂度为（ ）。

#include <iostream>
using namespace std;
#define N 35
int a[N];
int main() {
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        a[i] = 1;
        for (int j = i - 1; j > 0; j--)
            ________; // 在此处填入选项
        for (int j = 0; j <= i; j++)
            cout << a[j] << " ";
        cout << endl;
    }
    return 0;
}

表达式 '5' - 3.0 的结果为 $2.0$，类型为 double。

在 C++ 语言中，如果想要在一个函数内调用一个类的私有方法，可以在该类中将该函数声明为友元函数。

插入排序一般是稳定的。

$5$ 个相同的红球和 $4$ 个相同的蓝球排成一排，要求蓝球不能相邻，则一共有 $15$ 种排列方案。

使用 math.h 或 cmath 头文件中的函数，表达式 pow(2, 5) 的结果类型为 int 、值为 $32$ 。

C++ 是一种面向对象编程语言，C 则不是。多态是面向对象三大特性之一，虚函数是动态多态的代表特性。 因此，使用 C 语言无法实现虚函数。

在 $n$ 个节点的平衡二叉树中查找指定元素的最差时间复杂度为 $O(\log n)$。

定义 int 类型的变量 $a$ 和 $b$ ，求二次函数取最小值时 $x$ 的值，可以通过表达式 -a / 2.0 求得。

判断无向图中是否有环，可以通过广度优先搜索实现。

从 $32$ 名学生中选出 $4$ 人分别担任班长、副班长、学习委员和组织委员，共有 种不同的选法。

试题名称：上学

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

题目描述

C 城可以视为由 $n$ 个结点与 $m$ 条边组成的无向图。 这些结点依次以 $1,2,\dots ,n$ 标号，边依次以 $1\le i\le m$ 连接边号为 uiu_iui​ 与 viv_ivi​ 的结点，长度为 lil_ili​ 米。

小 A 的学校坐落在 C 城的编号为 $s$ 的结点。小 A 的同学们共有 $q$ 位，他们想在保证不迟到的前提下，每天尽可能晚地出门上学。但同学们并不会计算从家需要多久才能到学校，于是找到了聪明的小 A。第 $i$ 位同学 ($1\le i\le q$) 告诉小 A，他的家位置于编号为 hih_ihi​ 的结点，并且他每秒钟能行走 1 米。请你帮小 A 计算，每位同学从家出发需要多少秒才能到达学校呢？

输入格式

第一行，四个正整数 $n,m,s,q$，分别表示 C 城的结点数与边数，学校所在的结点编号，以及小 A 同学们的数量。

接下来 $m$ 行，每行三个正整数 ui,vi,liu_i, v_i, l_iui​,vi​,li​，表示 C 城中的一条无向边。

接下来 $q$ 行，每行一个正整数 hih_ihi​，表示一位同学的情况。

输出格式

共 $q$ 行，对于每位同学，输出一个整数，表示从家出发到学校的最短时间。

样例输入 #1

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

样例输出 #1

4
3
1

说明/提示

本题采用捆绑测试。

对于 $20\%$ 的测试点，保证 $q=1$。

对于另外 $20\%$ 的测试点，保证 $1\le n\le 500$，$1\le m\le 500$。

对于所有测试点，保证 1≤n≤2×1051 \leq n \leq 2 \times 10^51≤n≤2×105，1≤m≤2×1051 \leq m \leq 2 \times 10^51≤m≤2×105，1≤q≤2×1051 \leq q \leq 2 \times 10^51≤q≤2×105，1≤ui,vi,s,hi≤n1 \leq u_i, v_i, s, h_i \leq n1≤ui​,vi​,s,hi​≤n，1≤li≤1061 \leq l_i \leq 10^61≤li​≤106。

试题名称：割裂

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

题目描述

小杨有一棵包含 $n$ 个节点的树，其中节点的编号从 $1$ 到 $n$。

小杨设置了 $a$ 个好点对 {⟨u1,v1⟩,⟨u2,v2⟩,…,⟨ua,va⟩}\{\langle u_1, v_1 \rangle, \langle u_2, v_2 \rangle, \dots, \langle u_a, v_a \rangle\}{⟨u1​,v1​⟩,⟨u2​,v2​⟩,…,⟨ua​,va​⟩} 和一个坏点对 ⟨bu,bv⟩\langle b_u, b_v \rangle⟨bu​,bv​⟩。一个节点能被删除，当且仅当：

• 删除该节点后对于所有的 $1\le i\le a$，好点对 uiu_iui​ 和 viv_ivi​ 仍然连通；
• 删除该节点后坏点对 bub_ubu​ 和 bvb_vbv​ 不连通。

如果点对中的任意一个节点被删除，其视为不连通。

小杨想知道，还有多少个节点能被删除。

输入格式

第一行包含两个非负整数 $n$, $a$，含义如下题面所示。

接下来 $n-1$ 行，每行包含两个正整数 xi,yix_i, y_ixi​,yi​，代表存在一条连接节点 xix_ixi​ 和 yiy_iyi​ 的边；

之后 $a$ 行，每行包含两个正整数 ui,viu_i, v_iui​,vi​，代表一个好点对 ⟨ui,vi⟩\langle u_i, v_i \rangle⟨ui​,vi​⟩；

最后一行包含两个正整数 bu,bvb_u, b_vbu​,bv​，代表坏点对 ⟨bu,bv⟩\langle b_u, b_v \rangle⟨bu​,bv​⟩。

输出格式

输出一个非负整数，代表删除的节点个数。

样例输入 #1

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

样例输出 #1

2

说明/提示

对于全部数据，保证有 1≤n≤1061 \leq n \leq 10^61≤n≤106, 0≤a≤1050 \leq a \leq 10^50≤a≤105, ui≠viu_i \neq v_iui​=vi​, bu≠bvb_u \neq b_vbu​=bv​。