首页 › 题库 › GESP编程能力等级认证 › 1 计数原理

GESP-C++八级 题库

共 133 道题 ,第 6 / 7 页 · 按题型筛选,点「查看答案」核对解析
章节 1 计数原理 清除
101 判断题 偏易 GESP编程能力等级认证 ·GESP-C++八级 · 综合练习

使用 math.h 或 cmath 头文件中的余弦函数,表达式 cos(60) 的结果类型为 double 、值约为 0.5 。

A
对
B
错
答案与解析
正确答案:错

cos函数接受的角度参数是以弧度为单位的。因此,如果要用角度(如60度)作为参数,需要先将其转换为弧度。在C或C++中,可以使用M_PI(在math.h或cmath中定义)来表示π,从而将60度转换为弧度,即60 * M_PI / 180。

题目详情
102 判断题 偏易 GESP编程能力等级认证 ·GESP-C++八级 · 综合练习

诚实国公民只说实话,说谎国公民只说谎话。你来到一处分岔口,一条通往诚实国,一条通往说谎国,但不知是哪一条通往哪里。正在为难之际,走来两位路人,他们都自称是诚实国公民,都说对方是说谎国公民。你想去说谎国,可以这样问其中一位路人:“我要去说谎国,如果我去问另一个路人,他会指向哪一条路?”。

A
对
B
错
答案与解析
正确答案:对

说谎的人回答的是去诚实国的路,诚实的人回答的是去诚实国的路,故而分辨出来。

题目详情
103 判断题 偏易 GESP编程能力等级认证 ·GESP-C++八级 · 综合练习

ABCDE五个小朋友,排成一队跑步,其中AB两人必须排在一起,一共有48种排法。

A
对
B
错
答案与解析
正确答案:对

排列组合捆绑法。AB在一起,看成1个人,AB和BA共2中情况,所以是排队是:2*A(4,4)=48。

题目详情
104 判断题 偏易 GESP编程能力等级认证 ·GESP-C++八级 · 综合练习

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

A
对
B
错
答案与解析
正确答案:错

a和b是double类型,加减会造成精度的损失,导致2个变量值不能互换。

题目详情
105 判断题 偏易 GESP编程能力等级认证 ·GESP-C++八级 · 综合练习

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

A
对
B
错
答案与解析
正确答案:对
这道题暂未补解析。
题目详情
106 判断题 偏易 GESP编程能力等级认证 ·GESP-C++八级 · 综合练习

C++语言中,可以为同一个类定义多个析构函数。

A
对
B
错
答案与解析
正确答案:错

析构函数只能有1个。

题目详情
107 判断题 偏易 GESP编程能力等级认证 ·GESP-C++八级 · 综合练习

为解决哈希函数冲突,可以使用不同的哈希函数为每个表项各建立一个子哈希表,用来管理该表项的所有冲突元素。这些子哈希表一定不会发生冲突。

A
对
B
错
答案与解析
正确答案:错

子哈希表仍然可能产生冲突。

题目详情
108 判断题 偏易 GESP编程能力等级认证 ·GESP-C++八级 · 综合练习

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

A
对
B
错
答案与解析
正确答案:错
这道题暂未补解析。
题目详情
109 判断题 偏易 GESP编程能力等级认证 ·GESP-C++八级 · 综合练习

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

A
对
B
错
答案与解析
正确答案:错
这道题暂未补解析。
题目详情
110 判断题 偏易 GESP编程能力等级认证 ·GESP-C++八级 · 综合练习

N个顶点的无向完全图有N×(N-1)条边。(   )

A
对
B
错
答案与解析
正确答案:错
这道题暂未补解析。
题目详情
111 判断题 偏易 GESP编程能力等级认证 ·GESP-C++八级 · 综合练习

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

A
对
B
错
答案与解析
正确答案:对
这道题暂未补解析。
题目详情
112 判断题 偏易 GESP编程能力等级认证 ·GESP-C++八级 · 综合练习

给定 double 类型的变量 x ,且其值大于等于 ,我们可以通过二分法求出logx的近似值。(   )

