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

GESP-C++四级 题库

共 324 道题 ,第 16 / 17 页 · 按题型筛选,点「查看答案」核对解析
301 简答题 偏难 GESP编程能力等级认证 ·GESP-C++四级 · 1.1 指针定义

建造

时间限制:1.0 s

内存限制:512.0 MB

题目描述

小 A 有一张M行N列的地形图,其中第i 行第 列的数字aij代表坐标 ( i,j)) 的海拔高度。停机坪为一个3*3的区域且内部所有 9个点的最大高度和最小高度之差不超过H。 小 A 想请你计算出,在所有适合建造停机坪的区域中,区域内部9个点海拔之和最大是多少。

输入格式

第一行三个正整数M,N,H,含义如题面所示。之后M行,第i行包含N个整数ai1,ai2,...,aiN,代表坐标(i,j)的高度。数据保证总存在一个适合建造停机坪的区域。

输出格式

输出一行,代表最大的海拔之和。

输入样例

5 5 3
5 5 5 5 5
5 1 5 1 5
5 5 5 5 5
5 2 5 2 5
3 5 5 5 2

输出样例

40

数据范围

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

int a[1010][1010];
int main() {
    int M, N, H;
    cin >> M >> N >> H;

    for (int i = 1; i <= M; ++i) {
        for (int j = 1; j <= N; ++j) {
            cin >> a[i][j];
        }
    }

    int max_sum = 0;
    for (int i = 1; i <= M - 2; ++i) {
        for (int j = 1; j <= N - 2; ++j) {
            int local_max = a[i][j], local_min = a[i][j], local_sum = 0;
            for (int x = 0; x < 3; ++x) {
                for (int y = 0; y < 3; ++y) {
                    int height = a[i + x][j + y];
                    local_sum += height;
                    if (height > local_max)
                        local_max = height;
                    if (height < local_min)
                        local_min = height;
                }
            }
            if (local_max - local_min <= H) {
                if (local_sum > max_sum) {
                    max_sum = local_sum;
                }
            }
        }
    }

    cout << max_sum;
    return 0;
}
题目详情
302 简答题 偏难 GESP编程能力等级认证 ·GESP-C++四级 · 综合练习

优先购买

时间限制:1.0 s

内存限制:512.0 MB

题目描述

小 A 有M元预算。商店有N个商品,每个商品有商品名S 、价格P和优先级V三种属性,其中V为正整数,且V越小代表商品的优先级越高。

小 A 的购物策略为:

总是优先买优先级最高的东西;

如果有多个最高优先级商品,购买价格最低的;

如果有多个优先级最高且价格最低的商品,购买商品名字典序最小的。

小 A 想知道能购买哪些商品。

输入格式

第一行两个正整数 M,N,代表预算和商品数。

之后N行,每行一个商品,依次为Si,Pi,Vi ,代表第 个商品的商品名、价格、优先级。数据保证不存在两个名字相同的商品。

输出格式

按照字典序从小到大的顺序,输出所有购买商品的商品名。

输入样例

20 4
apple 6 8
bus 15 1
cab 1 10
water 4 8

输出样例

bus
cab
water

数据范围

对于所有测试点,保证商品名仅由小写字母组成且不存在两个相同的商品名。

答案与解析
参考答案
#include <iostream>
#include <algorithm>
#include <string>
#include <map>
#include <assert.h>
using namespace std;

struct Item {
    string name;
    int price;
    int priority;
};

bool cmp(const Item &a, const Item &b) {
    if (a.priority != b.priority)
        return a.priority < b.priority;
    if (a.price != b.price)
        return a.price < b.price;
    return a.name < b.name;
}

string s[1005];
std::map<string, int> mp;

int main() {
    int M, N;
    cin >> M >> N;
    Item items[N];
    
    for (int i = 0; i < N; ++i) {
        cin >> items[i].name >> items[i].price >> items[i].priority;
        assert(mp.find(items[i].name) == mp.end());
        mp[items[i].name] = items[i].priority;
    }
    
    sort(items, items + N, cmp);
    int budget = M;
    int count = 0;
    
    for (int i = 0; i < N; ++i) {
        if (items[i].price <= budget) {
            budget -= items[i].price;
            s[count++] = items[i].name;
        }
    }
    
    sort(s, s + count);
    for (int i = 0; i < count; ++i) {
        cout << s[i] << endl;
    }
    
    return 0;
}
题目详情
303 简答题 偏难 GESP编程能力等级认证 ·GESP-C++四级 · 综合练习

排兵布阵

