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

202412-1 Recamán#

题目描述

小杨最近发现了有趣的 Recamán 数列，这个数列是这样生成的：

数列的第一项 $a_1$ 是 $1$ ；
如果 $a_{k-1}-k$ 是正整数并且没有在数列中出现过，那么数列的第 $k$ 项 $a_k$ 为 $a_{k-1}-k$ ，否则为 $a_{k-1}+k$ 。

小杨想知道 Recamán 数列的前 $n$ 项从小到大排序后的结果。手动计算非常困难，小杨希望你能帮他解决这个问题。

输入格式

第一行，一个正整数 $n$ 。

输出格式

一行， $n$ 个空格分隔的整数，表示 Recamán 数列的前 $n$ 项从小到大排序后的结果。

样例输入 1

样例输出 1

1 2 3 6 7

样例输入 2

样例输出 2

1 2 3 6 7 12 13 20

提示

【样例解释】

对于样例 1， $n=5$ ：

$a_1=1$ ；
$a_1-2=-1$ ，不是正整数，因此 $a_2=a_1+2=3$ ；
$a_2-3=0$ ，不是正整数，因此 $a_3=a_2+3=6$ ；
$a_3-4=2$ ，是正整数，且没有在数列中出现过，因此 $a_4=a_3-4=2$ ；
$a_4-5=-3$ ，不是正整数，因此 $a_5=a_4+5=7$ 。

$a_1,a_2,a_3,a_4,a_5$ 从小到大排序的结果为 $1,2,3,6,7$ 。

【数据范围】

对于所有数据点，保证 $1\le n\le 3\, 000$ 。

代码解析

根据题目意思写代码，模拟法解题即可，这里可以把“正整数并且没有在数列中出现过”封装为一个 check() 函数，可以让主函数可读性更佳，其余没有什么难点了。

1
#include<bits/stdc++.h>
2
using namespace std;
3
int n, a[3005];
4
bool check(int num) {
5
    if (num <= 0) return false;
6
    for (int i = 1; i <= n; i++)
7
        if (num == a[i])
8
            return false;
9
    return true;
10
}
11
int main() {
12

13
    a[1] = 1;
14
    cin >> n;
15
    for (int i = 2; i <= n; i++)
16
        if (check(a[i-1] - i))
17
            a[i] = a[i-1] - i;
18
      else
19
            a[i] = a[i-1] + i;
20
    sort(a+1, a+n+1);
21
    for (int i = 1; i <= n ; i++)
22
        cout << a[i] << ' ';
23

24

25
    return 0;
26
}

202412-2 字符排序#

题目描述

小杨有 $n$ 个仅包含小写字母的字符串 $s_1,s_2,\ldots,s_n$ ，小杨想将这些字符串按一定顺序排列后拼接到一起构成字符串 $t$ 。小杨希望最后构成的字符串 $t$ 满足：

假设 $t_i$ 为字符串 $t$ 的第 $i$ 个字符，对于所有的 $j\lt i$ 均有 $t_j\le t_i$ 。两个字符的大小关系与其在字母表中的顺序一致，例如 $\texttt{e}\lt \texttt{g}\lt \texttt{p} \lt \texttt{s}$ 。

小杨想知道是否存在满足条件的字符串排列顺序。

输入格式

第一行包含一个正整数 $T$ ，代表测试数据组数。

对于每组测试数据，第一行包含一个正整数 $n$ ，含义如题面所示。

之后 $n$ 行，每行包含一个字符串 $s_i$ 。

输出格式

对于每组测试数据，如果存在满足条件的排列顺序，输出（一行一个） $\texttt{1}$ ，否则输出（一行一个） $\texttt{0}$ 。

样例输入 1

3
3
aa
ac
de
2
aac
bc
1
gesp

样例输出 1

1
0
0

提示

【样例解释】

对于第一组测试数据，一种可行的排列顺序为 $\texttt{aa}+\texttt{ac}+\texttt{de}$ ，构成的字符串 $t$ 为 $\texttt{aaacde}$ ，满足条件。

