首页 › 题库 › GESP编程能力等级认证 › 综合练习

GESP-C++四级 题库

共 77 道题 ,第 4 / 4 页 · 按题型筛选,点「查看答案」核对解析
61 判断题 偏易 GESP编程能力等级认证 ·GESP-C++四级 · 综合练习

字符常量'0'和'\0'是等价的。

A
对
B
错
答案与解析
正确答案:错
这道题暂未补解析。
题目详情
62 简答题 偏难 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;
}
题目详情
63 简答题 偏难 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;
}
题目详情
64 简答题 偏难 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;
}
题目详情
65 简答题 偏难 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数组中的最大值,就是我们要移除杂物的位置,把最大值更新到答案中就是我们要 的最终答案。

题目详情
66 简答题 偏难 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;
}
题目详情
67 简答题 偏难 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)开始的子矩形是否与之前定义好的模版匹配进行判断,输出结果

题目详情
68 简答题 偏难 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区间范围内数据进行排序操作,调用之前定义好的排序方法输出结果

题目详情
69 简答题 偏难 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)。

题目详情
70 简答题 偏难 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)。


题目详情
71 简答题 偏难 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;
}
题目详情
72 简答题 偏难 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;
}
题目详情
73 简答题 偏难 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;
}
题目详情
74 简答题 偏难 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;
}


题目详情
75 简答题 偏难 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;
}


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

幸运数

【问题描述】

小明发明了一种“幸运数”。一个正整数,其偶数位不变(个位为第 1 位,十位为第 2 位,以此类推),奇数位做如下变换:将数字乘以 7,如果不大于 9则作为变换结果,否则把结果的各位数相加,如果结果不大于 9 则作为变换结果,否则(结果仍大于 9)继续把各位数相加,直到结果不大于 9,作为变换结果。变换结束后,把变换结果的各位数相加,如果得到的和是 8 的倍数,则称一开始的正整数为幸运数。

例如,16347:第 1 位为 7,乘以 7 结果为 49,大于 9,各位数相加为 13,仍大于 9,继续各位数相加,最后结果为 4;第 3 位为 3,变换结果为 3;第 5位为 1,变换结果为 7。最后变化结果为 76344,对于结果 76344 其各位数之和为 24,是 8 的倍数。因此 16347 是幸运数。

【输入描述】

输入第一行为正整数N,表示有N个待判断的正整数。约定 1 ≤N≤ 20。

从第 2 行开始的N行,每行一个正整数,为待判断的正整数。约定这些正整数小于1012。

【输出描述】

输出N行,对应N个正整数是否为幸运数,如是则输出'T',否则输出'F'。

提示:不需要等到所有输入结束在依次输出,可以输入一个数就判断一个数并输出,再输入下一个数。


【样例输入 1】

2
16347
76344

【样例输出 1】

T
F


答案与解析
参考答案
#include <iostream>
using namespace std;
// 奇数位要做的数字变换
int trans(int t) {
	if (t == 0)
		return 0;
	return (t * 7 - 1) % 9 + 1;
}
// 判断是否为幸运数
bool judge(long long x) {
	int sum = 0;
	for (int d = 1; x > 0; d++, x /= 10) {
		int t = (int)(x % 10);
		if (d % 2 == 0)
			sum += t;
		else
			sum += trans(t);
	}
	return (sum % 8 == 0);
}
int main() {
	int N = 0;
	cin >> N;
	for (int n = 0; n < N; n++) {
		long long x = 0;
		cin >> x;
		if (judge(x))
			cout << "T" << endl;
		else
			cout << "F" << endl;
	}
	return 0;
}


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

图像压缩

【问题描述】

图像是由很多的像素点组成的。如果用 0 表示黑,255 表示白,0 和 255 之间的值代表不同程度的灰色,则可以用一个字节表达一个像素(取值范围为十进制 0-255、十六进制 00-FF)。这样的像素组成的图像,称为 256 级灰阶的灰度图像。

现在希望将 256 级灰阶的灰度图像压缩为 16 级灰阶,即每个像素的取值范围为十进制 0-15、十六进制 0-F。压缩规则为:统计出每种灰阶的数量,取数量最多的前 16 种灰阶(如某种灰阶的数量与另外一种灰阶的数量相同,则以灰阶值从小到大为序),分别编号 0-F(最多的编号为 0,以此类推)。其他灰阶转换到最近的 16 种灰阶之一,将某个点灰阶数与 16 种灰阶种的一种相减,绝对值最小即为最近,如果绝对值相等,则编号较小的灰阶更近。