答案与解析
参考答案
#include <algorithm>
#include <cstdio>
using namespace std;
const int N = 15;
int n, m;
int a[N][N], col[N][N];
int ans;
int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++) {
            scanf("%d", &a[i][j]);
            col[j][i] = col[j][i-1] + a[i][j]; // 第j列前缀和
        }
    for (int u = 1; u <= n; u++)
        for (int l = 1; l <= m; l++)
            for (int d = u; d <= n; d++) {
                int chk = 1;
                for (int r = l; r <= m; r++) {
                    // u~d行总和等于行数则全1
                    if (col[r][d] - col[r][u-1] != d - u + 1) {
                        chk = 0;
                    }
                    if (!chk) break;
                    ans = max(ans, (r - l + 1) * (d - u + 1));
                }
            }
    printf("%d\n", ans);
    return 0;
}
题目详情
304 简答题 偏难 GESP编程能力等级认证 ·GESP-C++四级 · 综合练习

最长连续段

答案与解析
参考答案
#include <algorithm>
#include <cstdio>
using namespace std;
const int N = 1e5 + 5;
int n;
int a[N];
int last, cnt, mx;
int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) 
        scanf("%d", &a[i]);
    sort(a + 1, a + n + 1);
    
    last = a[1];
    cnt = mx = 1;
    // 从第二个元素开始遍历
    for (int i = 2; i <= n; i++) {
        if (a[i] == last) {
            // 重复数字,连续长度不变
        } else if (a[i] == last + 1) {
            cnt++;
        } else {
            cnt = 1;
        }
        last = a[i];
        mx = max(cnt, mx);
    }
    printf("%d\n", mx);
    return 0;
}
题目详情
305 简答题 偏难 GESP编程能力等级认证 ·GESP-C++四级 · 1.3 引用

画布裁剪

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

【问题描述】

小 A 在高为 h 宽为 w 的矩形画布上绘制了一幅画。由于画布边缘留白太多,小 A 想适当地裁剪画布,只保留画的主体。

具体来说,画布可以视为 h 行 w 列的字符矩阵,其中的字符均为 ASCII 码位于 33~126 之间的可见字符,小 A只保留画布中由第 x1 行到第 x2 行、第 y1 列到第 y2 列构成的子矩阵。

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

【输入描述】

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

第二行,四个正整数 x1、x2、y1、y2,表示保留的行列边界。

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

【输出描述】

输出共 x2 - x1 + 1 行,每行一个长度为 y2 - y1 + 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 <= h、w <= 100,1 <= x1 <= x2 <= h,1 <= y1 <= y2 <= w。

答案与解析
参考答案
#include <iostream>
#include <cstring>
using namespace std;
int n, m;
string s[105];
int x1, x2, y1, y2;
int main() {
    cin >> n >> m >> x1 >> x2 >> y1 >> y2;
    for (int i = 0; i < n; i++)
        cin >> s[i];
    for (int i = x1 - 1; i < x2; i++) {
        string s1 = s[i].substr(y1 - 1, y2 - y1 + 1);
        cout << s[i].substr(y1 - 1, y2 - y1 + 1) << endl;
    }
    return 0;
}
题目详情
306 简答题 偏难 GESP编程能力等级认证 ·GESP-C++四级 · 1.3 引用

排序

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

【问题描述】

体育课上有 n 名同学排成一队,从前往后数第 i 位同学的身高为 hi,体重为 wi。

目前排成的队伍看起来参差不齐,老师希望同学们能按照身高从高到低的顺序排队,如果身高相同则按照体重从重到轻排序。

在调整队伍时,每次只能交换相邻两位同学的位置。老师想知道,最少需要多少次交换操作,才能将队伍调整成目标顺序。

【输入描述】

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

接下来 n 行,每行两个正整数 hi 和 wi,分别表示第 i 位同学的身高和体重。

【输出描述】

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

【样例输入1】

5
1 60
3 70
2 80
4 55
4 50

【样例输出1】

8

【样例输入2】

5
4 0
4 0
2 0
3 0
1 0

【样例输出2】

1

【数据范围】

对于所有测试点,保证 1 <= n <= 3000,0 <= hi、wi<= 10^9。

答案与解析
参考答案
#include <iostream>
#include <vector>
using namespace std;
int main() {
    int n, ans = 0;
    cin >> n;
    vector<pair<int,int>> a(n);
    for (int i = 0; i < n; i ++)
        cin >> a[i].first >> a[i].second;
    for (int i = 0; i < n; i ++)
        for (int j = i + 1; j < n; j ++)
            if (a[i] < a[j])
                ans ++;
    cout << ans << '\n';
    return 0;
}
题目详情
307 简答题 偏难 GESP编程能力等级认证 ·GESP-C++四级 · 综合练习

荒地开垦

时间限制: 1.0 s

内存限制 :512.0 MB

题面描述

小杨有—大片荒地,可以表⽰为—个n行m列的网格图。

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

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

输入格式

第—行包含两个正整数  n ,  m ,含义如题面所⽰。

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

输出格式

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

输入样例

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

输出样例

11

样例解释

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

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

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

数据范围

对于全部数据,保证有  1 ≤ n, m ≤ 1000 。