对于全部数据，保证有 $1\le T,n\le 100$ ，每个字符串的长度不超过 $10$ 。

代码解析

题目的意思是，我们需要对于这个字符串数组重新排列，拼接成一个新的字符串，这个字符串里面的字符都需要按照字母表（ASCII 编码）去排序，需要知道能否找到这样的排列方式

思考一下，如果存在这样的排列方式，那么任何一个字符串的字典序一定比前一个字符串的字典序大，所以我们可以先对字符串数组按照字典序排序，然后拼接成新字符串，检查一下拼接后的字符串的每个字符是否大于等于前一个字符即可。

1
#include<bits/stdc++.h>
2
using namespace std;
3
bool check(string s) {
4
    for (int i = 1; i < s.size(); i++)
5
        if (s[i-1] > s[i])
6
            return false;
7
    return true;
8
}
9
int main() {
10

11
    int t, n;
12
    cin >> t;
13
    while (t--) {
14
        cin >> n;
15
        string a[105], s;
16
        for (int i = 0; i < n; i++)
17
            cin >> a[i];
18
        sort(a, a+n);
19
        for (int i = 0; i < n; i++)
20
            s += a[i];
21
        if (check(s)) cout << 1 << endl;
22
        else cout << 0 << endl;
23
    }
24

25
    return 0;
26
}

202409-1 黑白方块#

题目描述

小杨有一个 $n$ 行 $m$ 列的网格图，其中每个格子要么是白色，要么是黑色。小杨想知道网格图中是否存在一个满足如下条件的子矩形：

子矩形由 $4$ 行 $4$ 列组成；
子矩形的第 $1$ 行和第 $4$ 行只包含白色格子；
对于子矩形的第 $2$ 行和第 $3$ 行，只有第 $1$ 个和第 $4$ 个格子是白色的，其余格子都是黑色的；

请你编写程序帮助小杨判断。

输入格式

第一行包含一个正整数 $t$ ，代表测试用例组数。
接下来是 $t$ 组测试用例。对于每组测试用例，一共 $n+1$ 行。
第一行包含两个正整数 $n,m$ ，含义如题面所示。
之后 $n$ 行，每行一个长度为 $m$ 的 $01$ 串，代表网格图第 $i$ 行格子的颜色，如果为 $0$ ，则对应格子为白色，否则为黑色。

输出格式

对于每组测试用例，如果存在，输出 Yes，否则输出 No。

样例输入 1

样例输出 1

No
Yes
No

提示

【样例 1 解释】

【数据规模与约定】

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

代码解析

这道题也是暴力枚举解题即可，注意有多层循环跳出比较麻烦的话可以多封装几个函数，模块化编写不容易出问题，这道题需要注意的是行列如果小于 4 则不需要进行额外判断，还有多个 if 如果嵌套的话注意加大括号。

1
#include<bits/stdc++.h>
2
using namespace std;
3
int t, n, m;
4
int a[105][105];
5
bool check4(int i, int j) {
6
    for (int x = i; x <= i+3; x++)
7
        for (int y = j; y <= j+3; y++)
8
            if (x == i || x == i+3) {
9
                if (a[x][y] == 1) return false;
10
            } else {
11
                if (y == j || y == j+3) {
12
                    if (a[x][y] == 1) return false;
13
                } else {
14
                    if (a[x][y] == 0) return false;
15
                }
16
            }
17
    return true;
18
}
19
bool check() {
20
    if (n < 4 || m < 4) return false;
21
    // 枚举 4 行 4 列的左上角起点
22
    for (int i = 1; i <= n-3; i++)
23
        for (int j = 1; j <= m-3; j++)
24
            if (check4(i, j))
25
                return true;
26
    return false;
27
}
28
int main() {
29

30
    cin >> t;
31
    while (t--) {
32
        cin >> n >> m;
33
        for (int i = 1; i <= n; i++) {
34
            string s;
35
            cin >> s;
36
            for (int j = 1; j <= m; j++)
37
                a[i][j] = s[j-1] - '0';
38
        }
39
        if (check())
40
            cout << "Yes" << endl;
41
        else
42
            cout << "No" << endl;
43
    }
44

45
    return 0;
46
}

