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

202412-1 数字替换#

题目描述

小杨有一个包含 $n$ 个数字的序列 $A$ ，即 $A=[a_1,a_2,\ldots,a_n]$ ，他想将其中大于 $k$ 的数字都替换为序列的最大值，将其中小于 $k$ 的数字都替换为序列的最小值，请你帮他计算出替换后的序列。

输入格式

第一行包含两个正整数 $n,k$ ，含义如题面所示。

第二行包含 $n$ 个数字，代表序列 $A$ 。

输出格式

输出 $n$ 个整数，代表替换后的结果。

样例输入 1

5 0
-2 -1 0 1 2

样例输出 1

-2 -2 0 2 2

提示

对于全部数据，保证有 $1\le n\le 10^5$ ， $|k|,|a_i|\le 10^5$ 。

代码解析

这是一道结合数组的，简单的打擂台求最值问题，我们先输入第一个数字，将其作为最大和最小值的初始值，接下来输入剩余的第 2~n 个数字，同时进行比大小得出最大和最小值，最后遍历数组，根据题目条件选择合适的输出。

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

5
    int a[100005];
6
    int n, k;
7
    cin >> n >> k;
8
    cin >> a[1];
9
    int max_n = a[1], min_n = a[1];
10
    for (int i = 2; i <= n; i++) {
11
        cin >> a[i];
12
        max_n = max(max_n, a[i]);
13
        min_n = min(min_n, a[i]);
14
    }
15
    for (int i = 1; i <= n; i++)
16
        if (a[i] < k) cout << min_n << ' ';
17
      else if (a[i] > k) cout << max_n << ' ';
18
      else cout << a[i] << ' ';
19

20
    return 0;
21
}

202412-2 打印数字#

题目描述

小杨为数字 $0,1,2$ 和 $3$ 设计了一款表示形式，每个数字占用了 $5\times 5$ 的网格。数字 $0,1,2$ 和 $3$ 的表示形式如下：

1
..... ****. ..... .....
2
.***. ****. ****. ****.
3
.***. ****. ..... .....
4
.***. ****. .**** ****.
5
..... ****. ..... .....

小杨想请你将给定的数字 $n$ 转换为对应的表示形式。

输入格式

第一行包含一个正整数代表 $n$ 。

输出格式

输出对应的表示形式。

样例输入 1

样例输出 1

****.....................
****.****.****.****..***.
****.................***.
****..****.********..***.
****.....................

提示

对于全部数据，保证有 $0\le n\le 10^6$ ，且 $n$ 仅由数字 $0,1,2,3$ 组成。

代码解析

这道题相对来说较复杂，可以先将四个数字的五行字符串保存在字符串数组中，输出的时候注意，是每行分别输出每个数字的一行，注意循环的写法。

1
#include<iostream>
2
using namespace std;
3
int main() {
4

5
  string a0[] = {".....", ".***.", ".***.", ".***.", "....."};
6
  string a1[] = {"****.", "****.", "****.", "****.", "****."};
7
  string a2[] = {".....", "****.", ".....", ".****", "....."};
8
  string a3[] = {".....", "****.", ".....", "****.", "....."};
9

10
    string s;
11
    cin >> s;
12
    for (int i = 0; i < 5; i++) {
13
        for (int j = 0; j < s.size(); j++) {
14
            int num = s[j] - '0';
15
            if (num == 0) cout << a0[i];
16
            else if (num == 1) cout << a1[i];
17
            else if (num == 2) cout << a2[i];
18
            else if (num == 3) cout << a3[i];
19
        }
20
        cout << endl;
21
    }
22

23
    return 0;
24
}

已经掌握二维数组的同学可以用更简单的写法

1
#include<iostream>
2
using namespace std;
3
int main() {
4

5
    string n[4][5] = {
6
        {".....", ".***.", ".***.", ".***.", "....."},
7
        {"****.", "****.", "****.", "****.", "****."},
8
        {".....", "****.", ".....", ".****", "....."},
9
        {".....", "****.", ".....", "****.", "....."}
10
        };
11

12
    string s;
13
    cin >> s;
14
    for (int i = 0; i < 5; i++) {
15
        for (int j = 0; j < s.size(); j++) {
16
            int num = s[j] - '0';
17
            cout << n[num][i];
18
        }
19
        cout << endl;
20
    }
21

22
    return 0;
23
}

