GESP 2025年C++三级编程题解析

2904 字

15 分钟

GESP 2025年C++三级编程题解析

2025/03/22

2025/09/30

GESP

/

GESP三级

/

CPP

202509-1 数组清零#

题目描述

小 A 有一个由 $n$ 个非负整数构成的数组 $a = [a_1, a_2, \ldots, a_n]$ 。他会对阵组 $a$ 重复进行以下操作，直到数组 $a$ 只包含 0。在一次操作中，小 A 会依次完成以下三个步骤：

在数组 $a$ 中找到最大的整数，记其下标为 $k$ 。如果有多个最大值，那么选择其中下标最大的。
从数组 $a$ 所有不为零的整数中找到最小的整数 $a_j$ 。
将第一步找出的 $a_k$ 减去 $a_j$ 。

例如，数组 $a = [2, 3, 4]$ 需要 7 次操作变成 $[0, 0, 0]$ ：

[2, 3, 4] \rightarrow [2, 3, 2] \rightarrow [2, 1, 2] \rightarrow [2, 1, 1] \rightarrow [1, 1, 1] \rightarrow [1, 1, 0] \rightarrow [1, 0, 0] \rightarrow [0, 0, 0]

小 A 想知道，对于给定的数组 $a$ ，需要多少次操作才能使得 $a$ 中的整数全部变成 0。可以证明， $a$ 中整数必然可以在有限次操作后全部变成 0。你能帮他计算出答案吗？

输入格式

第一行，一个正整数 $n$ ，表示数组 $a$ 的长度。

第二行， $n$ 个非负整数 $a_1, a_2, \ldots, a_n$ ，表示数组 $a$ 中的整数。

输出格式

一行，一个正整数，表示 $a$ 中整数全部变成 0 所需要的操作次数。

样例输入 1

3
2 3 4

样例输出 1

样例输入 2

5
1 3 2 2 5

样例输出 2

提示

对于所有测试点，保证 $1 \leq n \leq 100$ ， $0 \leq a_i \leq 100$ 。

代码解析

这道题题目不难，主要考察的是打擂台求最大值和最小值，判断数组全部为0可以换种思路，如果数组的最大值是0，那数组元素肯定全部都是0。

1
#include<bits/stdc++.h>
2
using namespace std;
3
int main() {
4

5
    int a[105], n;
6
    cin >> n;
7
    for (int i = 1; i <= n; i++)
8
        cin >> a[i];
9
    int cnt = 0;
10
    while (1) {
11
        int k = 1, aj = 999;
12
        for (int i = 1; i <= n; i++) {
13
            if (a[i] != 0) aj = min(aj, a[i]);
14
            // 这里使用 >= 保证有多个最大值选下标最大的
15
            if (a[i] >= a[k]) k = i;
16
        }
17
        // 如果最大值是 0 说明已经全都是 0 了
18
        if (a[k] == 0) break;
19
        a[k] -= aj;
20
        cnt++;
21
    }
22
    cout << cnt;
23

24
    return 0;
25
}

202509-2 日历制作#

题目描述

小 A 想制作 $2025$ 年每个月的日历。他希望你能编写一个程序，按照格式输出给定月份的日历。

具体来说，第一行需要输出 MON TUE WED THU FRI SAT SUN，分别表示星期一到星期日。接下来若干行中依次输出这个月所包含的日期，日期的个位需要和对应星期几的缩写最后一个字母对齐。例如， $2025$ 年 $9$ 月 $1$ 日是星期一，在输出九月的日历时， $1$ 号的个位 $1$ 就需要与星期一 MON 的最后一个字母 N 对齐。九月的日历输出效果如下:

MON TUE WED THU FRI SAT SUN
  1   2   3   4   5   6   7
  8   9  10  11  12  13  14
 15  16  17  18  19  20  21
 22  23  24  25  26  27  28
 29  30

你能帮助小 A 完成日历的制作吗?

输入格式

一行，一个正整数 $m$ ，表示需要按照格式输出 $2025$ 年 $m$ 月的日历。

输出格式

输出包含若干行，表示 $2025$ 年 $m$ 月的日历。

样例输入 1

样例输出 1

MON TUE WED THU FRI SAT SUN
  1   2   3   4   5   6   7
  8   9  10  11  12  13  14
 15  16  17  18  19  20  21
 22  23  24  25  26  27  28
 29  30

样例输入 2

样例输出 2

MON TUE WED THU FRI SAT SUN
                          1
  2   3   4   5   6   7   8
  9  10  11  12  13  14  15
 16  17  18  19  20  21  22
 23  24  25  26  27  28  29
 30

提示

对于所有测试点，保证 $1 \leq m \leq 12$ 。

代码解析

这道题目给出了 9 月 1 日是星期一，所以其他月的 1 号是星期几需要从 9 月开始往前或者往后去推，推出来这个月的 1 号是星期几之后剩下的就简单了。