202409-2 区间排序#

题目描述

小杨有一个包含 $n$ 个正整数的序列 $a$ 。

小杨计划对序列进行多次升序排序，每次升序排序小杨会选择一个区间 $[l,r]$ （ $l \leq r$ ）并对区间内所有数字，即进行升序 $a_l, a_{l + 1}, \dots a_r$ 排序。每次升序排序会在上一次升序排序的结果上进行。

小杨想请你计算出多次升序排序后的序列。

输入格式

第一行包含一个正整数 $n$ ，含义如题面所示。
第二行包含 $n$ 个正整数 $a_1, a_2, \dots a_n$ ，代表序列 $a$ 。
第三行包含一个正整数 $q$ ，代表排序次数。
之后 $q$ 行，每行包含两个正整数 $l, r$ ，代表将区间 $[l_i, r_i]$ 内所有数字进行升序排序。

输出格式

输出一行包含 $n$ 个正整数，代表多次升序排序后的序列。

样例输入 1

样例输出 1

1 3 4 5 2

提示

【样例 1 解释】

第一次升序排序后，序列为 $[3,4,5,1,2]$ ；
第二次升序排序后，序列为 $[3,4,1,5,2]$ ；
第三次升序排序后，序列为 $[1,3,4,5,2]$ ；

【数据规模与约定】

对于全部的测试数据，保证 $1 \leq n, a_i, q \leq 100$ ， $1 \leq l_i \leq r_i \leq n$ 。

代码解析

很简单的一道题，考察对于 STL sort() 的运用，注意参数即可。

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 q, l, r;
10
    cin >> q;
11
    while (q--) {
12
        cin >> l >> r;
13
        sort(a+l, a+r+1);
14
    }
15
    for (int i = 1; i <= n; i++)
16
        cout << a[i] << ' ';
17

18

19
    return 0;
20
}

202406-1 黑白方块#

题目描述

小杨有一个 $n$ 行 $m$ 列的网格图，其中每个格子要么是白色，要么是黑色。对于网格图中的一个子矩形，小杨认为它是平衡的当且仅当其中黑色格子与白色格子数量相同。小杨想知道最大的平衡子矩形包含了多少个格子。

输入格式

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

之后 $n$ 行，每行一个长度为 $m$ 的 $01$ 串，代表网格图第 $i$ 行格子的颜色，如果为 $0$ ，则对应格子为白色，否则为黑色。

输出格式

输出一个整数，代表最大的平衡子矩形包含格子的数量，如果不存在则输出 $0$ 。

样例输入 1

样例输出 1

提示

【样例解释】

对于样例 $1$ ，假设 $(i,j)$ 代表第 $i$ 行第 $j$ 列，最大的平衡子矩形的四个顶点分别为 $(1,2),(1,5),(4,2),(4,5)$ 。

【数据范围】

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

代码解析

暴力枚举解题即可，我们枚举子矩形的左上角的坐标（a, b）以及右下角的坐标（c, d），检查这个矩形中黑白方块的个数是否相同即可，这道题考察的依旧是对题目的理解能力、数组的下标规律以及编写代码的细心程度。