202409-1 平衡序列#

题目描述

小杨有一个包含 $n$ 个正整数的序列 $a$ 。他认为一个序列是平衡的当且仅当存在一个正整数 $i$ （ $1 \leq i < n$ ）使得序列第 $1$ 到第 $i$ 个数字的总和等于第 $i + 1$ 到第 $n$ 个数字的总和。

小杨想请你判断序列 $a$ 是否是平衡的。

输入格式

本题单个测试点内包含多组测试数据。第一行是一个正整数 $t$ ，表示测试用例组数。

接下来是 $t$ 组测试用例。对每组测试用例，一共两行。

第一行包含一个正整数 $n$ ，表示序列长度。第二行包含 $n$ 个正整数，代表序列 $a$ 。

输出格式

对每组测试用例输出一行一个字符串。如果 $a$ 是平衡的，输出 $\texttt{Yes}$ ，否则输出 $\texttt{No}$ 。

样例输入 1

样例输出 1

Yes
Yes
No

提示

【样例 1 解释】

对第一组测试用例，令 $i = 2$ ，有 $i + 2 = 3$ ，因此序列是平衡的。
对第二组测试用例，令 $i = 2$ ，有 $2 + 3 = 1 + 4$ ，因此序列是平衡的。
对第三组测试用例，不存在满足要求的 $i$ 。

【数据规模与约定】

对全部的测试数据，保证 $1 \leq t \leq 100$ ， $1 \leq n, a_i \leq 10000$ 。

代码解析

达到平衡序列的条件是把一个数组分成两半，左半部分的和和右半部分的和相等，这道题使用枚举法，枚举的 i 表示我们从哪里将数组分开，分别求 a[1] ~ a[i] 与 a[i+1] ~ a[n] 的和，判断是否相等即可，使用 flag 进行标记。

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

5
    int t, a[10005];
6
    cin >> t;
7
    while(t--) {
8
        int n;
9
        cin >> n;
10
        for (int i = 1; i <= n; i++)
11
            cin >> a[i];
12
        bool flag = false;
13
        for (int i = 1; i < n; i++) {
14
            int sum1 = 0, sum2 = 0;
15
            // 计算左半部分的和
16
            for (int j = 1; j <= i; j++)
17
                sum1 += a[j];
18
            // 计算右半部分的和
19
            for (int j = i+1; j <= n; j++)
20
                sum2 += a[j];
21
            if (sum1 == sum2) {
22
                flag = true;
23
                break;
24
            }
25
        }
26
        if (flag) cout << "Yes" << endl;
27
        else cout << "No" << endl;
28
    }
29

30
    return 0;
31
}

202409-2 回文拼接#

题目描述

一个字符串是回文串，当且仅当该字符串从前往后读和从后往前读是一样的，例如， $\texttt{aabaa}$ 和 $\texttt{ccddcc}$ 都是回文串，但 $\texttt{abcd}$ 不是。

小杨有 $n$ 个仅包含小写字母的字符串，他想请你编写程序判断每个字符串是否由两个长度至少为 $2$ 的回文串前后拼接而成。

输入格式

第一行包含一个正整数 $n$ ，代表字符串数量。接下来 $n$ 行，每行一个仅包含小写字母的字符串。

输出格式

对于每个字符串输出一行，如果该字符串由两个长度至少为 $2$ 的回文串前后拼接而成则输出 Yes，否则输出 No。

样例输入 1

4
abcd
aabbb
aaac
abcdd

样例输出 1

No
Yes
No
No

提示

【样例 1 解释】

对于第 $1,3,4$ 个字符串，都不是由两个长度至少为 $2$ 的回文串前后拼接而成。第 $2$ 个字符串由回文串 $\texttt{aa}$ 和 $\texttt{bbb}$ 前后拼接而成，并且两个回文串长度都至少为 $2$ 。

【数据规模与约定】

对全部的测试数据，保证 $1 \leq n \leq 10$ ，且每个字符串的长度均不超过 $100$ 。

代码解析