【输入描述】

输入第 1 行为一个正整数N,表示接下来有N行数据组成一副 256 级灰阶的灰度图像。约定 10 ≤ N≤ 20。

第 2 行开始的N行,每行为长度相等且为偶数的字符串,每两个字符用十六进制表示一个像素。约定输入的灰度图像至少有 16 种灰阶。约定每行最多 20个像素。

【输出描述】

第一行输出压缩选定的 16 种灰阶的十六进制编码,共计 32 个字符。

第二行开始的N行,输出压缩后的图像,每个像素一位十六进制数表示压缩后的灰阶值。


【样例输入 1】

10
00FFCFAB00FFAC09071B5CCFAB76
00AFCBAB11FFAB09981D34CFAF56
01BFCEAB00FFAC0907F25FCFBA65
10FBCBAB11FFAB09981DF4CFCA67
00FFCBFB00FFAC0907A25CCFFC76
00FFCBAB1CFFCB09FC1AC4CFCF67
01FCCBAB00FFAC0F071A54CFBA65
10EFCBAB11FFAB09981B34CFCF67
01FFCBAB00FFAC0F071054CFAC76
1000CBAB11FFAB0A981B84CFCF66

【样例输出 1】

ABCFFF00CB09AC07101198011B6776FC
321032657CD10E
36409205ACC16D
B41032657FD16D
8F409205ACF14D
324F326570D1FE
3240C245FC411D
BF4032687CD16D
8F409205ACC11D
B240326878D16E
83409205ACE11D

【样例解释 1】

灰阶‘AB’、‘CF’和‘FF’出现 14 次,‘00’出现 10 次,‘CB’出现9 次,‘09’出现 7 次,‘AC’出现 6 次,‘07’出现 5 次,‘10’、‘11’和‘98’出现 4 次,‘01’、‘1B’、‘67’、‘76’和‘FC’出现 3 次。

答案与解析
参考答案
#include <iostream>
#include <cstring>
using namespace std;
int image[20][20];
int cpimg[20][20];
int his[256];
int color[16];
// 一位十六进制字符转换为数字
int trans(char a) {
	if (a <= '9')
		return (a - '0');
	return (a - 'A' + 10);
}
// 一位十六进制数字转换为字符
char itrans(int n) {
	if (n >= 10)
		return (char)(n - 10 + 'A');
	return (char)(n + '0');
}
// 寻找离 c 最近的灰阶
int compress(int c) {
	int dis = 256, res = -1;
	for (int i = 0; i < 16; i++) {
		int d = c - color[i];
		if (d < 0)
			d = -d;
		if (d < dis) {
			dis = d;
			res = i;
		}
	}
	return res;
}
int main() {
	int N = 0, M = 0;
	cin >> N;
	// 灰阶计数,初始化为-1
	for (int i = 0; i < 256; i++)
		his[i] = -1;
	// 输入图像,并对灰阶计数
	for (int i = 0; i < N; i++) {
		char line[50];
		cin >> line;
		M = strlen(line) / 2;
		for (int j = 0; j < M; j++) {
			int c = trans(line[j * 2]) * 16 + trans(line[j * 2 + 1]);
			image[i][j] = c;
			his[c]++;
		}
	}
	// 选取出现次数最多的 16 个灰阶
	for (int c = 0; c < 16; c++) {
		int max = 0, max_id = -1;
		for (int i = 0; i < 256; i++)
			if (his[i] > max) {
				max = his[i];
				max_id = i;
			}
		color[c] = max_id;
		his[max_id] = -1;
	}
	// 将 image 的灰阶压缩为 cpimg
	for (int i = 0; i < N; i++)
		for (int j = 0; j < M; j++)
			cpimg[i][j] = compress(image[i][j]);
	// 输出选取的 16 个灰阶
	for (int c = 0; c < 16; c++)
		cout << itrans(color[c] / 16) << itrans(color[c] % 16);
	cout << endl;
	// 输出压缩后的图像
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++)
			cout << itrans(cpimg[i][j]);
		cout << endl;
	}
	return 0;
}


题目详情