1
#include<bits/stdc++.h>
2
using namespace std;
3
int main() {
4

5
    int m;
6
    int days[] = {0,31,28,31,30,31,30,31,31,30,31,30,31};
7
    cin >> m;
8

9
    int sum = 0;
10
    if (m >= 9) {
11
        // 往后推 1 号是周几
12
        for (int i = 9; i < m; i++) sum += days[i];
13
        sum = sum % 7;
14
    } else {
15
        // 往前推 1 号是周几
16
        for (int i = 8; i >= m; i--) sum += days[i];
17
        sum = 7 - sum % 7;
18
    }
19

20
    cout << "MON TUE WED THU FRI SAT SUN" << endl;
21
    // 输出前面的空格
22
    for (int i = 1; i <= sum; i++)
23
        cout << "    ";
24
    for (int i = 1; i <= days[m]; i++) {
25
        if (i < 10) cout << "  ";
26
        else cout << ' ';
27
        cout << i << ' ';
28
        // 换行需要考虑到前面空格的数量
29
        if ((i+sum) % 7 == 0) cout << endl;
30
    }
31

32
    return 0;
33
}

202506-1 奇偶校验#

题目描述

数据在传输过程中可能出错，因此接收方收到数据后通常会校验传输的数据是否正确，奇偶校验是经典的校验方式之一。

给定 $n$ 个非负整数 $c_1, c_2, \ldots, c_n$ 代表所传输的数据，它们的校验码取决于这些整数在二进制下 1 的数量之和的奇偶性。如果这些整数在二进制下共有奇数个 1，那么校验码为 1；否则校验码为 0。你能求出这些整数的校验码吗？

输入格式

第一行，一个正整数 $n$ ，表示所传输的数据量。

第二行， $n$ 个非负整数 $c_1, c_2, \ldots, c_n$ ，表示所传输的数据。

输出格式

输出一行，两个整数，以一个空格分隔：

第一个整数表示 $c_1, c_2, \ldots, c_n$ 在二进制下 1 的总数量；

第二个整数表示校验码（0 或 1）。

样例输入 1

4
71 69 83 80

样例输出 1

13 1

样例输入 2

6
1 2 4 8 16 32

样例输出 2

6 0

提示

对于所有测试点，保证 $1 \leq n \leq 100$ ， $0 \leq c_i \leq 255$ 。

代码解析

题目意思很好理解，需要统计 n 个数字中，每个数字的二进制中 1 的个数的和，并且判断 1 的个数是奇数还是偶数，使用二进制的数位剥离方法即可。

1
#include<bits/stdc++.h>
2
using namespace std;
3
int main() {
4

5
    int n, cnt = 0;
6
    cin >> n;
7
    while (n--) {
8
        int c;
9
        cin >> c;
10
        while (c) {
11
            cnt += c % 2;
12
            c /= 2;
13
        }
14
    }
15
    cout << cnt << ' ' << cnt % 2;
16

17
    return 0;
18
}

202506-2 分糖果#

题目描述

有 $n$ 位小朋友排成一队等待老师分糖果。第 $i$ 位小朋友想要至少 $a_i$ 颗糖果，并且分给他的糖果数量必须比分给前一位小朋友的糖果数量更多，不然他就会不开心。

老师想知道至少需要准备多少颗糖果才能让所有小朋友都开心。你能帮帮老师吗？

输入格式

第一行，一个正整数 $n$ ，表示小朋友的人数。

第二行， $n$ 个正整数 $a_1, a_2, \ldots, a_n$ ，依次表示每位小朋友至少需要的糖果数量。

输出格式

输出一行，一个整数，表示最少需要准备的糖果数量。

样例输入 1

4
1 4 3 3

样例输出 1

样例输入 2

15
314 15926 53589793 238462643 383279502 8 8 4 1 9 7 1 6 9 3

样例输出 2

4508143253

提示

对于所有测试点，保证 $1 \leq n \leq 1000$ ， $1 \leq a_i \leq 10^9$ 。

代码解析

我们需要分别计算每位同学需要多少糖果，如果 a[i] 大于前一位同学的糖果数量，则准备 a[i] 颗，否则需要比前一位同学 a[i-1] 多一颗

1
#include<bits/stdc++.h>
2
using namespace std;
3
int main() {
4

5
    long long n, cnt = 0, a[1005];
6
    cin >> n;
7
    a[0] = 0;  // 方便第一位同学a[1]比较
8
    for (int i = 1; i <= n; i++) {
9
        cin >> a[i];
10
        if (a[i] <= a[i-1])
11
            a[i] = a[i-1] + 1;
12
        cnt += a[i];
13
    }
14
  cout << cnt;
15

16
    return 0;
17
}

202503-1 2025#

题目描述

小 A 有一个整数 $x$ ，他想找到最小的正整数 $y$ 使得下式成立：