和上道题一样的思路，我们枚举切开的位置，判断切开之后左边部分和右半部分是不是均为回文字符串，多了一个条件，如果切开之后字符串长度小于 2 则不满足。

从 i 切开，前半部分就是 s.substr(0, i) 后半部分是 s.substr(i) 。

1
#include<bits/stdc++.h>
2
using namespace std;
3

4
bool hui(string s) {
5
    // 两个回文串长度都至少为 2
6
    if (s.size() < 2) return false;
7
    string s1;
8
    for (int i = 0; i < s.size(); i++)
9
        s1 = s[i] + s1;
10
     return s == s1;
11
}
12

13
int main() {
14

15
    int n;
16
    cin >> n;
17
    while (n--) {
18
        string s;
19
        cin >> s;
20
        bool flag = false;
21
        for (int i = 1; i < s.size(); i++) {
22
            if (hui(s.substr(0, i)) && hui(s.substr(i))) {
23
                flag = true;
24
                break;
25
            }
26
        }
27
        if (flag) cout << "Yes" << endl;
28
        else cout << "No" << endl;
29
    }
30

31
    return 0;
32
}

202406-1 移位#

题目描述

小杨学习了加密技术移位，所有大写字母都向后按照⼀个固定数目进行偏移。偏移过程会将字母表视作首尾相接的环，例如，当偏移量是 $3$ 的时候，大写字母 A 会替换成 D，大写字母 Z 会替换成 C，总体来看，大写字母表 ABCDEFGHIJKLMNOPQRSTUVWXYZ 会被替换成 DEFGHIJKLMNOPQRSTUVWXYZABC。

注：当偏移量是 $26$ 的倍数时，每个大写字母经过偏移后会恰好回到原来的位置，即大写字母表 ABCDEFGHIJKLMNOPQRSTUVWXYZ 经过偏移后会保持不变。

输入格式

第一行包含一个正整数 $n$ 。

输出格式

输出在偏移量为 $n$ 的情况下，大写字母表 ABCDEFGHIJKLMNOPQRSTUVWXYZ 移位替换后的结果。

样例输入 1

样例输出 1

DEFGHIJKLMNOPQRSTUVWXYZABC

提示

【样例解释】

当偏移量是 $3$ 的时候，大写字母 A 会替换成 D，大写字母 Z 会替换成 C，总体来看，大写字母表 ABCDEFGHIJKLMNOPQRSTUVWXYZ 会被替换成 DEFGHIJKLMNOPQRSTUVWXYZABC。

【数据范围】

对于全部数据，保证有 $1\leq n\leq 100$ 。

代码解析

0 ~ 25 这组数字加 ‘A’ 就能构建一个大写字母表，所以我们先将 0 ~ 25 的数字进行偏移处理，先 +n，再取余26 即可得到偏移后的数字，再将数字 +‘A’，拼接到字符串 s 即可。

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

5
    int n;
6
    string s;
7
    cin >> n;
8
    for (int i = 0; i < 26; i++) {
9
        s += (i+n)%26 + 'A';
10
    }
11
    cout << s;
12

13
    return 0;
14
}

202406-2 寻找倍数#

题目描述

小杨有一个包含 $n$ 个正整数的序列 $A=[a_1,a_2,\dots,a_n]$ ，他想知道是否存在 $i(1\leq i\leq n)$ 使得 $a_i$ 是序列 $A$ 中所有数的倍数。

输入格式

第一行包含一个正整数 $t$ ，代表测试用例组数。

接下来是 $t$ 组测试用例。对于每组测试用例，一共两行。

其中，第一行包含一个正整数 $n$ ；第二行包含 $n$ 个正整数，代表序列 $A$ 。

输出格式

对于每组测试用例，如果存在 $i(1\leq i\leq n)$ ，满足对于所有 $k(1\leq k\leq n)$ $a_i$ 是 $a_k$ 的倍数，输出 Yes，否则输出 No。

样例输入 1

样例输出 1

Yes
No

提示

【样例解释】

对于第⼀组数据，对于 $a_3=4$ ，满足 $a_3$ 是 $a_1$ 和 $a_2$ 的倍数。

【数据范围】

对于全部数据，保证有 $1\leq t\leq 10$ ， $1\leq n\leq 10^5$ ， $1\leq a_i\leq 10^9$ 。

