GESP-C++四级 题库
建造
时间限制: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)的高度。数据保证总存在一个适合建造停机坪的区域。
输出格式
输出一行,代表最大的海拔之和。
输入样例
输出样例
数据范围

#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;
}优先购买
时间限制:1.0 s
内存限制:512.0 MB
题目描述
小 A 有M元预算。商店有N个商品,每个商品有商品名S 、价格P和优先级V三种属性,其中V为正整数,且V越小代表商品的优先级越高。
小 A 的购物策略为:
总是优先买优先级最高的东西;
如果有多个最高优先级商品,购买价格最低的;
如果有多个优先级最高且价格最低的商品,购买商品名字典序最小的。
小 A 想知道能购买哪些商品。
输入格式
第一行两个正整数 M,N,代表预算和商品数。
之后N行,每行一个商品,依次为Si,Pi,Vi ,代表第 个商品的商品名、价格、优先级。数据保证不存在两个名字相同的商品。
输出格式
按照字典序从小到大的顺序,输出所有购买商品的商品名。
输入样例
输出样例
数据范围
对于所有测试点,保证
商品名仅由小写字母组成且不存在两个相同的商品名。
#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;
}排兵布阵


#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;
}最长连续段


#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;
}画布裁剪
时间限制: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】
【样例输出1】
【样例输入2】
【样例输出2】
【数据范围】
对于所有测试点,保证 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;
}排序
时间限制:1 s,内存限制:512 MB
【问题描述】
体育课上有 n 名同学排成一队,从前往后数第 i 位同学的身高为 hi,体重为 wi。
目前排成的队伍看起来参差不齐,老师希望同学们能按照身高从高到低的顺序排队,如果身高相同则按照体重从重到轻排序。
在调整队伍时,每次只能交换相邻两位同学的位置。老师想知道,最少需要多少次交换操作,才能将队伍调整成目标顺序。
【输入描述】
第一行,一个正整数 n,表示队伍人数。
接下来 n 行,每行两个正整数 hi 和 wi,分别表示第 i 位同学的身高和体重。
【输出描述】
输出一行,一个整数,表示最少需要的交换次数。
【样例输入1】
【样例输出1】
【样例输入2】
【样例输出2】
【数据范围】
对于所有测试点,保证 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;
}荒地开垦
时间限制: 1.0 s
内存限制 :512.0 MB
题面描述
小杨有—大片荒地,可以表⽰为—个n行m列的网格图。
小杨想要开垦这块荒地,但荒地中—些位置存在杂物,对于—块不存在杂物的荒地,该荒地可以开垦当且仅当其 上、下、左、右四个方向相邻的格子均不存在杂物。
小杨可以选择至多—个位置,清除该位置的杂物,移除杂物后该位置变为荒地。小杨想知道在清除至多—个位置的 杂物的情况下,最多能够开垦多少块荒地。
输入格式
第—行包含两个正整数 n , m ,含义如题面所⽰。
之后 n 行,每行包含—个长度为 m 且仅包含字符 . 和 # 的字符串。如果为 . ,代表该位置为荒地;如果为# ,代表该位置为杂物。
输出格式
输出—个整数,代表在清除至多—个位置的杂物的情况下,最多能够开垦的荒地块数。
输入样例
输出样例
样例解释
移除第二行从左数第二块空地的杂物后:
第—行从左数前 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数组中的最大值,就是我们要移除杂物的位置,把最大值更新到答案中就是我们要 的最终答案。
二阶矩阵
题目描述
小 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
输出格式
—行, —个整数,表⽰ 中好的子矩阵的数量。
输入样例
输出样例
数据范围
对于所有测试点,保证 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;
}按照题目的公式,对输入矩阵进行暴力循环,统计答案个数即可。
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
输出样例 1
输入样例 2
输出样例 2
样例解释
对于样例 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;
}字符排序
时间限制: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。
输入样例
输出样例
样例解释
对于第一组测试数据,一种可行的排列顺序为 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";
}
}黑白方块
时间限制: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。
输入样例
输出样例
满足条件的子矩形形如:
对于全部数据,保证有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)开始的子矩形是否与之前定义好的模版匹配进行判断,输出结果
区间排序
时间限制: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个正整数,代表多次升序排序后的序列。
输入样例
输出样例
第一次升序排序后,序列为[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区间范围内数据进行排序操作,调用之前定义好的排序方法输出结果
黑白方块
时间限制:1.0 s
内存限制:512.0 MB
题面描述
小杨有一个n行m列的网格图,其中每个格子要么是白色,要么是黑色。
对于网格图中的一个子矩形,小杨认为它是平衡的当且仅当其中黑色格子与白色格子数量相同。
小杨想知道最大的平衡子矩形包含了多少个格子。
输入格式
第一行包含两个正整数n,m,含义如题面所示。
之后n行,每行一个长度为m的01串,代表网格图第i行格子的颜色,如果为0,则对应格子为白色,否则为黑色。
输出格式
输出一个整数,代表最大的平衡子矩形包含格子的数量,如果不存在则输出0。
输入样例
输出样例
样例解释
对于样例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)。
宝箱
时间限制:1.0 s
内存限制:512.0 MB
题面描述
小杨发现了n个宝箱,其中第i个宝箱的价值是ai。
小杨可以选择一些宝箱放入背包并带走,但是小杨的背包比较特殊,假设小杨选择的宝箱中最大价值为x,最小价值为y,小杨需要保证x−y≤k,否则小杨的背包会损坏。
小杨想知道背包不损坏的情况下,自己能够带走宝箱的总价值最大是多少。
输入格式
第一行包含两个正整数n,k,含义如题面所示。
第二行包含n个正整数a1,a2,...,an,代表宝箱的价值。
输出格式
输出一个整数,代表带走宝箱的最大总价值。
输入样例
输出样例
样例解释
在背包不损坏的情况下,小杨可以拿走两个价值为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)。
相似字符串
问题描述
对于两个字符串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
样例输出 1
#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;
}做题
题目描述
小杨同学为了提高自己的实力制定了做题计划,在第k天时,他必须要完成k道题,否则他就会偷懒。
小杨同学现在找到了一个题库,一共有n套题单,每一套题单中有一定数量的题目。但是他十分挑剔,每套题单他只会使用一次,每一天也只能使用一套题单里的题目,之后那套题单就会被弃之不用。对于每套题单,他不必完成题单内所有的题。
那么问题来了,小杨同学最多会做题几天才偷懒呢?
输入格式
第一行,1个数为n,表示有多少套题单。
第二行,n个整数a1,a2,...,an,分别表示每套题单有多少道题。
输出格式
输出一行,小杨同学偷懒前最多做题天数。
样例输入
样例输出
对于全部数据,保证有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;
}小杨的字典
时间限制: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
样例输出 1
样例输入 2
样例输出 2
样例输入 3
样例输出 3
#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;
}田忌赛马
时间限制: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
样例输出 1
样例解释 1
第 1 轮,田忌派出速度为2的马匹,你可以派出速度为3的马匹迎战,本轮你获胜。
第 2 轮,田忌派出速度为4的马匹,你可以派出速度为5的马匹迎战,本轮你获胜。
第 3 轮,田忌派出速度为6的马匹,你可以派出速度为1的马匹迎战,本轮田忌获胜。
如此,你可以赢得 2 轮比赛。
样例输入 2
样例输出 2
#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;
}进制转换(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;
}变长编码(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;
}