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

2980 字

15 分钟

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

2025/03/22

2025/09/29

GESP

/

GESP四级

/

CPP

202509-1 排兵布阵#

题目描述

作为将军，你自然需要合理地排兵布阵。地图可以视为 $n$ 行 $m$ 列的网格，适合排兵的网格以 1 标注，不适合排兵的网格以 0 标注。现在你需要在地图上选择一个矩形区域排兵，这个矩形区域内不能包含不适合排兵的网格。请问可选择的矩形区域最多能包含多少网格？

输入格式

第一行，两个正整数 $n, m$ ，分别表示地图网格的行数与列数。

接下来 $n$ 行，每行 $m$ 个整数 $a_{i,1}, a_{i,2}, \ldots, a_{i,m}$ ，表示各行中的网格是否适合排兵。

输出格式

一行，一个整数，表示适合排兵的矩形区域包含的最大网格数。

样例输入 1

样例输出 1

样例输入 2

样例输出 2

提示

对于所有测试点，保证 $1 \leq n, m \leq 12$ ， $0 \leq a_{i,j} \leq 1$ 。

代码解析

没有技巧，根据题意使用模拟法解题即可，简而言之，可选择的矩形区域必须全都是 1，只需要以每个点 arr[i][j] 作为起点，再以这个点为矩形左上角，依次枚举右下角的点 arr[x][y]，遍历这个矩形区域，看这个区域内是否全部都是 1，如果全部都是 1 则统计这个矩形区域内点的数量 (x-i+1)*(y-j+1)，求最大值。

1
#include<bits/stdc++.h>
2
using namespace std;
3
bool arr[15][15] = {0};
4
int n, m;
5

6
// 封装 sum 函数统计以 arr[i][j] 作为左上角的矩形中全是 1 的最大矩形
7
int sum(int i, int j) {
8
    int cnt = 0;
9
    for(int x = i; x <= n; x++)
10
        for(int y = j; y <= m; y++) {
11
            bool flag = true;
12
            for(int a = i; a <= x; a++)
13
                for(int b = j; b <= y; b++)
14
                    if (arr[a][b] == 0)
15
                        flag = false;
16
            if (flag)
17
                cnt = max(cnt, (x-i+1)*(y-j+1));
18
        }
19
    return cnt;
20
}
21

22
int main() {
23

24
    cin >> n >> m;
25
    int ans = 0;
26
    for(int i = 1; i <= n; i++)
27
        for(int j = 1; j <= m; j++)
28
            cin >> arr[i][j];
29
    for(int i = 1; i <= n; i++)
30
        for(int j = 1; j <= m; j++) {
31
            ans = max(ans, sum(i, j));
32
        }
33
    cout << ans;
34

35
    return 0;
36
}

202509-2 最长连续段#

题目描述

对于 $k$ 个整数构成的数组 $[b_1, b_2, \ldots, b_k]$ ，如果对 $1 \leq i < k$ 都有 $b_{i+1} = b_i + 1$ ，那么称数组 $b$ 是一个连续段。

给定由 $n$ 个整数构成的数组 $[a_1, a_2, \ldots, a_n]$ ，你可以任意重排数组 $a$ 中元素顺序。请问在重排顺序之后， $a$ 所有是连续段的子数组中，最长的子数组长度是多少？

例如，对于数组 $[1, 0, 2, 4]$ ，可以将其重排为 $[4, 0, 1, 2]$ ，有以下 $10$ 个子数组：

$[4], [0], [1], [2], [4, 0], [0, 1], [1, 2], [4, 0, 1], [0, 1, 2], [4, 0, 1, 2]$

其中除 $[4, 0], [4, 0, 1], [4, 0, 1, 2]$ 以外的子数组均是连续段，因此是连续段的子数组中，最长子数组长度为 3。

输入格式

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

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

输出格式

一行，一个整数，表示数组 $a$ 重排顺序后，所有是连续段的子数组的最长长度。

样例输入 1

4
1 0 2 4

样例输出 1

样例输入 2

9
9 9 8 2 4 4 3 5 3

样例输出 2

提示

对于 $40\%$ 的测试点，保证 $1 \leq n \leq 8$ 。

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

代码解析

连续段的意思是 1，2，3，4 …

解题思路就是先对原数组进行排序，然后确定一个变量 last 来记录上一个数字，如果数 a[i] == last ，就跳过继续找，如果 a[i] == last + 1 则连续段长度加 1，如果 a[i] 小于 last 或大于 last + 1 说明当前连续段已经最长，记录最大值，重新开始统计下一个连续段

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

5
    int a[100005];
6
    int n;
7
    cin >> n;
8
    for(int i = 0; i < n; i++)
9
        cin >> a[i];
10
    sort(a, a+n);
11
    int last = a[0], m = 1, cnt = 1;
