首页 › 题库 › GESP编程能力等级认证 › GESP-C++六级

GESP-C++六级 题库

共 270 道题 ,第 13 / 14 页 · 按题型筛选,点「查看答案」核对解析
241 判断题 偏易 GESP编程能力等级认证 ·GESP-C++六级 · 4.1 一维动态规划

TCP/IP的传输层的两个不同的协议分别是UDP和TCP。(2023.9C++六级)

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

5G网络中,5G中的G表示Gigabytes/s,其中 1 GB = 1024 MB。(2023.9C++六级)

A
对
B
错
答案与解析
正确答案:错
这道题暂未补解析。
题目详情
243 判断题 偏易 GESP编程能力等级认证 ·GESP-C++六级 · 5.1 面向对象思想

在面向对象中,类是对象的实例。(2023.9C++六级)

A
对
B
错
答案与解析
正确答案:错
这道题暂未补解析。
题目详情
244 判断题 偏易 GESP编程能力等级认证 ·GESP-C++六级 · 5.1 面向对象思想

在C++类的定义中,使用 static 修饰符定义的静态成员被该类的所有对象共享。

A
对
B
错
答案与解析
正确答案:对
这道题暂未补解析。
题目详情
245 判断题 偏易 GESP编程能力等级认证 ·GESP-C++六级 · 5.1 面向对象思想

在C++类的定义中,可以定义初始化函数或运算符函数等。

A
对
B
错
答案与解析
正确答案:对
这道题暂未补解析。
题目详情
246 判断题 偏易 GESP编程能力等级认证 ·GESP-C++六级 · 3.1 深度优先搜索DFS

DFS 是深度优先算法的英文简写。

A
对
B
错
答案与解析
正确答案:对
这道题暂未补解析。
题目详情
247 判断题 偏易 GESP编程能力等级认证 ·GESP-C++六级 · 1.2 哈夫曼树

哈夫曼编码是一种有损压缩算法。(2023.9C++六级)

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

有些算法或数据结构在C/C++语言中使用指针实现,一个典型的例子就是链表。因此,链表这一数据结构在C/C++语言中只能使用指针来实现。

A
对
B
错
答案与解析
正确答案:错
这道题暂未补解析。
题目详情
249 判断题 偏易 GESP编程能力等级认证 ·GESP-C++六级 · 1.1 树的基本概念

如果节点数为 ,广度搜索算法的最差时间复杂度为O(N)。(2023.9C++六级)

A
对
B
错
答案与解析
正确答案:对
这道题暂未补解析。
题目详情
250 判断题 偏易 GESP编程能力等级认证 ·GESP-C++六级 · 1.1 树的基本概念

二叉搜索树的左右子树也是二叉搜索树。(2023.9C++六级)

A
对
B
错
答案与解析
正确答案:对
这道题暂未补解析。
题目详情
251 简答题 偏难 GESP编程能力等级认证 ·GESP-C++六级 · 1.1 树的基本概念

路径覆盖

题目描述

给定一棵有 n 个结点的有根树 T ,结点依次以 1,2, …, n 编号,根结点编号为1。初始时 T 中的结点均为白色。你需要将 T 中的若干个结点染为黑色,使得所有叶子到根的路径上至少有一个黑色结点。将结点 i 染为黑色需要代价 ci ,你需要在满足以上条件的情况下,最小化染色代价之和。 叶子是指 T 中没有子结点的结点。

输入格式

第一行,一个正整数 n ,表示结点数量。 第二行, n−1 个正整数 f2, f3, …, fn ,其中 fi 表示结点 i 的父结点的编号,保证 fi<i 第三行, n 个正整数 c1, c2, …, cn,其中 ci 表示将结点 i 染为黑色所需的代价。

输出格式

一行,一个整数,表示在满足所有叶子到根的路径上至少有一个黑色结点的前提下,染色代价之和的最小值。

样例

输入样例1

4
1 2 3
5 6 2 3

输出样例1

2

输入样例2

7
1 1 2 2 3 3
64 16 15 4 3 2 1

输出样例2

10

数据范围

对于 40% 的测试点,保证 2 ≤n ≤16

对于另外 20% 的测试点,保证 fi=i-1 对于所有测试点,保证 2 ≤n ≤10^5, 1 ≤ci ≤10^9

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

const int N = 1e5 + 5;
int n;
int f[N], c[N], cnt[N];
long long ans[N];
vector<int> son[N];