答案与解析
参考答案
#include<bits/stdc++.h>
using namespace std;
const int N = 1005;
char mat[N][N];
int a[N][N];
const int d[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
int main() {
	int n, m, ans = 0;
	scanf("%d%d", &n, &m);
	assert(1 <= n && n <= 1000);
	assert(1 <= m && m <= 1000);
	for (int i = 1; i <= n; i ++)
		scanf("%s", mat[i] + 1);
	for (int i = 1; i <= n; i ++)
		for (int j = 1; j <= m; j ++) {
			int num = 0, p = -1;
			for (int k = 0; k < 4; k ++)
				if (mat[i + d[k][0]][j + d[k][1]] == '#')
					num ++, p = k;
			if (mat[i][j] == '. ' && num == 1)
				a[i + d[p][0]][j + d[p][1]] ++;
			else if (mat[i][j] == '. ' && num == 0)
				ans ++;
			else if (mat[i][j] == '#' && num == 0)
				a[i][j] ++;
		}
	int mx = 0;
	for (int i = 1; i <= n; i ++)
		for (int j = 0; j <= m; j ++)
			mx = max(mx, a[i][j]);
	cout << ans + mx << endl;
	return 0;
}


遍历全图,先找到所有不需要移除杂物即可开垦的荒地数量,另外构建数组a表示移除该点的杂物可 以激活的荒地数量,最后找到a数组中的最大值,就是我们要移除杂物的位置,把最大值更新到答案中就是我们要 的最终答案。

题目详情
308 简答题 偏难 GESP编程能力等级认证 ·GESP-C++四级 · 1.1 指针定义

二阶矩阵

题目描述

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

小 A 认为—个 2*2的矩阵 D 是好的,当且仅当D1,1 * D2,2 = D1,2 * D2,1。其中 Di,j表⽰矩阵 的第 i行第 j列 的元 素。 小 A 想知道 A中有多少个好的子矩阵。

输入格式

第—行,两个正整数 n和m。

接下来 n行,每行 m 个整数 Ai,1,Ai,2,...,Ai,m

输出格式

—行, —个整数,表⽰ 中好的子矩阵的数量。


输入样例

3 4
1 2 1 0
2 4 2 1
0 3 3 0

输出样例

2

数据范围

对于所有测试点,保证 1 ≤ n ≤ 500 , 1 ≤  m ≤ 500 ,-100 ≤ Ai,j ≤ 100 。

答案与解析
参考答案
#include <bits/stdc++.h>
using namespace std;

const int N = 505;
int n, m;
int a[N][N];
int ans;

int main() {
	scanf("%d%d", &n, &m);
	assert(1 <= n && n <= 500 && 1 <= m && m <= 500);
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= m; j++) {
			scanf("%d", &a[i][j]);
			assert(-100 <= a[i][j] && a[i][j] <= 100);
		}
	for (int i = 1; i < n; i++)
		for (int j = 1; j < m; j++)
			if (a[i][j] * a[i + 1][j + 1] == a[i + 1][j] * a[i][j + 1])
				ans++;
	printf("%d\n", ans);
	return 0;
}

按照题目的公式,对输入矩阵进行暴力循环,统计答案个数即可。

题目详情
309 简答题 偏难 GESP编程能力等级认证 ·GESP-C++四级 · 综合练习

Recamán

时间限制:1.0 s

内存限制:512.0 MB

题目描述

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

数列的第一项 a1是 1 ;

如果 ak−1−k 是正整数并且没有在数列中出现过,那么数列的第 k 项 ak为 ak−1−k,否则为 ak−1+k。

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

输入格式

第一行,一个正整数 n 。

输出格式

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

输入样例 1

5

输出样例 1

1 2 3 6 7

输入样例 2

8

输出样例 2

1 2 3 6 7 12 13 20

样例解释

对于样例 1,n=5 :

a1=1;

a1−2=−1,不是正整数,因此 a2=a1+2=3;

a2−3=0,不是正整数,因此 a3=a2+3=6;

a3−4=2,是正整数,且没有在数列中出现过,因此 a4=2;

a4−5=−3,不是正整数,因此 a5=a4+5=7;

a1,a2,a3,a4,a5从小到大排序后的结果为 1 2 3 6 7 。

数据范围

对于所有数据点,保证 1≤n≤3000。

答案与解析
参考答案
#include <cstdio>
#include <algorithm>

using namespace std;

const int N = 2e5 + 5;
const int C = 1e6 + 5;

int n;
int a[N];
int vis[C];

void bubble_sort(int *a, int n) {
	bool flag = true;
	while (flag) {
		flag = false;
		for (int i = 1; i < n; ++i) {
			if (a[i] > a[i + 1]) {
				flag = true;
				int t = a[i];
				a[i] = a[i + 1];
				a[i + 1] = t;
			}
		}
	}
}

int main() {
	scanf("%d", &n);
	a[1] = 1;
	vis[1] = 1;
	for (int i = 2; i <= n; i++) {
		if (a[i - 1] - i <= 0 || vis[a[i - 1] - i])
			a[i] = a[i - 1] + i;
		else
			a[i] = a[i - 1] - i;
		vis[a[i]] = 1;
	}
	bubble_sort(a, n);
	for (int i = 1; i <= n; i++)
		printf("%d%c", a[i], " \n"[i == n]);
	return 0;
}
题目详情
310 简答题 偏难 GESP编程能力等级认证 ·GESP-C++四级 · 1.3 引用