A
对
B
错
答案与解析
正确答案:对
这道题暂未补解析。
题目详情
113 判断题 偏易 GESP编程能力等级认证 ·GESP-C++八级 · 综合练习

N个顶点的有向完全图(不带自环)有N×(N-1)/2条边。

A
对
B
错
答案与解析
正确答案:错
这道题暂未补解析。
题目详情
114 判断题 偏易 GESP编程能力等级认证 ·GESP-C++八级 · 综合练习

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

A
对
B
错
答案与解析
正确答案:对
这道题暂未补解析。
题目详情
115 判断题 偏易 GESP编程能力等级认证 ·GESP-C++八级 · 综合练习

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

A
对
B
错
答案与解析
正确答案:错
这道题暂未补解析。
题目详情
116 判断题 偏易 GESP编程能力等级认证 ·GESP-C++八级 · 综合练习

给定 double 类型的变量 x ,且其值大于等于 ,我们可以通过二分法求出的近似值。

A
对
B
错
答案与解析
正确答案:对
这道题暂未补解析。
题目详情
117 简答题 偏难 GESP编程能力等级认证 ·GESP-C++八级 · 综合练习

猫和老鼠

时间限制:1.0 s

内存限制:512.0 MB

题目描述

猫和老鼠所在的庄园可以视为一张由n个点和m条带权无向边构成的连通图。结点依次以1,2,...,n编号,结点i(1≤i≤n)有价值为ci的奶酪。在m条带权无向边中,第i(1≤i≤m)条无向边连接结点ui与结点vi,边权wi表示猫和老鼠通过这条边所需的时间。

猫窝位于结点a,老鼠洞位于结点b。对于老鼠而言,结点u是安全的当且仅当:

老鼠能规划一条从结点u出发逃往老鼠洞的路径,使得对于路径上任意结点x(包括结点u与老鼠洞)都有:

猫从猫窝出发到结点x的最短时间严格大于老鼠从结点u沿这条路径前往结点x所需的时间。

老鼠在拿取安全结点的奶酪时不存在被猫抓住的可能,但在拿取不是安全结点的奶酪时则不一定。为了确保万无一失,老鼠决定只拿取安全结点放置的奶酪。请你计算老鼠所能拿到的奶酪价值之和。

输入格式

第一行,两个正整数n,m,分别表示图的结点数与边数。

第二行,两个正整数a,b,分别表示猫窝的结点编号,以及老鼠洞的结点编号。

第三行,n个正整数c1,c2,...,cn,表示各个结点的奶酪价值。

接下来 行中的第i行(1≤x≤m)包含三个正整数ui,vi,wi,表示图中连接结点ui与结点vi的边,边权为wi。

输出格式

输出一行,一个整数,表示老鼠所能拿到的奶酪价值之和。

输入样例 1

5 5
1 2
1 2 4 8 16
1 2 4
2 3 3
3 4 1
2 5 2
3 1 8

输出样例 1

22

输入样例 2

6 10
3 4
1 1 1 1 1 1
1 2 6
2 3 3
3 1 4
3 4 5
4 5 8
5 6 2
6 4 1
3 2 4
5 4 4
3 3 6

输出样例 2

3

数据范围

对于40的测试点,保证1≤n≤500,1≤m≤500。

对于所有测试点,保证1≤n≤105,1≤m≤105,1≤a,b≤n且a≠b,1≤ui,vi≤n,1≤wi≤109。

答案与解析
参考答案
#include <cstdio>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;

const int N = 1e5 + 5;
const long long oo = 1e18;
int n, m;
int a, b;
int c[N];
vector<pair<int, int>> e[N];
long long dis[N];
priority_queue<pair<long long, int>> q;
long long ans;