int main() {
    scanf("%d", &n);
    for (int i = 2; i <= n; i++) {
        scanf("%d", &f[i]);
        son[f[i]].push_back(i);
        cnt[f[i]]++;
    }

    for (int i = 1; i <= n; i++)
        scanf("%d", &c[i]);

    for (int i = n; i >= 1; i--) {
        ans[i] = c[i];
        long long sum = 0;
        for (int v : son[i]) {
            sum += ans[v];
        }
        ans[i] = min(ans[i], sum);
    }

    printf("%lld\n", ans[1]);
    return 0;
}
题目详情
252 简答题 偏难 GESP编程能力等级认证 ·GESP-C++六级 · 综合练习

道具商店

题目描述

道具商店里有 n 件道具可供挑选。第 i 件道具可为玩家提升ai点攻击力,需要 ci 枚金币才能购买,每件道具只能购买一次。现在你有 k 枚金币,请问你最多可以提升多少点攻击力?

输入格式

第一行,两个正整数 n k ,表示道具数量以及你所拥有的金币数量。 接下来 n 行,每行两个正整数ai , ci ,表示道具所提升的攻击力点数,以及购买所需的金币数量。

输出格式

输出一行,一个整数,表示最多可以提升的攻击力点数。

样例

输入样例1 

3 11 99 1 33 2 11 3

输出样例1 

132

输入样例2 

4 100 10 1 20 11 100 99 40 33

输出样例2 

110

数据范围

对于部分测试点,保证 1 ≤k ≤500, 1 ≤ ci  ≤500

对于所有测试点,保证 1 ≤n ≤500 , 1 ≤k ≤10^9 , 1 ≤ ai ≤500 , 1 ≤ ci  ≤10^9

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

const int N = 505;
const int oo = 1e9 + 10;
int n, k;
int f[N * N];

int main() {
    scanf("%d%d", &n, &k);
    for (int i = 1; i < N * N; i++)
        f[i] = oo;
    f[0] = 0;

    int s = 0;
    for (int i = 1; i <= n; i++) {
        int a, c;
        scanf("%d%d", &a, &c);
        s += a;
        for (int j = s; j >= a; j--)
            f[j] = min(f[j], f[j - a] + c);
    }

    int ans = 0;
    for (int i = 0; i < N * N; i++)
        if (f[i] <= k)
            ans = i;
    printf("%d\n", ans);
    return 0;
}
题目详情
253 简答题 偏难 GESP编程能力等级认证 ·GESP-C++六级 · 5.1 面向对象思想

划分字符串

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

const int N = 100005;
int n;
char s[N];
int a[N];
long long f[N];

int main() {
    scanf("%d", &n);
    scanf("%s", s + 1);  // 字符串下标从1开始
    for (int i = 1; i <= n; ++i) {
        scanf("%d", &a[i]);
    }

    // DP:f[i] = 前i个字符分割后的最大收益
    for (int i = 1; i <= n; ++i) {
        int mask = 0; // 位掩码,记录当前分段出现过的字符
        // j向左枚举分段起点,区间 [j, i]
        for (int j = i; j >= 1; --j) {
            int cur_bit = 1 << (s[j] - 'a');
            // 当前字符已在分段内,无法继续向左拓展
            if (mask & cur_bit) break;
            mask |= cur_bit;
            // 分段长度 len = i - j + 1
            int seg_len = i - j + 1;
            f[i] = max(f[i], f[j - 1] + a[seg_len]);
        }
    }

    printf("%lld\n", f[n]);
    return 0;
}
题目详情
254 简答题 偏难 GESP编程能力等级认证 ·GESP-C++六级 · 5.1 面向对象思想

货物运输

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

const int N = 100005;
int n;
vector<vector<pair<int, int>>> e;
long long total_sum, max_dist;

// u当前节点 fa父节点 d从起点1走到u的距离
void dfs(int u, int fa, long long d) {
    max_dist = max(d, max_dist);
    for (auto edge : e[u]) {
        int v = edge.first;
        int w = edge.second;
        if (v != fa) {
            dfs(v, u, d + w);
        }
    }
}

int main() {
    scanf("%d", &n);
    e.resize(n + 1);
    for (int i = 1; i < n; ++i) {
        int u, v, w;
        scanf("%d%d%d", &u, &v, &w);
        e[u].emplace_back(v, w);
        e[v].emplace_back(u, w);
        total_sum += w;
    }
    dfs(1, 0, 0);
    // 总往返路程 - 最长单条路径(不用折返)
    long long ans = total_sum * 2 - max_dist;
    printf("%lld\n", ans);
    return 0;
}
题目详情
255 简答题 偏难 GESP编程能力等级认证 ·GESP-C++六级 · 5.1 面向对象思想