字符排序

时间限制:1.0 s

内存限制:512.0 MB

题面描述

小杨有 n 个仅包含小写字母的字符串 s1,s2,...,sn,小杨想将这些字符串按一定顺序排列后拼接到一起构成字符串 t 。小杨希望最后构成的字符串 满足:

假设 ti为字符串 t 的第 i 个字符,对于所有的 j<i 均有 tj≤ti。两个字符的大小关系与其在字母表中的顺序一致,例如e<g<p<s。

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

输入格式

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

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

之后 n 行,每行包含一个字符串 si。

输出格式

对于每组测试数据,如果存在满足条件的排列顺序,输出 1,否则输出 0。


输入样例

3
3
aa
ac
de
2
aac
bc
1
gesp

输出样例

1
0
0

样例解释

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

对于全部数据,保证有 1≤t,n≤100,每个字符串的长度不超过 10。

答案与解析
参考答案
#include<bits/stdc++.h>
using namespace std;
string s[110];
void bubble_sort(string *a, int n) {
	bool flag = true;
	while (flag) {
		flag = false;
		for (int i = 1; i < n; ++i) {
			if (a[i] > a[i + 1]) {
				flag = true;
				string t = a[i];
				a[i] = a[i + 1];
				a[i + 1] = t;
			}
		}
	}
}
int main(){
	int t;
	cin>>t;
	while(t--){
		int n;
		cin>>n;
		for(int i=1;i<=n;i++){
			cin>>s[i];
		}
		bubble_sort(s, n);
		string t="";
		for(int i=1;i<=n;i++){
			t+=s[i];
		}
		int m = t.size();
		int fl=1;
		for(int i=1;i<m;i++){
			if(t[i]<t[i-1]){
				fl=0;
				break;
			}
		}
		cout<<fl<<"\n";
	}
}
题目详情
311 简答题 偏难 GESP编程能力等级认证 ·GESP-C++四级 · 综合练习

黑白方块

时间限制:1.0 s

内存限制:512.0 MB

题面描述

小杨有一个n行m 列的网格图,其中每个格子要么是白色,要么是黑色。

小杨想知道网格图中是否存在一个满足如下条件的子矩形:

子矩形由4行4列组成;

子矩形的第1行 和第4行只包含白色格子;

对于子矩形的第2行 和第3行,只有第1个和第4个格子是白色的,其余格子都是黑色的;

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

输入格式

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

接下来是t组测试用例。对于每组测试用例,一共n+1 行。

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

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

输出格式

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


输入样例

3
1 4
0110
5 5
00000
01100
01100
00001
01100
5 5
00000
01100
01110
00001
01100

输出样例

No
Yes
No

满足条件的子矩形形如:

0000
0110
0110
0000

对于全部数据,保证有1≤t≤10,1≤n,m≤100。

答案与解析
参考答案
#include<bits/stdc++.h>
using namespace std;
const int N = 110;
int w[N][N];
int n,m;
int match[4][4];
bool check(int xa,int ya){
	for(int i=0;i<4;i++){
		for(int j=0;j<4;j++){
			if(w[xa+i][ya+j]!=match[i][j]){
				return false;
			}
		}
	}
	return true;
}

int main(){
	int t;
	cin>>t;
	for(int i=1;i<3;i++)match[1][i]=match[2][i]=1;
	while(t--){
		cin>>n>>m;
		for(int i=1;i<=n;i++){
			string s;
			cin>>s;
			for(int j=1;j<=m;j++){
				w[i][j]=s[j-1]-'0';
			}
		}
		int fl = 0;
		for(int i=1;i<=n-3;i++){
			for(int j=1;j<=m-3;j++){
				if(check(i,j)){
					fl=1;
				}
			}
		}
		if(fl)cout<<"Yes\n";
		else cout<<"No\n";
	}
}

定义二维数组,存储将要输入的网格数据;

将要匹配的模版矩形初始化,4X4的二维数组;

使用循环遍历网格数据中每一个可能的4X4子矩形,检查从位置(i,j)开始的子矩形是否与之前定义好的模版匹配进行判断,输出结果

题目详情
312 简答题 偏难 GESP编程能力等级认证 ·GESP-C++四级 · 综合练习

区间排序

时间限制:1.0 s

内存限制:512.0 MB

题面描述

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

小杨计划对序列进行多次升序排序,每次升序排序小杨会选择一个区间[l,r](l≤r) 并对区间内所有数字,即al,al+1,...,ar进行升序排序。每次升序排序会在上一次升序排序的结果上进行。

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

输入格式

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

第二行包含n个正整数 a1,a2,...,an,代表序列。

第三行包含一个正整数q,代表排序次数。

之后q行,每行包含两个正整数li,ri,代表将区间[li,ri] 内所有数字进行升序排序。 ,

