牛客小白月赛99

文章目录

A.材料打印
B. %%%
C.迷宫
又是一年毕业季
题目链接

A.材料打印

签到题，直接按照题意输出就行。赛时写的有点慢了，这种题应该一分钟之内写完的

void solve () {int n;cin>>n;for (int i=1;i<=n;i++) {int a,b,c,d;cin>>a>>b>>c>>d;int ans=b*d;ans+=min(c,d)*a;cout<<ans<<'\n';}
}

B. %%%

在这里插入图片描述
一道小小思维题
问n最多能进行几次操作。
模拟一下，当n为6的时候，能选取的值为1,2,3,4,5.可以发现取4的时候最大。当n为7的时候可以选取的数字为1,2,3,4,5,6.可以发现取4的时候最大。
因此我们发现规律，当每次选取n/2+1为值的时候就是最大的

void solve () {int n;cin>>n;for (int i=1;i<=n;i++) {int x;cin>>x;int ans=0;while (x) {x%=(x/2+1);ans++;}cout<<ans<<'\n';}
}

C.迷宫

一道搜索题。
问小明能否从S走到E，‘.’代表路,‘#’代表障碍。但是小明有魔力，可以清除一个方向上的障碍物。但是小明的魔力只能使用一次，问小明能否到达目的地
一开始看到这种迷宫问题我就开始用BFS的思路写。但是发现写不出来，想了想发现这题是DFS的思路。但是最后DFS的思路没有写出来，赛后看了别人的代码才明白
因为小明的魔力可以清除一个方向上的障碍，所以在一点来看的话，要想到终点，小明必须清除六个方向上的某一个方向才能到达目的地。我们就先从终点DFS一下，每次把六个方向给标记一下，来说明清除这一方向上的所有点。标记完之后，再从起点DFS，如果小明走到了一处被六个方向其中一个标记的话，就说明能到达终点，因为这一方向是的障碍都被清除了。
接下来看下代码怎么实现

const int N = 2e5+5;
char a[1050][1050];
int q1,q2;
int z1,z2;
int m[1050][1050];int n,M;
int dx[4]={0,0,1,-1},dy[4]={1,-1,0,0};
int f=0;
int q[1050],w[1050];
void dfs2 (int x,int y) {if (x==z1&&y==z2) {f=1;return ;}if (q[x]==1||w[y]==1) {f=1;return ;}for (int i=0;i<4;i++) {int nx=x+dx[i];int ny=y+dy[i];if (nx>=1&&nx<=n&&ny>=1&&ny<=M&&m[nx][ny]==-1) {if (a[nx][ny]=='.'||a[nx][ny]=='E') {m[nx][ny]=1;dfs2 (nx,ny);}}}
}void dfs1 (int x,int y) {if (x==q1&&y==q2) {f=1;return ;}q[x-1]=1,q[x]=1,q[x+1]=1,w[y-1]=1,w[y]=1,w[y+1]=1;for (int i=0;i<4;i++) {int nx=x+dx[i];int ny=y+dy[i];if (nx>=1&&nx<=n&&ny>=1&&ny<=M&&m[nx][ny]==-1) {if (a[nx][ny]=='.'||a[nx][ny]=='S') {m[nx][ny]=1;dfs1 (nx,ny);}}}
}void solve () {memset (m,-1,sizeof m);cin>>n>>M;for (int i=1;i<=n;i++) {for (int j=1;j<=M;j++) {cin>>a[i][j];if (a[i][j]=='S') q1=i,q2=j;if (a[i][j]=='E') z1=i,z2=j;}}dfs1 (z1,z2);if (f==1) {cout<<"YES";return;}memset (m,-1,sizeof m);dfs2 (q1,q2);if (f==1) cout<<"YES";else cout<<"NO";
}

感觉是比较好的一道搜索题，以前没有见过这种类型的题。这一题的主要思路就是清除障碍的这六个方向，写好就能轻松AC。搜索还是要多练练，毕竟不是难题。

又是一年毕业季

一道欧拉筛的题
在这里插入图片描述
题意很好理解，就是最少多少秒拍照，学生们的眼睛都是睁开的。
每个学生眨眼的时间都给出了。我们可以发现，如果一个学生第二秒眨眼，那么他往后第4,6,8,10…都会眨眼。我们可以发现，往后眨眼的秒数都是合数。再结合样例我们会发现答案都是素数，所以我们就是要找没有出现的第一个素数。题目范围是已经给出了。
我们现用欧拉筛预处理一下前200000个素数，然后我们直接遍历这200000个素数，用个map标记一下，如果没有出现过的话，那么它就是答案
下面看下代码

void oula  () {a[1]=1,a[0]=1;for (int i=2;i<=N;i++) {if (!a[i]) b[++k]=i;for (int j=1;j<=k&&b[j]*i<=N;j++) {a[b[j]*i]=1;if (i%b[j]==0) break;}}
}void solve () {
//	cout<<k;int n;cin>>n;map<int,int>mp;for (int i=1;i<=n;i++) {cin>>x[i];mp[x[i]]++;}for (int i=1;i<=k;i++) {if (mp[b[i]]==0) {cout<<b[i]<<'\n';return ;}}
}