学习小组

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

【问题描述】

班主任计划将班级里的 n 名同学划分为若干个学习小组,每名同学都需要分入某一个学习小组中。观察发现,如果一个学习小组中恰好包含 k 名同学,则该学习小组的讨论积极度为 ak。

给定讨论积极度 a1、a2、……、an,请你计算将这 n 名同学划分为学习小组的所有可能方案中,讨论积极度之和的最大值。

【输入描述】

第一行,一个正整数 n,表示班级人数。

第二行,n 个非负整数 a1、a2、……、an,表示不同人数学习小组的讨论积极度。

【输出描述】

输出共一行,一个整数,表示所有划分方案中,学习小组讨论积极度之和的最大值。

【样例输入1】

4
1 5 6 3

【样例输出1】

10

【样例输入2】

8
0 2 5 6 4 3 3 4

【样例输出2】

12

【数据范围】

对于40%测试点,保证 1 <= n <= 10。

对于所有测试点,保证 1 <= n <= 1000,0 <= ai <= 10000。

答案与解析
参考答案
#include <iostream>
using namespace std;
const int N = 1005;
int n, a[N];
int main() {
cin >> n;
    for (int i = 1; i <= n; i++) {
     cin >> a[i];
        for (int j = 1; j < i; j++)
            a[i] = max(a[i], a[j] + a[i - j]);
    }
    cout << a[n] << endl;
    return 0;
}
题目详情
256 简答题 偏难 GESP编程能力等级认证 ·GESP-C++六级 · 1.1 树的基本概念

最大因数

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

【问题描述】

给定一棵有 10^9 个结点的有根树,这些结点依次以 1、2、……、10^9编号,根结点的编号为 1。

对于编号为 k(2 <= k <= 10^9)的结点,其父结点的编号为 k 的因数中除 k 以外最大的因数。

现在有 q 组询问,第 i(1<= i  <= q)组询问给定 xi、yi,请你求出编号分别为 xi、yi 的两个结点在这棵树上的距离。

两个结点之间的距离是连接这两个结点的简单路径所包含的边数。

【输入描述】

第一行,一个正整数 q,表示询问组数。

接下来 q 行,每行两个正整数 xi、yi,表示询问结点的编号。

【输出描述】

输出共 q 行,每行一个整数,表示结点 xi、yi 之间的距离。

【样例输入1】

3
1 3
2 5
4 8

【样例输出1】

1
2
1

【样例输入2】

1
120 650

【样例输出2】

9

【数据范围】

对于60%的测试点,保证 1 <= xi、yi <= 1000。

对于所有测试点,保证 1 <= q <= 1000,1 <= xi、yi <= 10^9。

答案与解析
参考答案
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 50;
int a[N], cnta, b[N], cntb;
int f[N], t, q;
void factorize(int x, int a[], int &cnt) {
    a[0] = x;
    t = 0;
    for (int i = 2; i * i <= x; i++)
        while (x % i == 0) {
            f[++t] = i;
            x /= i;
        }
    if (x > 1)
        f[++t] = x;
    for (int i = 1; i <= t; i++)
        a[i] = a[i - 1] / f[i];
    cnt = t;
}
int main() {
    cin >> q;
    while (q--) {
        int x, y;
        cin >> x >> y;
        factorize(x, a, cnta);
        factorize(y, b, cntb);
        int px = 0, py = 0;
        while (a[px] != b[py]) {
            if (a[px] > b[py])
                px++;
            else
                py++;
        }
        cout << px + py << endl;
    }
    return 0;
}
题目详情
257 简答题 偏难 GESP编程能力等级认证 ·GESP-C++六级 · 1.1 树的基本概念

树上漫步

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

【问题描述】

小 A 有一棵 n 个结点的树,这些结点依次以 1、2、……、n标号。

小 A 想在这棵树上漫步。具体来说,小 A 会从树上的某个结点出发,每一步可以移动到与当前结点相邻的结点,并且小 A 只会在偶数步(可以是零步)后结束漫步。

现在小 A 想知道,对于树上的每个结点,从这个结点出发开始漫步,经过偶数步能结束漫步的结点有多少个(可以经过重复的节点)。

【输入描述】

第一行,一个正整数 n。

接下来 n - 1 行,每行两个整数 ui、vi,表示树上有一条连接结点 ui 和结点 vi 的边。

【输出描述】

一行, n 个整数,第 i 个整数表示从结点 i 出发开始漫步,能结束漫步的结点数量。