输出格式

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

输入样例

5
3 4 5 2 1
3
4 5
3 4
1 3

输出样例

1 3 4 5 2


第一次升序排序后,序列为[3,4,5,1,2];

第二次升序排序后,序列为[3,4,1,5,2];

第三次升序排序后,序列为[1,3,4,5,2];

对于全部数据,保证有1≤n≤100,1≤ai≤100,1≤q≤100,1≤li≤ri≤n。

答案与解析
参考答案
#include<bits/stdc++.h>
using namespace std;
const int N = 1010;
int a[N];
int n;
void bubbleSort(int l,int r){
	bool flag = true;
	while (flag) {
		flag = false;
		for (int i = l; i <r; ++i) {
			if (a[i] > a[i + 1]) {
				flag = true;
				swap(a[i],a[i+1]);
			}
		}
	}
}
int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	int q;
	cin>>q;
	while(q--){
		int l,r;
		cin>>l>>r;
		bubbleSort(l,r);
	}
	for(int i=1;i<=n;i++){
		cout<<a[i];
		if(i!=n)cout<<" ";
		else cout<<"\n";
	}
}

将要排序的数据存储在列表中,初始化定义一个长度为1010的数组,尽可能大的数据,确保在输入规模较大的情况下不会越界

定义排序方法对数据进行排序

处理部分:

存储输入数据

处理需要进行排序的区间操作数q

对选定的l,r区间范围内数据进行排序操作,调用之前定义好的排序方法输出结果

题目详情
313 简答题 偏难 GESP编程能力等级认证 ·GESP-C++四级 · 综合练习

黑白方块

时间限制:1.0 s

内存限制:512.0 MB

题面描述

小杨有一个n行m列的网格图,其中每个格子要么是白色,要么是黑色。

对于网格图中的一个子矩形,小杨认为它是平衡的当且仅当其中黑色格子与白色格子数量相同。

小杨想知道最大的平衡子矩形包含了多少个格子。

输入格式

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

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

输出格式

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


输入样例

4 5
00000
01111
00011
00011

输出样例

16

样例解释

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

数据范围

对于全部数据,保证有 1≤n,m≤10。

答案与解析
参考答案
#include<bits/stdc++.h>
using namespace std;
const int N = 55;
int w[N][N];
int n,m;
bool check(int xa,int ya,int xb,int yb){
	int a[2]={0,0};
	for(int i = xa;i<=xb;i++){
		for(int j=ya;j<=yb;j++){
			a[w[i][j]]++;
		}
	}
	
	return a[0]==a[1];
}
int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		string s;
		cin>>s;
		for(int j=1;j<=m;j++){
			w[i][j]=s[j-1]-'0';
		}
	}
	int ans = 0;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			for(int ii=i;ii<=n;ii++){
				for(int jj=j;jj<=m;jj++){
					if(check(i,j,ii,jj)){
						ans = max(ans,(ii-i+1)*(jj-j+1));
					}
				}
			}
		}
	}
	cout<<ans<<"\n";
}

首先解决 “如何判断一个矩阵 a是一个平衡矩阵”这个问题:枚举矩阵中的每一个元素,用两个计数器a[0]、a[1]分别记录0和1的数量,如果最终a[0]==a[1],那么就是平衡矩阵,复杂度是O(n^2)。

然后解决“如何枚举一个矩阵中的所有子矩阵”这个问题:对于任意一个子矩阵,它都有一个起始行、一个终止行、一个起始列和一个终止列,我们可以用4个for循环来分别枚举它们,这样就应该把每个子矩阵确定下来,复杂度是O(n^4)。

如此一来,我们便可以用O(n4)的复杂度枚举每一个子矩阵,然后再花O(n2)的复杂度判断是否是平衡矩阵,总体时间复杂度为O(n^6)。

题目详情
314 简答题 偏难 GESP编程能力等级认证 ·GESP-C++四级 · 综合练习

宝箱

时间限制:1.0 s

内存限制:512.0 MB

题面描述

小杨发现了n个宝箱,其中第i个宝箱的价值是ai。

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

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

输入格式

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

第二行包含n个正整数a1,a2,...,an,代表宝箱的价值。

输出格式

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


输入样例

5 1
1 2 3 1 2

输出样例

7

样例解释

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

数据范围

对于全部数据,保证有1≤n≤1000,0≤k≤1000,1≤ai≤1000。

答案与解析
参考答案
#include<bits/stdc++.h>
using namespace std;
const int N = 1010;
int a[N];
int n,k;
int main(){
	cin>>n>>k;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	sort(a+1,a+n+1);
	int ans=0;
	for(int i=1;i<=n;i++){
		int sum=0;
		for(int j=i;j>=1;j--){
			if(a[i]-a[j]<=k){
				sum+=a[j];
			}else break;
		}
		ans=max(ans,sum);
	}
	cout<<ans<<"\n";
}