1
#include<bits/stdc++.h>
2
using namespace std;
3
int n, m, max_cnt = 0;
4
char w[11][11];
5
void check(int a, int b, int c, int d) {
6
    int t = 0, f = 0;
7
    for (int i = a; i <= c; i++)
8
        for (int j = b; j <= d; j++)
9
            if (w[i][j] == '1') t++;
10
        else f++;
11
    if (t == f) {
12
        max_cnt = max(max_cnt, (c-a+1)*(d-b+1));
13
    }
14
}
15
int main() {
16

17
    cin >> n >> m;
18
    for (int i = 1; i <= n; i++)
19
        for (int j = 1; j <= m; j++)
20
            cin >> w[i][j];
21
    for (int a = 1; a <= n; a++)
22
        for (int b = 1; b <= m; b++)
23
            for (int c = a; c <= n; c++)
24
                for (int d = b; d <= m; d++)
25
          check(a, b, c, d);
26
    cout << max_cnt;
27

28
    return 0;
29
}

202406-2 宝箱#

题目描述

小杨发现了 $n$ 个宝箱，其中第 $i$ 个宝箱的价值是 $a_i$ 。

小杨可以选择一些宝箱放入背包并带走，但是小杨的背包比较特殊，假设小杨选择的宝箱中最大价值为 $x$ ，最小价值为 $y$ ，小杨需要保证 $x-y\leq k$ ，否则小杨的背包会损坏。

小杨想知道背包不损坏的情况下，自己能够带走宝箱的总价值最大是多少。

输入格式

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

第二行包含 $n$ 个正整数 $a_1,a_2,\dots,a_n$ ，代表宝箱的价值。

输出格式

输出一个整数，代表带走宝箱的最大总价值。

样例输入 1

5 1
1 2 3 1 2

样例输出 1

提示

【样例解释】

在背包不损坏的情况下，小杨可以拿走两个价值为 $2$ 的宝箱和一个价值为 $3$ 的宝箱。

【数据范围】

对于全部数据，保证有 $1\leq n\leq 1000$ ， $0\leq k\leq 1000$ ， $1\leq a_i\leq 1000$ 。

代码解析

还是枚举啦，小杨的背包中最大价值和最小价值的物品的差是有要求的，我们只需要把物品按照价值从小到大排序，然后确定一个价值最小的物品 a[i]，然后累加 a[i] 之后所有满足 a[x] - a[i] <= k 的 a[x]，就可以枚举出一种可能性，再打擂台即可。

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

5
    int a[1005], n, k, w = 0;
6
    cin >> n >> k;
7
    for (int i = 0; i < n; i++)
8
        cin >> a[i];
9
    sort(a, a+n);
10
    for (int i = 0; i < n; i++)
11
        for (int j = i; j < n; j++){
12
            int sum = 0;
13
            for (int x = i; x <= j; x++)
14
                if (a[x] - a[i] <= k)
15
                    sum += a[x];
16
            w = max(sum, w);
17
        }
18
    cout << w;
19

20
    return 0;
21
}

如果觉得三层循环枚举时间复杂度太高，也可以使用双指针，如果 a[x] - a[i] <= k 则 x++，否则 i++。记得同步修改 sum，注意边界问题。

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

5
    int a[1005], n, k, w = 0;
6
    cin >> n >> k;
7
    for (int i = 0; i < n; i++)
8
        cin >> a[i];
9
    sort(a, a+n);
10
    int i = 0, x = 0, sum = 0;
11
    while (x != n) {
12
        while (a[x] - a[i] <= k && x < n) {
13
            sum += a[x];
14
            x++;
15
        }
16
        w = max(sum, w);
17
        while (a[x] - a[i] > k && i <= x) {
18
            sum -= a[i];
19
            i++;
20
        }
21
    }
22
    cout << w;
23

24
    return 0;
25
}

202403-1 相似字符串#

题目描述

对于两个字符串 $A$ 和 $B$ ，如果 $A$ 可以通过删除一个字符，或插入一个字符，或修改一个字符变成 $B$ ，那么我们说 $A$ 和 $B$ 是相似的。