代码解析

如果有满足条件的数字存在，那么这个数字必然是所有数字中最大的那个数字，所以只需要先找出这组数字中最大的那个，再去试除看能否整除所有数字，使用 flag 做标记。

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

5
    int t, n, a[100005], max_n;
6
    cin >> t;
7
    while (t--) {
8
        cin >> n;
9
        max_n = 0;
10
        for (int i = 0; i < n; i++) {
11
            cin >> a[i];
12
            max_n = max(max_n, a[i]);
13
        }
14
        bool flag = true;
15
        for (int i = 0; i < n; i++) {
16
            if (max_n % a[i] != 0) {
17
                flag = false;
18
                break;
19
            }
20
        }
21
        if (flag) cout << "Yes" << endl;
22
        else cout << "No" << endl;
23
    }
24

25
    return 0;
26
}

202403-1 字母求和#

题目描述

小杨同学发明了一种新型密码，对于每一个小写英文字母，该小写字母代表了一个正整数，即该字母在字母顺序中的位置，例如字母 a 代表了正整数 $1$ ，字母 b 代表了正整数 $2$ ；对于每一个大写英文字母，该大写字母代表了一个负整数，即该字母的 ASCII 码的相反数，例如字母 A 代表了负整数 $-65$ 。小杨同学利用这种放缩对一个整数进行了加密并得到了一个由大写字母和小写字母组成的字符串，该字符串中每个字母所代表数字的总和即为加密前的整数，例如 aAc 对应的加密前的整数为 $1+(-65)+3=-61$ 。

对于给定的字符串，请你计算出它对应的加密前的整数是多少。

输入格式

第一行一个正整数 $n$ ，表示字符串中字母的个数。第二行一个由大写字母和小写字母的字符串 T，代表加密后得到的字符串。

输出格式

输出一行一个整数，代表加密前的整数。

样例输入 1

3
aAc

样例输出 1

-61

提示

对全部的测试数据，保证 $1 \leq n \leq 10^5$ 。

代码解析

小写字母在字母表中的顺序，假设字符 c = 'a'，只需要 c-'a'+1 可得 1

1
#include<bits/stdc++.h>
2
using namespace std;
3
int main() {
4
    int n, sum = 0;
5
  string s;
6
    cin >> n >> s;
7
    for (int i = 0; i < n; i++) {
8
        if (s[i] >= 'a' && s[i] <= 'z')
9
            sum += s[i] - 'a' + 1;
10
        else
11
            sum -= s[i];
12
    }
13
    cout << sum;
14
    return 0;
15
}

202403-2 完全平方数#

题目描述

小杨同学有一个包含 $n$ 个非负整数的序列 $A$ ，他想要知道其中有多少对下标组合 $<i,j>$ （ $1 \leq i < j \leq n$ ），使得 $A_i + A_j$ 是完全平方数。

如果 $x$ 是完全平方数，则存在非负整数 $y$ 使得 $y \times y = x$ 。

输入格式

第一行一个非负整数 $n$ ，表示非负整数个数。第二入行包含 $n$ 个非负整数 $A_1, A_2, \dots A_n$ ，表示序列 $A$ 包含的非负整数。

输出格式

输出一行一个整数表示答案。

样例输入 1

5
1 4 3 3 5

样例输出 1

提示

对全部的测试数据，保证 $1 \leq n \leq 1000$ ， $0 \leq A_i \leq 10^5$ 。

代码解析

如果 m 不是完全平方数，sqrt(m) 得到的结果是一个浮点数，我们将它向下取整，再次计算平方得到的结果肯定不等于 m

1
#include<iostream>
2
#include<cmath>
3
using namespace std;
4
int main() {
5
    int n, cnt = 0, num[1001];
6
    cin >> n;
7
    for (int i = 0; i < n; i++)
8
        cin >> num[i];
9
    for (int i = 0; i < n-1; i++) {
10
        for (int j = i; j < n; j++) {
11
            int m = num[i] + num[j];
12
            int t = floor(sqrt(m));
13
            if (t * t == m)
14
                cnt++;
15
        }
16
    }
17
    cout << cnt;
18
    return 0;
19
}