比较容易想到的做法是用O(n)的复杂度枚举一个a[i]作为最大值x,然后用O(n)的复杂度枚举另一个值a[j]作为最小值y,最后用O(n)的复杂度枚举数组,计算一下值处于[x,y]的元素总和sum,算出来的总和与ans取最大值即可,但是这样的做法是O(n^3)的,没有办法拿到满分;

我们发现,之所以我们最后需要O(n)的复杂度枚举数组的元素计算总和,是因为我们不知道数值处在[x,y]范围内的元素总和是多少,所以需要枚举计算。

为了解决这个问题,我们可以先将数组从小到大排序,这样一来,数组中的每个子区间[j,i]的左右端点的值a[j]、a[i]分别就对应了我们枚举的最小值x,和最大值y,又因为数组是有序的,因此,数值处于[x,y]范围内的元素正好就是区间[j,i]内的所有元素,这样一来,我们就可以在向前枚举a[j](也就是最小值y)的同时,顺便计算区间[j,i]内的元素总和sum,时间复杂度降为了O(n^2)。


题目详情
315 简答题 偏难 GESP编程能力等级认证 ·GESP-C++四级 · 综合练习

相似字符串

问题描述

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

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

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

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

输入描述

第一行一个正整数T。

接下来T行,每行两个用空格隔开的字符串A和B。

保证T≤100,A,B的长度不超过50。保证A和B只包含小写字母。

输出描述

输出T行,对于每组A,B,如果它们相似,则输出 similar ,否则输出 not similar 。

特别提醒

在常规程序中,输入、输出时提供提示是好习惯。但在本场考试中,由于系统限定,请不要在输入、输出中附带任何提示信息。


样例输入 1

5
apple applee
apple appe
apple bpple
applee bpple
apple apple

样例输出 1

similar
similar
similar
not similar
similar
答案与解析
参考答案
#include <iostream>
#include <string>
using namespace std;
bool isSimilar(string A, string B) {
	int m = A.size(), n = B.size();
	if (abs(m - n) > 1) return false;
	if (m == n) {
		int diff = 0;
		for (int i = 0; i < m; ++i) {
			if (A[i] != B[i]) {
				if (++diff > 1) return false;
			}
		}
		return diff <= 1;
	} else {
		string& shorter = (m < n) ? A : B;
		string& longer = (m < n) ? B : A;
		int i = 0, j = 0;
		int diff = 0;
		while (i < shorter.size() && j < longer.size()) {
			if (shorter[i] != longer[j]) {
				if (++diff > 1) return false;
				++j;
			} else {
				++i;
				++j;
			}
		}
		return true;
	}
}
int main() {
	int T;
	cin >> T;
	while (T--) {
		string A, B;
		cin >> A >> B;
		if (isSimilar(A, B)) {
			cout << "similar" << endl;
		} else {
			cout << "not similar" << endl;
		}
	}
	return 0;
}
题目详情
316 简答题 偏难 GESP编程能力等级认证 ·GESP-C++四级 · 综合练习

做题

题目描述

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

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

那么问题来了,小杨同学最多会做题几天才偷懒呢?

输入格式

第一行,1个数为n,表示有多少套题单。

第二行,n个整数a1,a2,...,an,分别表示每套题单有多少道题。

输出格式

输出一行,小杨同学偷懒前最多做题天数。


样例输入

4
3 1 4 1

样例输出

3

对于全部数据,保证有1≤n≤106,1≤ai≤109。

答案与解析
参考答案
#include<bits/stdc++.h>
#define maxn 1000006
using namespace std;
long long a[maxn];int n;
int main()
{
	int m,ans=0;
	cin>>n;m=n;int s=1;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
	}
	sort(a+1,a+n+1);
	for(int j=1;j<=m;j++)
	{
		for(int k=s;k<=n;k++)
		{
			if(j<=a[k])
			{
				ans++;
				a[k]=j;
				s=k;
				break;
			}
		}
	}
	cout<<ans;
	return 0;
}
题目详情
317 简答题 偏难 GESP编程能力等级认证 ·GESP-C++四级 · 1.3 引用

小杨的字典

时间限制:1.0 s

内存限制:128.0 MB

问题描述

在遥远的星球,有两个国家 A 国和 B 国,他们使用着不同的语言:A 语言和 B 语言。小杨是 B 国的翻译官,他的工作是将 A 语言的文章翻译成 B 语言的文章。

为了顺利完成工作,小杨制作了一本字典,里面记录了 个 A 语言单词对应的 B 语言单词,巧合的是,这些单词都由地球上的 26 个小写英文字母组成。

小杨希望你写一个程序,帮助他根据这本字典翻译一段 A 语言文章。这段文章由标点符号 !()-[]{}\|;:'",./?<> 和一些 A 语言单词构成,每个单词之间必定由至少一个标点符号分割,你的程序需要把这段话中的所有 A 语言单词替换成它的 B 语言翻译。特别地,如果遇到不在字典中的单词,请使用大写 UNK 来替换它。

