GESPC++2024.9四级编程题题解
2025-09-24 18:25:44
发布于：广东
GESP-C++2024.9 四级编程题题解来啦！
1.
时间限制：1000ms
内存限制：512MB
小杨有一个n行m列的网格图，其中每个格子要么是白色，要么是黑色。
小杨想知道网格图中是否存在一个满足如下条件的子矩形：
⋅ 子矩形由4行4列组成；
⋅ 子矩形的第1行和第4行只包含白色格子；
⋅ 对于子矩形的第2行和第3行，只有第1个和第4个格子是白色的，其余格子都是黑色的；
请你编写程序帮助小杨判断。
输入格式
第一行包含一个正整数t，代表测试用例组数。
接下来是t组测试用例。对于每组测试用例，一共n+1行。
第一行包含两个正整数n,m含义如题面所示。
之后n行，每行一个长度为m的01串，代表网格图第i行格子的颜色，如果为0，则对应格子为白色，否则为黑色。
输出格式
对于每组测试用例，如果存在，输出 Yes，否则输出 No。
样例组
输入#1
3
1 4
0110
5 5
00000
01100
01100
00001
01100
5 5
00000
01100
01110
00001
01100
输出#1
No
Yes
No
提示说明
满足条件的子矩形形如：
0000
0110
0110
0000
对于全部数据，保证有1≤t≤10,1≤n,m≤100。
题解：
#include<bits/stdc++.h>
using namespace std;
int a[110][110];
//定义检查函数check
bool check(int x,int y){
for(int i = 0;i <=3;i++){
if(a[x][y+i]) return 0;
if(a[x+3][y+i]) return 0;
}
for(int i = 0;i <= 3;i++){
if(a[x+1][y+i] == 0 && (i == 1 || i == 2)) return 0;
if(a[x+2][y+i] == 0 && (i == 1 || i == 2)) return 0;
if(a[x+1][y+i] == 1 && (i == 0 || i == 3)) return 0;
if(a[x+2][y+i] == 1 && (i == 0 || i == 3)) return 0;
}
return 1;
}
int main(){
int q;
cin >> q;
while(q--){
int n,m;
cin >> n >> m;
memset(a,0,sizeof(a));
//输入
for(int i = 1;i <= n;i++){
string s;
cin >> s;
for(int j = 1;j <= m;j++){
a[i][j] = s[j-1] - '0';
}
}
bool flag = false;
//使用暴力枚举法枚举每种可能
for(int x = 1;x <= n - 3;x++){
for(int y = 1;y <= m - 3;y++){
//使用check检查
if(check(x,y)){
flag = true;
}
}
}
//输出
if(flag) cout << "Yes\n";
else cout << "No\n";
}
return 0;
}
时间限制：1000ms
内存限制：512MB
小杨有一个包含n个正整数的序列a。
小杨计划对序列进行多次升序排列，每次升序排序小杨都会选择一个区间l,r并对区间内所有数字，即a
l ,a l+1,...,a r
进行升序排序。每次升序排序会在上一次升序排序的结果上进行。
小杨想请你计算出多次升序排序后的序列。
输入格式
第一行包含一个正整数t，含义如题面所示。
第二行包含n个正整数a 1,a 2,...,a n ，代表序列
第三行包含一个正整数q，代表排序次数。
之后q行，每行包含两个正整数l i,r i ，代表将区间[l i,r i
]内所有数字进行升序排序。
输出格式
输出一行包含n个正整数，代表多次升序排序后的序列。
样例组
输入#1
5
3 4 5 2 1
3
4 5
3 4
1 3
输出#1
1 3 4 5 2
提示说明
样例解释：
⋅ 第一次升序排序后，序列为[3,4,5,1,2]；
⋅ 第二次升序排序后，序列为[3,4,1,5,2]；
⋅ 第三次升序排序后，序列为[1,3,4,5,2]；
对于全部数据，保证有1≤n≤100,1≤a
i≤100,1≤q≤100,1≤l
i≤r i≤n。
#include<bits/stdc++.h>
using namespace std;
int a[110];
int main(){
int n;
cin >> n;
//输入数组
for(int i = 1;i <= n;i++){
cin >> a[i];
}
int q;
cin >> q;
while(q--){
int l,r;
cin >> l >> r;
//升序排序区间
sort(a + l,a + r + 1);
}
//输出
for(int i = 1;i <= n;i++){
cout << a[i] << " ";
}
return 0;
}
这里空空如也
有帮助，赞一个