【样例输入1】

3
1 3
2 3

【样例输出1】

2 2 1

【样例输入2】

4
1 3
3 2
4 3

【样例输出2】

3 3 1 3

【数据范围】

对于 20% 的测试点,保证 1<=n<=1000。

对于所有测试点,保证 1<=n<=200000。

答案与解析
参考答案
#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 2e5 + 5;
const int E = N << 1;
int n;
int h[N], to[E], nx[E], et;
int cnt[N], bel[N];
void ae(int u, int v) {
    et++;
    to[et] = v;
    nx[et] = h[u];
    h[u] = et;
}
void dfs(int u, int c, int f) {
    bel[u] = c;
    cnt[c]++;
    for (int i = h[u]; i; i = nx[i])
        if (to[i] != f)
            dfs(to[i], c ^ 1, u);
}
int main() {
    scanf("%d", &n);
    for (int i = 1; i < n; i++) {
        int u, v;
        scanf("%d%d", &u, &v);
        ae(u, v);
        ae(v, u);
    }
    dfs(1, 0, 0);
    for (int i = 1; i <= n; i++)
        printf("%d%c", cnt[bel[i]], " \n"[i == n]);
    return 0;
}
题目详情
258 简答题 偏难 GESP编程能力等级认证 ·GESP-C++六级 · 5.1 面向对象思想

环线

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

【问题描述】

小 A 喜欢坐地铁。地铁环线有 n 个车站,依次以 1、2、……、n标号。车站 i(1<=i<n )的下一个车站是车站 i+1。

特殊地,车站 n 的下一个车站是车站 1。

小 A 会从某个车站出发,乘坐地铁环线到某个车站结束行程,这意味着小 A 至少会经过一个车站。小 A 不会经过一个车站多次。

当小 A 乘坐地铁环线经过车站 i 时,小 A 会获得 ai 点快乐值。请你安排小 A 的行程,选择出发车站与结束车站,使得获得的快乐值总和最大。

【输入描述】

第一行,一个正整数 n,表示车站的数量。

第二行, n 个整数 a1、a2、……、an,分别表示经过每个车站时获得的快乐值。

【输出描述】

一行,一个整数,表示小 A 能获得的最大快乐值。

【样例输入1】

4
-1 2 3 0

【样例输出1】

5

【样例输入2】

5
-3 4 -5 1 3

【样例输出2】

5

【数据范围】

对于 20% 的测试点,保证 1<=n<=200。

对于 40% 的测试点,保证 1<=n<=2000。

对于所有测试点,保证 1<=n<=200000, -10^9<=ai<=10^9。

正确答案: 暂无(答题 0次,答对 0次,正确率:0%)

答案与解析
参考答案
#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 4e5 + 5;
int n;
long long a[N], pre[N];
int q[N], ql, qr;
long long ans;
int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%lld", &a[i]);
        a[n + i] = a[i];
    }
    for (int i = 1; i <= 2 * n; i++)
        pre[i] = pre[i - 1] + a[i];
    ql = qr = 1;
    ans = -1e18;
    for (int i = 1; i <= 2 * n; i++) {
        while (ql <= qr && q[ql] < i - n)
            ql++;
        ans = max(ans, pre[i] - pre[q[ql]]);
        while (ql <= qr && pre[i] < pre[q[qr]])
            qr--;
        q[++qr] = i;
    }
    printf("%lld\n", ans);
    return 0;
}
题目详情
259 简答题 偏难 GESP编程能力等级认证 ·GESP-C++六级 · 1.1 树的基本概念

树上游走

时间限制:1.0 s

内存限制:512.0 MB

题面描述

小杨有一棵包含无穷节点的二叉树(即每个节点都有左儿子节点和右儿子节点;除根节点外,每个节点都有父节点),其中根节点的编号为 1,对于节点 i ,其左儿子的编号为 2×i,右儿子的编号为 2×i+1。

小杨会从节点 s 开始在二叉树上移动,每次移动为以下三种移动方式的任意一种:

第1种移动方式: 如果当前节点存在父亲节点,向上移动到当前节点的父亲节点,否则不移动;

第2种移动方式: 移动到当前节点的左儿子;

第3种移动方式: 移动到当前节点的右儿子。

小杨想知道移动 n 次后自己所处的节点编号。数据保证最后的所处的节点编号不超过 1012。

输入格式

第一行包含一个正整数 n,s,代表移动次数和初始节点编号。