例如,小杨的字典中包含 2 个 A 语言单词 abc 和 d ,它们的 B 语言翻译分别为 a 和 def ,那么我们可以把 A语言文章 abc.d.d.abc.abcd. 翻译成 B 语言文章 a.def.def.a.UNK. ,其中,单词 abcd 不在词典内,因此我们需要使用 UNK 来替换它。

输入描述

第一行一个整数N,表示词典中的条目数。保证N≤100。

接下来 行,每行两个用单个空格隔开的字符串A,B,分别表示字典中的一个 A 语言单词以及它对应的 B 语言翻译。保证所有A不重复;保证A和B的长度不超过10。

最后一行一个字符串S,表示需要翻译的 A 语言文章。保证字符串 的长度不超过1000,保证字符串S只包含小写字母以及标点符号 !()-[]{}\|;:'",./?<> 。


输出描述

输出一行,表示翻译后的结果。

特别提醒

在常规程序中,输入、输出时提供提示是好习惯。但在本场考试中,由于系统限定,请不要在输入、输出中附带任何提示信息。


样例输入 1

2
abc a
d def
abc.d.d.abc.abcd.

样例输出 1

a.def.def.a.UNK.

样例输入 2

3
abc a
d def
abcd xxxx
abc,(d)d!-abc?abcd

样例输出 2

a,(def)def!-a?xxxx

样例输入 3

1
abcdefghij klmnopqrst
!()-[]{}\|;:'",./?<>abcdefghijklmnopqrstuvwxyz

样例输出 3

!()-[]{}\|;:'",./?<>UNK
答案与解析
参考答案
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <map>
#include <string>

using namespace std;
map<string, string> dict;
int main() {
  int N;
  cin >> N;
  while (N--) {
    string word1, word2;
    cin >> word1 >> word2;
    dict[word1] = word2;
  }
  string content, word = "";
  cin >> content, content += "\n";
  int m = content.length();
  for (int i = 0; i < m; i++) {
    if (content[i] >= 'a' && content[i] <= 'z')
      word += content[i];
    else {
      if (word != "") {
        if (dict.count(word))
          cout << dict[word];
        else
          cout << "UNK";
        word = "";
      }
      cout << content[i];
    }
  }
  return 0;
}
题目详情
318 简答题 偏难 GESP编程能力等级认证 ·GESP-C++四级 · 综合练习

田忌赛马

时间限制:1.0 s

内存限制:128.0 MB

问题描述

你要和田忌赛马。你们各自有N匹马,并且要进行N轮比赛,每轮比赛,你们都要各派出一匹马决出胜负。

你的马匹的速度分别为u1,u2,…,uN,田忌的马匹的速度分别为v1,v2,…,vN。田忌会按顺序派出他的马匹,请问你要如何排兵布阵,才能赢得最多轮次的比赛?巧合的是,你和田忌的所有马匹的速度两两不同,因此不可能出现平局。

输入描述

第一行一个整数 。保证1≤N≤5×104。

接下来一行N个用空格隔开的整数,依次为u1,u2,…,uN,表示你的马匹们的速度。保证1≤ui≤2N。

接下来一行N个用空格隔开的整数,依次为v1,v2,…,vN,表示田忌的马匹们的速度。保证1≤vi≤2N。

输出描述

输出一行,表示你最多能获胜几轮。

特别提醒

在常规程序中,输入、输出时提供提示是好习惯。但在本场考试中,由于系统限定,请不要在输入、输出中附带任何提示信息。


样例输入 1

3
1 3 5
2 4 6

样例输出 1

2

样例解释 1

第 1 轮,田忌派出速度为2的马匹,你可以派出速度为3的马匹迎战,本轮你获胜。

第 2 轮,田忌派出速度为4的马匹,你可以派出速度为5的马匹迎战,本轮你获胜。

第 3 轮,田忌派出速度为6的马匹,你可以派出速度为1的马匹迎战,本轮田忌获胜。

如此,你可以赢得 2 轮比赛。


样例输入 2

5
10 3 5 8 7
4 6 1 2 9

样例输出 2

5
答案与解析
参考答案
#include <bits/stdc++.h>
using namespace std;
const int N = 100005;
int a[N], t;
int b[N], h;
int n;
int main() {
  scanf("%d", &n);
  for (int i = 1; i <= n; ++i) {
    scanf("%d", &a[i]);
  }
  for (int i = 1; i <= n; ++i) {
    scanf("%d", &b[i]);
  }
  h = 1;
  t = 0;
  sort(a + 1, a + n + 1);
  sort(b + 1, b + n + 1);
  int ans = 0;
  for (int i = 1; i <= n; ++i)
    if (a[i] > b[h])
      ++ans, ++h;
  printf("%d\n", ans);
  return 0;
}
题目详情
319 简答题 偏难 GESP编程能力等级认证 ·GESP-C++四级 · 综合练习

进制转换(2023年9月C++四级))

时间限制:1.0 s

内存限制:128.0 MB

问题描述