12
    for(int i = 1; i < n; i++) {
13
        if (a[i] == last) {
14
            continue;
15
        } else if (a[i] == last + 1) {
16
            m++;
17
            last = a[i];
18
        } else {
19
            cnt = max(cnt, m);
20
            m = 1;
21
            last = a[i];
22
        }
23
    }
24
    cnt = max(cnt, m);
25
    cout << cnt;
26

27
    return 0;
28
}

202506-1 画布裁剪#

题目描述

小 A 在高为 $h$ 宽为 $w$ 的矩形画布上绘制了一幅画。由于画布边缘留白太多，小 A 想适当地裁剪画布，只保留画的主体。具体来说，画布可以视为 $h$ 行 $w$ 列的字符矩阵，其中的字符均为 ASCII 码位于 $33 \sim 126$ 之间的可见字符，小 A 只保留画布中由第 $x_1$ 行到第 $x_2$ 行、第 $y_1$ 列到第 $y_2$ 列构成的子矩阵。

小 A 将画布交给了你，你能帮他完成画布的裁剪吗？

输入格式

第一行，两个正整数 $h, w$ ，分别表示画布的行数与列数。

第二行，四个正整数 $x_1, x_2, y_1, y_2$ ，表示保留的行列边界。

接下来 $h$ 行，每行一个长度为 $w$ 的字符串，表示画布内容。

输出格式

输出共 $x_2 - x_1 + 1$ 行，每行一个长度为 $y_2 - y_1 + 1$ 的字符串，表示裁剪后的画布。

样例输入 1

3 5
2 2 2 4
.....
.>_<.
.....

样例输出 1

>_<

样例输入 2

5 5
1 2 3 4
AbCdE
fGhIk
LmNoP
qRsTu
VwXyZ

样例输出 2

Cd
hI

提示

对于所有测试点，保证 $1 \leq h, w \leq 100$ ， $1 \leq x_1 \leq x_2 \leq h$ ， $1 \leq y_1 \leq y_2 \leq w$ 。

代码解析

这道题就是送分题，注意我们只需要输出题目要求输出的部分即可，不是真的需要将原数组裁剪。。。

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

5
    char a[101][101];
6
    int h, w, x1, x2, y1, y2;
7
    cin >> h >> w;
8
    cin >> x1 >> x2 >> y1 >> y2;
9
    for (int i = 1; i <= h; i++)
10
        for (int j = 1; j <= w; j++)
11
            cin >> a[i][j];
12
     for (int i = x1; i <= x2; i++) {
13
        for (int j = y1; j <= y2; j++)
14
            cout << a[i][j];
15
        cout << endl;
16
  }
17

18
    return 0;
19
}

202506-2 排序#

题目描述

体育课上有 $n$ 名同学排成一队，从前往后数第 $i$ 位同学的身高为 $h_i$ ，体重为 $w_i$ 。目前排成的队伍看起来参差不齐，老师希望同学们能按照身高从高到低的顺序排队，如果身高相同则按照体重从重到轻排序。在调整队伍时，每次只能交换相邻两位同学的位置。老师想知道，最少需要多少次交换操作，才能将队伍调整成目标顺序。

输入格式

第一行，一个正整数 $n$ ，表示队伍人数。

接下来 $n$ 行，每行两个正整数 $h_i$ 和 $w_i$ ，分别表示第 $i$ 位同学的身高和体重。

输出格式

输出一行，一个整数，表示最少需要的交换次数。

样例输入 1

样例输出 1

样例输入 2

样例输出 2

提示

对于所有测试点，保证 $1 \leq n \leq 3000$ ， $0 \leq h_i, w_i \leq 10^9$ 。

代码解析

这道题考察的是结构体数组的冒泡排序，注意排序中交换的条件有两条，一个是只看身高，另一个是身高相同的时候看体重，这是为数不多的考集中直接考察排序的题目，说明排序在编程题中考察的概率还是有的。

1
#include<bits/stdc++.h>
2
using namespace std;
3
struct student {
4
    int h, w;
5
}a[3005];
6
int main() {
7

8
    int n, cnt = 0;
9
    cin >> n;
10
    for (int i = 1; i <= n; i++)
11
        cin >> a[i].h >> a[i].w;
12
    // 冒泡排序
13
    for (int i = 1; i <= n-1; i++)
14
        for (int j = 1; j <= n-i; j++)
15
            if (a[j].h < a[j+1].h || a[j].h == a[j+1].h && a[j].w < a[j+1].w) {
16
                swap(a[j], a[j+1]);
17
              cnt++;
18
            }
19
    cout << cnt;
20

21
    return 0;
22
}

202503-1 荒地开垦#

题目描述

小杨有一大片荒地，可以表示为一个 $n$ 行 $m$ 列的网格图。

