牛客小白月赛99部分题解

比赛地址：牛客小白月赛99_ACM/NOI/CSP/CCPC/ICPC算法编程高难度练习赛_牛客竞赛OJ

A.材料打印

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;void solve() {ll a,b,c,d;cin>>a>>b>>c>>d;if(c<d)cout<<a*c+b*d<<endl;else{cout<<(a+b)*d<<endl;}}signed main() {int t;cin >> t;while (t--) {solve();}
} 

B.%%%

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;void solve() {ll n,cnt;cin>>n;if(n==0){cout<<0<<endl;return;}while(1){if(n==0){cout<<cnt<<endl;return;}if (n & 1){n = n % ((n + 1) / 2);}else {n = n % (n / 2 + 1);}cnt++;}
}signed main() {int t;cin >> t;while (t--) {solve();}
} 

C.迷宫

这题有点难绷，前面一直超时

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int map1[1010][1010];
bool visited[1010][1010];
bool logs[1010][1010];
ll a,b;
int direction[4][2]={{0,1},{1,0},{-1,0},{0,-1}};
queue<pair<int,int> > q;
bool dfs(int x, int y, int end_x, int end_y) {// 如果当前位置超出了边界或已经访问过，返回 falseif (x < 1 || x > a || y < 1 || y > b || visited[x][y] || map1[x][y] != 1) {return false;}// 如果当前位置是终点，返回 trueif (x == end_x && y == end_y) {return true;}// 标记当前位置为已访问visited[x][y] = true;// 尝试四个方向移动if (dfs(x - 1, y, end_x, end_y)) return true; // 上if (dfs(x + 1, y, end_x, end_y)) return true; // 下if (dfs(x, y - 1, end_x, end_y)) return true; // 左if (dfs(x, y + 1, end_x, end_y)) return true; // 右// 如果没有找到路径，回溯return false;
}
void dfs1(int x, int y,int key) {if (x < 1 || x > a || y < 1 || y > b || visited[x][y] || map1[x][y] == 2) {return;}if (map1[x][y]==1) {if(key){map1[x][y]=9;}else{q.push({x,y});}}// 标记当前位置为已访问visited[x][y] = true;// 尝试四个方向移动dfs1(x - 1, y,key);dfs1(x + 1, y,key);dfs1(x, y - 1,key);dfs1(x, y + 1,key);
}
void solve() {ll c,d;cin>>a>>b;char s;memset(map1,0,sizeof(map1));int numx,numy,end_x,end_y;for(c=1;c<=a;c++){for(d=1;d<=b;d++){cin>>s;if(s=='.'){map1[c][d]=1;}else if(s=='#'){map1[c][d]=2;}else if(s=='S'){numx=c;numy=d;map1[c][d]=1;}else if(s=='E'){end_x=c;end_y=d;map1[c][d]=1;}}}if(dfs(numx,numy,end_x,end_y)){cout<<"YES";return;}memset(visited,0,sizeof(visited));dfs1(end_x,end_y,0);memset(visited,0,sizeof(visited));dfs1(numx,numy,1);/*for(c=1;c<=a;c++){for(d=1;d<=b;d++){cout<<map1[c][d];}cout<<endl;}*/memset(logs,0,sizeof(logs));while(!q.empty()){pair<int,int> i1=q.front();int num1=i1.first;int num2=i1.second;q.pop();if(logs[num1][num2]){}else{logs[num1][num2]=1;}int x,y,x1,y1;for(int v1=0;v1<=3;v1++){		x=num1+direction[v1][0];y=num2+direction[v1][1];//左 if(logs[x][y]){continue;}else{logs[x][y]=1;}x1=x;y1=y;while(x1>=1&&y1>=1&&x1<=a&&y1<=b){if(map1[x1][y1]==9){cout<<"YES";return; }x1--;}//上 x1=x;y1=y;while(x1>=1&&y1>=1&&x1<=a&&y1<=b){if(map1[x1][y1]==9){cout<<"YES";return; }y1++;}//下 x1=x;y1=y;while(x1>=1&&y1>=1&&x1<=a&&y1<=b){if(map1[x1][y1]==9){cout<<"YES";return; }y1--;}//右 x1=x;y1=y;while(x1>=1&&y1>=1&&x1<=a&&y1<=b){if(map1[x1][y1]==9){cout<<"YES";return; }x1++;}}}cout<<"NO"; return;}signed main() {int t=1;cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);//cin >> t;while (t--) {solve();}
} 

D.又是一年毕业季

暴力

#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10, M = 110, mod = 998244353, inf = 2e9;
typedef pair<int, int> pt;
typedef long long ll;bool isprime(int x) {for (int i = 2; i * i <= x; i++) {if (x % i == 0) return 0;}return 1;
}void solve() {int n;cin >> n;vector<int> a(n);map<int, int> mp;for (int i = 0; i < n; i++) {cin >> a[i];mp[a[i]]++;}sort(a.begin(), a.end());for (int i = 2; i <= a[n - 1] + 100; i++) {if (isprime(i) && !mp.count(i)) {cout << i << endl;return;}}
}   
signed main() {ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);int t = 1;cin >> t;while (t--) {solve();}return 0;
}