比如 $\texttt{apple}$ 可以通过插入一个字符变成 $\texttt{applee}$ ，可以通过删除一个字符变成 $\texttt{appe}$ ，也可以通过修改一个字符变成 $\texttt{bpple}$ 。因此 $\texttt{apple}$ 和 $\texttt{applee}$ 、 $\texttt{appe}$ 、 $\texttt{bpple}$ 都是相似的。但 $\texttt{applee}$ 并不能通过任意一个操作变成 $\texttt{bpple}$ ，因此它们并不相似。

特别地，两个完全相同的字符串也是相似的。

给定 $T$ 组 $A,B$ ，请你分别判断它们是否相似。

输入格式

第一行一个正整数 $T$ 。
接下来 $T$ 行，每行两个用空格隔开的字符串 $A$ 和 $B$ 。

输出格式

对组 $A,B$ ，如果他们相似，输出 similar，否则输出 not similar。

样例输入 1

5
apple applee
apple appe
apple bpple
applee bpple
apple apple

样例输出 1

similar
similar
similar
not similar
similar

提示

对全部的测试数据，保证 $1 \leq T \leq 100$ ， $A$ 和 $B$ 的长度不超过 $50$ ，仅含小写字母。

代码解析

题目本身不难，判断需要先看两个字符之间的长度差是 0 还是 1，除他们之外就不可能相似，分情况讨论：

如果长度差是 0，则只允许一个字符不相同

如果长度差是 1，则肯定是多了一位，其他位都相同

1
#include<bits/stdc++.h>
2
using namespace std;
3
bool is_similar(string s1, string s2) {
4
    // 为了方便处理，我们通过交换确保 s1 比 s2 长
5
    if (s1.size() > s2.size()) swap(s1, s2);
6
    int sub_size = s2.size() - s1.size();
7
    if (sub_size == 0) {
8
        int cnt = 0;
9
        for (int i = 0; i < s1.size(); i++)
10
            if (s1[i] != s2[i])
11
                cnt++;
12
        return cnt <= 1;
13
    } else if (sub_size == 1) {
14
        for (int i = 0, j = 0; i < s1.size(); i++, j++)
15
            if (s1[i] != s2[j]) {
16
                j++;
17
                if (s1[i] != s2[j]) return false;
18
            }
19
        return true;
20
    }
21
    return false;
22
}
23
int main() {
24

25
    int n;
26
    cin >> n;
27
    string s1, s2;
28
    while (n--) {
29
        cin >> s1 >> s2;
30
        if (is_similar(s1, s2))
31
            cout << "similar" << endl;
32
        else
33
            cout << "not similar" << endl;
34
    }
35

36
    return 0;
37
}

202403-2 做题#

题目描述

小杨同学为了提高自己的实力制定了做题计划，在第 $k$ 天时，他必须要完成 $k$ 道题，否则他就会偷懒。

小杨同学现在找到了一个题库，一共有 $n$ 套题单，每一套题单中有一定数量的题目。但是他十分挑剔，每套题单他只会使用一次，每一天也只能使用一套题单里的题目，之后那套题单就会弃之不用。对于每套题单，他不必完成题单内所有的题。

那么问题来了，小杨同学最多做题几天才偷懒呢？

输入格式

第一行，一个整数为 $n$ ，表示有多少套题单。
第二行 $n$ 个整数 $a_1, a_2, \dots a_n$ ，分别表示每套题单有多少道题。

输出格式

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

样例输入 1

4
3 1 4 1

样例输出 1

提示

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

代码解析

认真细心即可答对，考点就是数组以及排序，其实也可以说是双指针思路，排好序之后依次尝试，如果卷子 a[i] 的题目数量大于天数 day 则换下一套题下一天，如果题目不够则只换下一套题（i++），最后注意如果最后一天题目不够的话，天数实际上是多一天。

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

5
    int n, a[1000005], day = 1;
6
    cin >> n;
7
    for (int i = 0; i < n; i++)
8
        cin >> a[i];
9
    sort(a, a+n);
10
    for (int i = 0; i < n; i++)
11
        if (a[i] >= day)
12
            day++;
13
    cout << day-1;
14

15
    return 0;
16
}