第二行包含一个长度为 n 且仅包含大写字母 U,L,R 的字符串,代表每次移动的方式,其中 U 代表第1种移动方式,L 代表第2种移动方式,R代表第3种移动方式。

输出格式

输出一个正整数,代表最后所处的节点编号。

输入样例

3 2
URR

输出样例

7

样例解释

小杨的移动路线为 2-1-3-7。

对于全部数据,保证有 1≤n≤106,1≤s≤1012。

答案与解析
参考答案
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const ll INF = 1e12;
int n;
stack<char> st;
string c;
ll s;
int main(){
	cin >> n >> s >> c;
	for(int i = 0; i < n; i ++){
		if(c[i] == 'U'){
			if(s == 1) continue;
			if(st.size()){
				st.pop();
				continue;
			}
			s >>= 1;
		}else if(c[i] == 'L'){
			if((s << 1) > INF){
				st.push('L');
				continue;
			}
			s = s << 1;
		}else{
			if((s << 1 | 1) > INF){
				st.push('R');
				continue;
			}
			s = s << 1 | 1;
		}
	}
	cout << s << "\n";
	return 0;
}
题目详情
260 简答题 偏难 GESP编程能力等级认证 ·GESP-C++六级 · 5.1 面向对象思想

运送物资

时间限制:1.0 s

内存限制:512.0 MB

题面描述

小杨管理着 m 辆货车,每辆货车每天需要向 A 市和 B 市运送若干次物资。小杨同时拥有 n 个运输站点,这些站点位于 A 市和 B 市之间。

每次运送物资时,货车从初始运输站点出发,前往 A 市或 B 市,之后返回初始运输站点。A 市、B 市和运输站点的位置可以视作数轴上的三个点,其中 A 市的坐标为 0,B 市的坐标为 x ,运输站点的坐标为 p 且有 0<p<x,货车每次去 A 市运送物资的总行驶路程为 2p,去 B 市运送物资的总行驶路程为 2(x−p)。

对于第 i 个运输站点,其位置为 pi且至多作为 ci辆车的初始运输站点。小杨想知道,在最优分配每辆货车的初始运输站点的情况下,所有货车每天的最短总行驶路程是多少。

输入格式

第一行包含三个正整数 n,m,x,代表运输站点数量,货车数量和两市距离。

之后 n 行,每行包含两个正整数 pi,ci,代表第 i 个运输站点的位置和最多容纳车辆数。

之后 m 行,每行包含两个正整数 ai,bi,代表第 i 辆货车每天需要向 A 市运送 ai次物资,向 B 市运送 bi次物资。

输出格式

输出一个正整数,代表所有货车每天的最短总行驶路程。


输入样例

3 4 10
1 1
2 1
8 3
5 3
7 2
9 0
1 10000

输出样例

40186

样例解释

第 1 辆车的初始运输站点为站点 3,第 2 辆车的初始运输站点为站点 2。第 3 辆车的初始运输站点为站点 1,第 4 辆车的初始运输站点为站点 3。此时总行驶路程最短,为 40186。

对于全部数据,保证有 1≤n,m≤105,2≤x≤108,0<pi<x,1≤ci≤105,0≤ai,bi≤105。数据保证∑ci≥m。

答案与解析
参考答案
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 1e5+10;
int n,m;
ll x;
vector<pair<int,int> > st;
int a[N],b[N];
int main(){
	cin>>n>>m>>x;
	for(int i=1;i<=n;i++){
		int p,c;
		cin>>p>>c;
		st.push_back(make_pair(p,c));
	}
	sort(st.begin(),st.end());
	for(int i=1;i<=m;i++){
		cin>>a[i]>>b[i];
	}
	vector<pair<int,int> > neg,pos;
	ll res=0;
	for(int i=1;i<=m;i++){
		if(a[i]>=b[i])
			pos.push_back(make_pair(a[i]-b[i],i));
		else{
			neg.push_back(make_pair(a[i]-b[i],i));
		}
		res+=1ll*b[i]*x;
	}
	sort(neg.begin(),neg.end());
	sort(pos.begin(),pos.end());
	reverse(pos.begin(),pos.end());
	int l=0,r=n-1;
	for(auto i:neg){
		while(r>=1&&st[r].second==0)r--;
		res+=1ll*(a[i.second]-b[i.second])*st[r].first;
		st[r].second-=1;
	}
	for(auto i:pos){
		while(l<=n&&st[l].second==0)l++;
		res+=1ll*(a[i.second]-b[i.second])*st[l].first;
		st[l].second-=1;
	}
	cout<<res*2<<"\n";
}
题目详情