牛客小白月赛89（A~C）

本文主要是介绍牛客小白月赛89（A~C），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

小白赛怎么这么难打，是什么小白，我的世界小白吗。

A. 伊甸之花

给你一个数组 a，问你是否找出一个 不等于 a 的数组 b，满足

其中数值都要在 [1,m] 的范围内

直接在 a 数组上修改，可以发现如果改了 a[1],a[2]，那么 a[3] 也要一起修改，所以考虑两个极限情况，一个是全体加一，还有一个是全体减一。

#include <bits/stdc++.h>
//#define int long long
#define per(i,j,k) for(int (i)=(j);(i)<=(k);++(i))
#define rep(i,j,k) for(int (i)=(j);(i)>=(k);--(i))
#define debug(a) cout<<#a<<"="<<a<<endl
#define all(x) x.begin(),x.end()
#define EX exit(0)
#define fr first
#define se second
#define endl '\n'
using namespace std;
using ll=long long;void solve(){int n,m;cin>>n>>m;int a[n+1];per(i,1,n)cin>>a[i];per(i,1,n)a[i]++;per(i,1,n){if(a[i]>m){per(j,1,n)a[j]-=2;per(j,1,n){if(a[j]<1){cout<<"No"<<endl;return;}}}}cout<<"Yes"<<endl;
}signed main(){ios::sync_with_stdio(false),cin.tie(nullptr);int t=1;while(t--)solve();return 0;
}

B. 显生之宙

如果是负数，我们希望所有数都加上他，这样最终最小值才会尽可能小。

如果是正数，那么留到最后求和。

考虑先排序，然后如果第一个是负数，就以差分的形式把值保留下来，然后求和。

#include <bits/stdc++.h>
#define int long long
#define per(i,j,k) for(int (i)=(j);(i)<=(k);++(i))
#define rep(i,j,k) for(int (i)=(j);(i)>=(k);--(i))
#define debug(a) cout<<#a<<"="<<a<<endl
#define all(x) x.begin(),x.end()
#define EX exit(0)
#define fr first
#define se second
#define endl '\n'
using namespace std;
using ll=long long;void solve(){int n,sum=0;cin>>n;int a[n+1];per(i,1,n)cin>>a[i],sum+=a[i];sort(a+1,a+1+n);if(a[1]>=0){cout<<sum<<endl;}else{int res=a[1],ans=0;per(i,2,n){a[i]+=res;if(a[i]<0)res+=a[i];//如果一直都小于0,那么最后答案就是差分的累计a[n]else ans+=a[i];//如果加了累计的负数还大于0，那么后面都是正数,最终答案为ans}if(ans)cout<<ans<<endl;else cout<<a[n]<<endl;}}signed main(){ios::sync_with_stdio(false),cin.tie(nullptr);int t=1;cin>>t;while(t--)solve();return 0;
}

C. 太阳之华

每次可以选择一个红色连通块向外感染（注意不是所有红色块）。

观察题目所给的数据范围

最差情况感染一次的复杂度是n*m，2e6，一共有100组数据点，总计2e8复杂度，即这题最多进行10次及以下的搜索次数，因此我们向博弈论的方向考虑。

红方先手，然后来回执行。

假设蓝方执行之后，红方再执行可以覆盖所有蓝色，显然不管在中间还是四个角落，只要有一个蓝色块往外延伸一次，就会平局，那么得出结论：

红方必须在一次操作之后覆盖所有蓝色块，否则就是平局。

#include <bits/stdc++.h>
//#define int long long
#define per(i,j,k) for(int (i)=(j);(i)<=(k);++(i))
#define rep(i,j,k) for(int (i)=(j);(i)>=(k);--(i))
#define debug(a) cout<<#a<<"="<<a<<endl
#define all(x) x.begin(),x.end()
#define EX exit(0)
#define fr first
#define se second
#define endl '\n'
using namespace std;
using ll=long long;
const int N=2e3+5;int n,m;
string s[N],news[N];bool isok(int x,int y){return x>=1 and x<=n and y>=0 and y<=m-1;
}int dx[4]={0,0,1,-1};
int dy[4]={1,-1,0,0};bool vis[N][N];void dfs(int x,int y){if(vis[x][y])return;vis[x][y]=true;per(i,0,3){int nx=dx[i]+x,ny=dy[i]+y;if(isok(nx,ny) and !vis[nx][ny] and s[nx][ny]=='#')dfs(nx,ny);else if(isok(nx,ny) and s[nx][ny]=='.')news[nx][ny]='#';}
}bool redGo(){per(i,1,n){per(j,0,m-1){//遍历所有的红色连通块,是否能从其中一个使得蓝色全部被覆盖if(s[i][j]=='#' and !vis[i][j]){per(k,1,n)news[k]=s[k];dfs(i,j);int blue=0;per(k,1,n){per(l,0,m-1){blue+=news[k][l]=='.';}}if(blue==0)return true;}}}return false;
}void solve(){cin>>n>>m;//#先手per(i,1,n)cin>>s[i];int red=0;per(i,1,n){per(j,0,m-1){red+=s[i][j]=='#';}}if(red==0){//特判初始状态cout<<"Blue"<<endl;return;}else if(red==n*m){cout<<"Red"<<endl;return;}per(i,1,n){//多组测试点初始化per(j,0,m-1)vis[i][j]=false;}if(redGo()){cout<<"Red"<<endl;return;}cout<<"Draw"<<endl;
}signed main(){ios::sync_with_stdio(false),cin.tie(nullptr);int t=1;cin>>t;while(t--)solve();return 0;
}

这篇关于牛客小白月赛89（A~C）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---