广深营7月一期X02复赛模拟赛5全题解！
2024-07-20 21:25:06
发布于：广东
29阅读
0回复
0点赞
T1
我们都知道，平方后个位等于自己的只有0156四个数字，所以秒了
n = int(input())
a = [0, 1, 5, 6]
if n in a:
print(n, 'is right number')
else:
print(n, 'is error number')
T2
简单贪心，排个序，能够到的就采
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
struct node{
int height, tili;
}a[5005];
int ct, ctt;
bool cmp(node a, node b){
return a.tili < b.tili;
}
int main(){
int n, m, aa, b, x, y;
cin >> n >> m >> aa >> b;//远古代码，见谅
b += aa;
for(int i = 1; i <= n; i++){
cin >> x >> y;
if(x <= b){
a[++ct].height = x;
a[ct].tili = y;
}
}sort(a + 1, a + ct + 1, cmp);
for(int i = 1; i <= ct; i++){
if(m >= a[i].tili){
ctt++;
m -= a[i].tili;
}else break;
}cout << ctt;
return 0;
}
T3
二分查找，注意由于输入输出较大，可以使用快读快写，这里我偷懒用了printf
#include <iostream>
#include <cstdio>
using namespace std;
int a[1000005];
int x;
int check(int left, int right){
if(a[left] == x) return left;
if(a[left] > x || a[right] < x) return 0x3f3f3f3f;
return 0;
}
int find(int left, int right){//分治查找，只要保证左右两边只留一个就可以做到O(logn)
if(check(left, right)) return check(left, right);
if(left == right) return left;
int mid = (left + right) / 2;
return min(find(left, mid), find(mid + 1, right));
}
int read(){//快读模版
char c = getchar();
int x = 0;
while(!isdigit(c)) c = getchar();
while(isdigit(c)){
x = (x << 3) + (x << 1) + c - '0';
c = getchar();
}
return x;
}
int main(){
int n = read(), m = read();
for(int i = 1; i <= n; i++){
a[i] = read();
}
while(m--){
x = read();
int f = find(1, n, check_);
printf("%d ", (f == 0x3f3f3f3f ? -1 : f));
}
return 0;
}
T4
一眼二分，只要知道check函数套模版秒了
#include <iostream>
#include <cstdio>
#define int long long
using namespace std;
signed a[100005];
int n, m;
int check(int x){
int ct = 0;
for(int i = 1; i <= n; i++){
ct += a[i] / x + (a[i] % x >= 1);//吃每个香蕉的时间，注意向上取整
}
return ct <= m;
}
signed main(){
cin >> n >> m;
int ct = 0;
for(int i = 1; i <= n; i++){
cin >> a[i];
ct += a[i];
}
int l = 1, r = ct;
while(l <= r){
int mid = (l + r) >> 1;
if(check(mid)) r = mid - 1;
else l = mid + 1;
}
cout << l;
return 0;
}
T5
这个也是二分，贪心方法就是基础数学，长除n宽除n乘起来（本来想到一道题，但找不到了）
#include <iostream>
#include <cstdio>
#define int long long
using namespace std;
struct node{
int h, w;
}a[100005];
int n, m;
int check(int x){
int ct = 0;
for(int i = 1; i <= n; i++){
ct += (a[i].h / x) * (a[i].w / x);
}
return ct >= m;
}
signed main(){
cin >> n >> m;
int ct = 0;
for(int i = 1; i <= n; i++){
cin >> a[i].h >> a[i].w;
ct += a[i].h * a[i].w;
}
int l = 1, r = ct;
while(l <= r){
int mid = (l + r) >> 1;
if(check(mid)) l = mid + 1;
else r = mid - 1;
}
cout << l - 1;
return 0;
}
T6
区域问题，深搜广搜均可，这里选深搜省事
#include <iostream>
#include <cstdio>
using namespace std;
char a[105][105];
bool vis[105][105];
int dir[][2] = {-1, 0, 0, -1, 0, 1, 1, 0};
int kind[10];
int n, m;
bool check(int x, int y, char c){
if(x < 1 || x > n) return 0;
if(y < 1 || y > m) return 0;
if(vis[x][y]) return 0;
if(a[x][y] != c) return 0;//必须相同颜色
return 1;
}
void dfs(int x, int y, char c){
vis[x][y] = 1;
for(int i = 0; i < 4; i++){
int xx = x + dir[i][0], yy = y + dir[i][1];
if(check(xx, yy, c)) dfs(xx, yy, c);
}
}
int main(){
cin >> n >> m;
for(int i = 1; i <= n; i++){
scanf("%s", a[i] + 1);//输入可以学一下，直接输入字符串
}
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++){
if(!vis[i][j]){//没有遍历到就说明是不同区域
kind[a[i][j] - '0']++;
dfs(i, j, a[i][j]);
}
}
}
for(int i = 1; i <= 9; i++){
cout << kind[i] << ' ';
}
return 0;
}
T7
广搜
#include <iostream>
#include <cstdio>
#include <queue>
using namespace std;
struct Point{
int x, y, step;
};
int n, m, x, y;
int vis[405][405];
char mp[405][405];
int dir[8][2] = {-2, -1, -2, 1, -1, -2, -1, 2, 1, -2, 1, 2, 2, -1, 2, 1};
queue <Point> q;//也是远古代码，现在都用node
bool check(int x, int y){
if(x < 1 || x > n) return 0;
if(y < 1 || y > m) return 0;
if(vis[x][y]) return 0;
return 1;
}
void bfs(int x, int y){
vis[x][y] = 114514;
q.push({x, y, 0});
while(!q.empty()){
Point head = q.front();
for(int i = 0; i < 8; i++){
int xx = head.x + dir[i][0], yy = head.y + dir[i][1];
if(check(xx, yy)){
q.push({xx, yy, head.step + 1});
vis[xx][yy] = head.step + 1;
}
}q.pop();
}
}
int main(){
cin >> n >> m >> x >> y;
bfs(x, y);
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++){
if(vis[i][j] == 114514) cout << 0 << ' ';
else if(vis[i][j] == 0) cout << -1 << ' ';
else cout << vis[i][j] << ' ';
}cout << endl;
}
return 0;
}
T8
广搜，这里我和八皇后一样在node内加了vis数组记录
#include <iostream>
#include <cstdio>
#include <queue>
using namespace std;
struct node{
bool vis[15];
int cur = 0, step = 0;
};
char a[15][15];
int n, m;
int bfs(){
queue <node> q;
node nd;
q.push(nd);
while(!q.empty()){
node head = q.front();
q.pop();
bool flag = 1;
for(int i = 1; i <= m; i++){
if(!head.vis[i]){
flag = 0;
break;
}
}
if(flag) return head.step;
for(int i = head.cur + 1; i <= n; i++){
node tmp = head;
tmp.step++;
tmp.cur = i;
for(int j = 1; j <= m; j++){
if(a[i][j] == 'o') tmp.vis[j] = 1;//有卖的话更新vis
}
q.push(tmp);
}
}
return -1;
}
int main(){
cin >> n >> m;
for(int i = 1; i <= n; i++){
scanf("%s", a[i] + 1);
}
cout << bfs();
return 0;
}
T9
没想到已经过了八九天了，see you again~
print('see you')
有帮助，赞一个