int main() {
    scanf("%d%d", &n, &m);
    scanf("%d%d", &a, &b);
    for (int i = 1; i <= n; i++)
        scanf("%d", &c[i]);
    for (int i = 1; i <= m; i++) {
        int u, v, w;
        scanf("%d%d%d", &u, &v, &w);
        e[u].emplace_back(make_pair(v, w));
        e[v].emplace_back(make_pair(u, w));
    }
    for (int i = 1; i <= n; i++)
        dis[i] = oo;
    dis[b] = 0;
    q.push(make_pair(-dis[b], b));
    while (!q.empty()) {
        auto p = q.top();
        q.pop();
        if (dis[p.second] != -p.first)
            continue;
        int u = p.second;
        for (auto r : e[u]) {
            int v = r.first, w = r.second;
            if (dis[v] > dis[u] + w) {
                dis[v] = dis[u] + w;
                q.push(make_pair(-dis[v], v));
            }
        }
    }
    for (int i = 1; i <= n; i++)
        if (dis[i] < dis[a])
            ans += c[i];
    printf("%lld\n", ans);
    return 0;
}
题目详情
118 简答题 偏难 GESP编程能力等级认证 ·GESP-C++八级 · 综合练习

宝石项链

时间限制:1.0 s

内存限制:512.0 MB

题目描述

小 A 有一串包含n枚宝石的宝石项链,这些宝石按照在项链中的顺序依次以1,2,...,n编号,第n枚宝石与第1枚宝石相邻。项链由m种宝石组成,其中第i枚宝石种类为ti。

小 A 想将宝石项链分给他的好朋友们。具体而言,小 A 会将项链划分为若干连续段,并且需要保证每段都包含全部种宝石。请帮小 A 计算在满足条件的前提下,宝石项链最多可以划分为多少段。

输入格式

第一行,两个正整数n,m,分别表示宝石项链中的宝石的数量与种类数。

第二行,n个正整数ti,t2,...,tn,表示每枚宝石的种类。

输出格式

输出一行,一个整数,表示宝石项链最多可以划分的段数。

输入样例 1

6 2
1 2 1 2 1 2

输出样例 1

3

输入样例 2

7 3
3 1 3 1 2 1 2

输出样例 2

2

数据范围

答案与解析
参考答案
#include <cstdio>
#include <algorithm>
using namespace std;

const int L = 20;
const int N = 2e5 + 5;
const int oo = 1e9;
int n, m;
int t[N], jump[L][N];
int cnt[N], tot;
int ans;

int go(int u) {
    int cnt = 0, ans = 0;
    for (int i = L - 1; i >= 0; i--)
        if (cnt + jump[i][u] <= n) {
            cnt += jump[i][u];
            ans += 1 << i;
            u = (u + jump[i][u] - 1) % n + 1;
        }
    return ans;
}

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &t[i]);
        t[i + n] = t[i];
    }
    for (int i = 1, r = 0; i <= n; i++) {
        while (tot < m) {
            r++;
            if (!cnt[t[r]]++)
                tot++;
        }
        jump[0][i] = r - i + 1;
        if (!--cnt[t[i]])
            tot--;
    }
    for (int i = 1; i < L; i++)
        for (int j = 1; j <= n; j++) {
            int tar = (j + jump[i - 1][j] - 1) % n + 1;
            jump[i][j] = min(jump[i - 1][j] + jump[i - 1][tar], oo);
        }
    for (int i = 1; i <= n; i++)
        ans = max(ans, go(i));
    printf("%d\n", ans);
    return 0;
}
题目详情
119 简答题 偏难 GESP编程能力等级认证 ·GESP-C++八级 · 综合练习

最短距离

答案与解析
参考答案
#include <algorithm>
#include <cstdio>
using namespace std;

const int N = 100005;
int n, p, q;
int a, b;
int ans;

// 欧几里得求最大公约数
int gcd(int a, int b) {
    if (!a || !b) 
        return a + b;
    return gcd(b, a % b);
}

int main() {
    scanf("%d%d%d", &n, &p, &q);
    while (n--) {
        scanf("%d%d", &a, &b);
        if (a == b) {
            ans = 0;
        } else if (a == 1 || b == 1) {
            ans = p;
        } else {
            // 两种拆分方案:各自单独处理
            ans = min(p + p, q + q);
            if (gcd(a, b) == 1) {
                // 互质,可以合并处理花费p
                ans = min(ans, p);
            } else {
                // 不互质,合并处理花费q
                ans = min(ans, q);
            }
        }
        printf("%d\n", ans);
    }
    return 0;
}
题目详情
120 简答题 偏难 GESP编程能力等级认证 ·GESP-C++八级 · 综合练习