N进制数指的是逢N进一的计数制。例如,人们日常生活中大多使用十进制计数,而计算机底层则一般使用二进制。除此之外,八进制和十六进制在一些场合也是常用的计数制(十六进制中,一般使用字母 A 至 F 表示十至十五;本题中,十一进制到十五进制也是类似的)。

在本题中,我们将给出N个不同进制的数。你需要分别把它们转换成十进制数。

提示

对于任意一个L位K进制数,假设其最右边的数位为第0位,最左边的数位为第L-1位,我们只需要将其第i位的数码乘以权值Ki ,再将每位的结果相加,即可得到原K进制数对应的十进制数。下面是两个例子:

1. 八进制数 1362 对应的十进制数为1×83+3×82+6×81+2×80=754 ;

2. 十六进制数 3F0 对应的十进制数为 3×162+15×161+0×160=1008。

输入描述

输入的第一行为一个十进制表示的整数N。接下来N行,每行一个整数K,随后是一个空格,紧接着是一个K进制数,表示需要转换的数。保证所有 进制数均由数字和大写字母组成,且不以 0 开头。保证K进制数合法。

保证N≤1000;保证2≤K≤16

保证所有K进制数的位数不超过9。

 输出描述

输出N行,每一个十进制数,表示对应K进制数的十进制数值。

特别提醒

在常规程序中,输入、输出时提供提示是好习惯。但在本场考试中,由于系统限定,请不要在输入、输出中附带任何提示信息。


样例输入 1

2

8 1362

16 3F0

样例输出 1

754

1008

样例输入 2

2

2 11011

10 123456789

样例输出 2

27

123456789

答案与解析
参考答案
#include <iostream>
#include <cstring>
using namespace std;

int trans_digit(int k, char c) {
	if (c <= '9')
		return (c - '0');
	return (c - 'A' + 10);
}
long long trans(int k, char str[]) {
	int l = strlen(str);
	long long res = 0, pw = 1;
	for (int i = l - 1; i >= 0; i--) {
		res += pw * trans_digit(k, str[i]);
		pw *= k;
	}
	return res;
}
int main() {
	int n = 0;
	cin >> n;
	for (int t = 0; t < n; t++) {
		int k = 0;
		char str[10];
		cin >> k >> str;
		cout << trans(k, str) << endl;
	}
	return 0;
}


题目详情
320 简答题 偏难 GESP编程能力等级认证 ·GESP-C++四级 · 综合练习

变长编码(2023年9月C++四级)

时间限制:1.0 s

内存限制:128.0 MB

问题描述

小明刚刚学习了三种整数编码方式:原码、反码、补码,并了解到计算机存储整数通常使用补码。但他总是觉得,生活中很少用到231-1这么大的数,生活中常用的0~100这种数也同样需要用4个字节的补码表示,太浪费了些。

热爱学习的小明通过搜索,发现了一种正整数的变长编码方式。这种编码方式的规则如下:

1. 对于给定的正整数,首先将其表达为二进制形式。例如,(0) {10}=(0) {2},(926) {10}=(1110011110) {2} 。

2. 将二进制数从低位到高位切分成每组7bit,不足 bit的在高位用0填补。例如, (0) {2}变为0000000的一组,(1110011110) {2}变为0011110和0000111的两组。

3. 由代表低位的组开始,为其加入最高位。如果这组是最后一组,则在最高位填上0,否则在最高位填上1。于是,0的变长编码为00000000一个字节,926的变长编码为10011110和00000111两个字节。

这种编码方式可以用更少的字节表达比较小的数,也可以用很多的字节表达非常大的数。例如,987654321012345678的二进制为(0001101 1011010 0110110 1001011 1110100 0100110 1001000 0010110 1001110) {2},于是它的变长编码为(十六进制表示) CE 96 C8 A6 F4 CB B6 DA 0D ,共9个字节。

你能通过编写程序,找到一个正整数的变长编码吗?

输入描述

输入第一行,包含一个正整数N。约定 0≤N≤1018。


输出描述

输出一行,输出N对应的变长编码的每个字节,每个字节均以2位十六进制表示(其中,A-F使用大写字母表示),两个字节间以空格分隔。

样例输入1

0

样例输出1

00

样例输入2

926

样例输出2

9E 07

样例输入3

987654321012345678

样例输出3

CE 96 C8 A6 F4 CB B6 DA 0D

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

void output_digit(int d) {
	if (d >= 10)
		cout << (char)('A' + d - 10);
	else
		cout << (char)('0' + d);
}
void output_code(int s) {
	output_digit(s >> 4);
	output_digit(s & 0x0f);
}
int main() {
	long long n = 0;
	cin >> n;
	int split[10];
	int l = 0;
	while (n > 0) {
		split[l] = (int)(n & 0x7f);
		n >>= 7;
		l++;
	}
	for (int i = 0; i < l - 1; i++)
		split[i] |= 0x80;
	output_code(split[0]);
	for (int i = 1; i < l; i++) {
		cout << " ";
		output_code(split[i]);
	}
	cout << endl;
	return 0;
}


题目详情