(x \ \operatorname{and} \ y) + (x \ \operatorname{or} \ y) = 2025

其中 $\operatorname{and}$ 表示二进制按位与运算， $\operatorname{or}$ 表示二进制按位或运算。如果不存在满足条件的 $y$ ，则输出 $-1$ 。

输入格式

一行，一个整数 $x$ 。

输出格式

一行，一个整数，若满足条件的 $y$ 存在则输出 $y$ ，否则输出 $-1$ 。

样例输入 1

样例输出 1

提示

对于所有测试点，保证 $0 \leq x < 2025$ 。

(x \ \operatorname{and} \ y) + (x \ \operatorname{or} \ y) = 2025

其中：

$\operatorname{and}$ 表示按位与运算，运算符为 $\&$ 。
$\operatorname{or}$ 表示按位或运算，运算符为 $|$ 。

代码解析

枚举法，从 1 开始枚举，找到符合条件的 i 直接结束主函数，若循环结束也没有找到则输出 -1

1
#include<bits/stdc++.h>
2
using namespace std;
3
int main() {
4

5
    int x;
6
    cin >> x;
7
    for (int i = 1; i <= 2025; i++)
8
        if ((x & i) + (x | i) == 2025) {
9
            cout << i;
10
            return 0;
11
        }
12
     cout << -1;
13

14
    return 0;
15
}

202503-2 词频统计#

题目描述

在文本处理中，统计单词出现的频率是一个常见的任务。现在，给定 $n$ 个单词，你需要找出其中出现次数最多的单词。在本题中，忽略单词中字母的大小写（即 Apple、apple、APPLE、aPPle 等均视为同一个单词）。

请你编写一个程序，输入 $n$ 个单词，输出其中出现次数最多的单词。

输入格式

第一行，一个整数 $n$ ，表示单词的个数；

接下来 $n$ 行，每行包含一个单词，单词由大小写英文字母组成。

输入保证，出现次数最多的单词只会有一个。

输出格式

输出一行，包含出现次数最多的单词（输出单词为小写形式）。

样例输入 1

6
Apple
banana
apple
Orange
banana
apple

样例输出 1

apple

提示

对于所有测试点， $1\leq n\leq 100$ ，每个单词的长度不超过 $30$ ，且仅由大小写字母组成。

代码解析

GESP 三级考点只有字符串以及数组，解这道题稍微麻烦一些。

解法 1：

在 words 数组中保存新的单词，在数组 a 中保存对应的单词出现的次数。

1
#include<bits/stdc++.h>
2
using namespace std;
3
int main() {
4

5
    string words[105];
6
    int a[105] = {0}, n, cnt = 0;
7
    cin >> n;
8
    while (n--) {
9
        string s;
10
        cin >> s;
11
        for (int i = 0; i < s.size(); i++)
12
            if ('A' <= s[i] && s[i] <= 'Z')
13
                s[i] += 'a'-'A';
14
    int i = 0;
15
        for (i = 0; i <= cnt; i++) {
16
            // 若在数组中找到了单词，则对应的次数 a[i] 加一
17
            if (words[i] == s) {
18
                a[i]++;
19
                break;
20
            }
21
        }
22
        // 若上面的 for 循环正常结束，则说明单词第一次出现，做好记录，cnt是单词数
23
        if (i > cnt) {
24
            words[cnt] = s;
25
            a[cnt]++;
26
            cnt++;
27
        }
28
    }
29
    int max = 0;
30
    for (int i = 1; i < cnt; i++)
31
        if (a[i] > a[max]) max = i;
32
    cout << words[max];
33

34
    return 0;
35
}

解法 2：

直接使用 words 字符串记录出现过的单词，每次使用 find() 在 words 中找是否记录过单词，words 中单词 s 首字母的位置可以直接作为桶标记的下标。

例：

words："apple banana orange"

a: {2, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 3, 0, 0 ..... } 表示 2 个 apple，1 个 banana，3 个 orange

1
#include<bits/stdc++.h>
2
using namespace std;
3
int main() {
4

5
    string words;
6
    int n, a[3005] = {0};
7
    cin >> n;
8
    while (n--) {
9
        string s;
10
        cin >> s;
11
        for (int i = 0; i < s.size(); i++)
12
            if ('A' <= s[i] && s[i] <= 'Z')
13
                s[i] += 'a'-'A';
14
    if (words.find(s) == -1)
15
            // 若单词不在 words 中，则拼接，加空格方便最后的输出
16
            words += s + ' ';
17
        else
18
            a[words.find(s)]++;
19
    }
20
    int max = 0;
21
    for (int i = 1; i < 3005; i++)
22
        if (a[i] > a[max]) max = i;
23
    // 输出的时候以空格来区分
24
     for (int i = max; words[i]!=' '; i++)
25
      cout << words[i];
26

27
    return 0;
28
}