小杨想要开垦这块荒地，但荒地中一些位置存在杂物，对于一块不存在杂物的荒地，该荒地可以开垦当且仅当其上下左右四个方向相邻的格子均不存在杂物。

小杨可以选择至多一个位置，清除该位置的杂物，移除杂物后该位置变为荒地。小杨想知道在清除至多一个位置的杂物的情况下，最多能够开垦多少块荒地。

输入格式

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

之后 $n$ 行，每行包含一个长度为 $m$ 且仅包含字符 . 和 # 的字符串。如果为 .，代表该位置为荒地；如果为 #，代表该位置为杂物。

输出格式

输出一个整数，代表在清除至多一个位置的杂物的情况下，最多能够开垦的荒地块数。

样例输入 1

3 5
.....
.#..#
.....

样例输出 1

提示

【样例解释】

移除第二行从左数第二块空地的杂物后：

.....
....#
.....

第一行从左数前 $4$ 块荒地，第二行从左数前 $3$ 块荒地，第三行从左数前 $4$ 块荒地，均可开垦， $4+3+4=11$ 。

【数据范围】

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

代码解析

今年第一次四级考题就使用了模拟法，没有什么技巧，认真读题暴力枚举即可，这里的偏移数组 dx[] 和 dy[] 不是必要的，如果觉得思路受阻可以直接简单粗暴进行四个方向，对于代码的运行效率没有什么影响。

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

5
    int n, m, max = 0;
6
    char a[1005][1005];
7
    int dx[] = {0, 0, 1, -1};
8
    int dy[] = {1, -1, 0, 0};
9
    cin >> n >> m;
10
    for (int i = 1; i <= n; i++)
11
        for (int j = 1; j <= m; j++) {
12
            cin >> a[i][j];
13
          a[i][0] = a[i][m+1] = '.';
14
          a[0][j] = a[n+1][j] = '.';
15
    }
16
    int count = 0;
17
    for (int i = 1; i <= n; i++)
18
        for (int j = 1; j <= m; j++){
19
            if (a[i][j] == '#') continue;
20
            bool flag = true;
21
        for (int k = 0; k < 4; k++)
22
                if (a[i+dx[k]][j+dy[k]] == '#')
23
                    flag = false;
24
            if (flag) count++;
25
      }
26
    for (int i = 1; i <= n; i++)
27
        for (int j = 1; j <= m; j++){
28
            int max_count = count;
29
            if (a[i][j] == '#') {
30
                bool flag = true;
31
                for (int k = 0; k < 4; k++) {
32
                    int x = i+dx[k], y = j+dy[k];
33
                    if (a[x][y] == '#') {flag = false; break;}
34
                    if (x >= 1 && x <= n && y >= 1 && y <= m) {
35
                        int cnt = 0;
36
                        for (int d = 0; d < 4; d++)
37
                            if (a[x+dx[d]][y+dy[d]] == '#')
38
                                cnt++;
39
                        if (cnt == 1) max_count++;
40
                    }
41
                }
42
                if (flag) max_count++;
43
            }
44
             max = (max_count > max ? max_count : max);
45
        }
46
    cout << max;
47

48
    return 0;
49
}

202503-2 二阶矩阵#

题目描述

小 A 有一个 $n$ 行 $m$ 列的矩阵 $A$ 。

小 A 认为一个 $2 \times 2$ 的矩阵 $D$ 是好的，当且仅当 $D_{1,1} \times D_{2,2} = D_{1,2} \times D_{2,1}$ 。其中 $D_{i,j}$ 表示矩阵 $D$ 的第 $i$ 行第 $j$ 列的元素。

小 A 想知道 $A$ 中有多少个好的子矩阵。

输入格式

第一行，两个正整数 $n, m$ 。

接下来 $n$ 行，每行 $m$ 个整数 $A_{i,1}, A_{i,2}, \ldots, A_{i,m}$ 。

输出格式

一行，一个整数，表示 $A$ 中好的子矩阵的数量。

样例输入 1

样例输出 1

提示

【样例解释】

样例中好的子矩阵如下：

【数据范围】

对于所有测试点，保证 $1\leq n\leq 500$ ， $1\leq m\leq 500$ ， $-100\leq A_{i,j}\leq 100$

代码解析

枚举法啦，枚举就可以啦，没有啥难度嗷～注意细心一点，坐标之间的关系别搞混了。

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

5
    int n, m, a[505][505], cnt = 0;
6
    cin >> n >> m;
7
    for (int i = 1; i <= n; i++)
8
        for (int j = 1; j <= m; j++)
9
            cin >> a[i][j];
10

11
    for (int i = 1; i <= n-1; i++)
12
        for (int j = 1; j <= m-1; j++)
13
            if (a[i][j] * a[i+1][j+1] == a[i][j+1] * a[i+1][j])
14
                cnt++;
15
    cout << cnt;
16

17
    return 0;
18
}