树上旅行

时间限制:1 s,内存限制:512 MB

【问题描述】

给定一棵有 n 个结点的有根树,结点依次以 1、2、……、n 编号,其中根结点的编号为 1。

小 A 计划在这棵有根树上进行 q 次旅行。在第 i 次旅行中,小 A 首先会选定结点 si 作为起点,并移动若干次。移动分为以下两种:

(1)移动至当前结点的父结点。特殊地,如果当前位于根结点,则不进行移动。

(2)移动至当前结点的所有子结点中编号最小的结点。特殊地,如果当前位于叶子结点,则不进行移动。

由于移动次数可能很大,对于第 i 次旅行,旅行中的移动将以 ki 个不为零的整数构成的序列 ai,1、ai,2、……、ai,k 表示。

对于 ai,j,若 ai,j > 0 则代表进行 ai,j 次第一种移动;若 ai,j < 0 则代表进行 ai,j 次第二种移动。根据给出的序列从左至右完成所有移动后,小 A 所在的结点即是旅行的终点。

给定每次旅行的起点与移动序列,请你求出旅行终点的结点编号。

【输入描述】

第一行,两个正整数 n、q,分别表示有根树的结点数量,以及旅行次数。

第二行,n -1 个整数 p2、p3、……、pn,其中 pi 表示结点 i 的父结点编号。

接下来 2q 行中的第 2i - 1行(1<=i<=q )包含两个正整数 si、ki,分别表示第 i 次旅行的起点编号,以及移动序列的长度。

第 2i 行包含 k 个整数 ai,1、ai,2、……、ai,k,表示移动序列。

【输出描述】

输出共 q 行,第 i 行包含一个整数,表示第 i 次旅行终点的结点编号。

【样例输入1】

5 4
1 1 2 2
3 3
1 -1 -1
2 5
1 -1 1 -1 1
5 8
1 1 1 -1 -1 -1 -1 -1
5 3
-1 -1 1

【样例输出1】

4
1
4
2

【样例输入2】

8 3
5 4 2 1 3 6 6
8 1
8
8 2
8 -8
8 3
8 -8 8

【样例输出2】

1
7
1

【数据范围】

对于所有测试点,保证 1 <= n <= 10^5,1 <= q <= 2×10^4,1 <= pi、si <= n,ki >= 1,且Σki <= 10^5,1<=|ai,j|<=n。

答案与解析
参考答案
#include <iostream>
using namespace std;
const int N = 1e5 + 5;
const int L = 18;
int n, q;
int h[N], nx[N];
int par[L][N], son[L][N];
void dfs(int u) {
    for (int i = 1; i < L; i++)
        par[i][u] = par[i - 1][par[i - 1][u]];
    son[0][u] = u;
    for (int i = h[u]; i; i = nx[i]) {
        dfs(i);
        if (son[0][u] == u || i < son[0][u])
            son[0][u] = i;
    }
    for (int i = 1; i < L; i++)
        son[i][u] = son[i - 1][son[i - 1][u]];
}
int move(int go[L][N], int u, int step) {
    for (int i = 0; i < L; i++)
        if ((step >> i) & 1)
            u = go[i][u];
    return u;
}
int main() {
    cin >> n >> q;
    for (int i = 2; i <= n; i++) {
        cin >> par[0][i];
        nx[i] = h[par[0][i]];
        h[par[0][i]] = i;
    }
    par[0][1] = 1;
    dfs(1);
    while (q--) {
        int s, k;
        cin >> s >> k;
        while (k--) {
            int a;
            cin >> a;
            if (a < 0)
                s = move(son, s, -a);
            else
                s = move(par, s, a);
        }
        cout << s << endl;
    }
    return 0;
}
题目详情