A题
签到模拟题
#include<bits/stdc++.h> using namespace std; const int N=1e5+10; int g[55][55]; int col[55]; int row[55]; int main(){ int t; cin>>t; while(t--){ int n,m; cin>>n>>m; memset(col,0,sizeof col); memset(row,0,sizeof row); int i,j; for(i=1;i<=n;i++){ for(j=1;j<=m;j++){ cin>>g[i][j]; if(g[i][j]){ col[i]=1; row[j]=1; } } } int cnt=0; for(i=1;i<=n;i++){ for(j=1;j<=m;j++){ if(!g[i][j]){ if(!col[i]&&!row[j]){ cnt++; col[i]=row[j]=1; g[i][j]=1; } } } } if(cnt%2) cout<<"Ashish"<<endl; else{ cout<<"Vivek"<<endl; } } return 0; }
B题
排序比对
#include<iostream> #include<queue> #include<map> #include<vector> #include<cstdio> #include<algorithm> #include<stack> #include<cstring> #include<cstring> using namespace std; typedef long long ll; const int N=2e5+10; const int mod=1e9+7; int a[N]; int x[N]; int b[N]; int main(){ int t; cin>>t; while(t--){ int n; cin>>n; int i; for(i=1;i<=n;i++) cin>>a[i]; for(i=1;i<=n;i++) cin>>x[i]; int cnt1=0,cnt2=0; for(i=1;i<=n;i++){ if(x[i]==0) cnt1++; else cnt2++; } if(cnt1&&cnt2){ cout<<"YES"<<endl; } else{ memcpy(b,a,sizeof a); sort(b+1,b+1+n); int sign=0; for(i=1;i<=n;i++) if(b[i]!=a[i]){ sign=1; break; } if(!sign) cout<<"YES"<<endl; else cout<<"NO"<<endl; } } }
C题
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int N=6e5+10; int a[N]; int b[N]; int pos[N]; int cnt[N]; int main(){ ios::sync_with_stdio(false); int n; cin>>n; int i; for(i=1;i<=n;i++){ cin>>a[i]; pos[a[i]]=i; } for(i=1;i<=n;i++){ cin>>b[i]; } for(i=1;i<=n;i++){ int x=pos[b[i]]; if(x>=i){ cnt[x-i]++; } else{ int tmp=n-i+1; cnt[x-1+tmp]++; } } //cout<<cnt[1]<<endl; sort(cnt,cnt+1+n); reverse(cnt,cnt+1+n); cout<<cnt[0]<<endl; }
D题
如果好人和坏人挨在一起肯定不行
否则讲坏人周围的一圈全部围起来，这样是最优的
之后从n,m处看看能否经过所有的好人
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int N=6e5+10; char s[60][60]; int dx[]={-1,0,1,0}; int dy[]={0,1,0,-1}; int vis[60][60]; int res; int n,m; void dfs(int x,int y){ int i; for(i=0;i<4;i++){ int a=x+dx[i]; int b=y+dy[i]; if(a&&a<=n&&b&&b<=m&&(!vis[a][b])){ if(s[a][b]=='#') continue ; vis[a][b]=1; if(s[a][b]=='G'){ res++; } dfs(a,b); } } } int main(){ ios::sync_with_stdio(false); int t; cin>>t; while(t--){ memset(vis,0,sizeof vis); cin>>n>>m; int i,j; int gcnt=0; int sign=0; for(i=1;i<=n;i++){ for(j=1;j<=m;j++){ cin>>s[i][j]; } } for(i=1;i<=n;i++){ for(j=1;j<=m;j++){ if(s[i][j]=='G') gcnt++; else if(s[i][j]=='B'){ int k; //cout<<i<<" "<<j<<endl; for(k=0;k<4;k++){ int a=i+dx[k]; int b=j+dy[k];//cout<<a<<" "<<b<<endl; if(a&&a<=n&&b&&b<=m){ if(s[a][b]=='G'){ sign=1; break; } else if(s[a][b]=='.'){ s[a][b]='#'; } } } } } } res=0; if(sign){ cout<<"NO"<<endl; continue; } if(s[n][m]!='#'){ vis[n][m]=1; dfs(n,m); } if(res==gcnt) cout<<"YES"<<endl; else cout<<"NO"<<endl; } }
E题
因为题目已知至少要k-2个
假设我们取了k个，使得答案最大
那么因为对于每个数来说至少k-2个数在这位是1
因此我们只要任意选三个数，都能保证在每一位上都有至少一个数为1
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int N=1e5+10; ll a[N]; int main(){ int n; cin>>n; int i; for(i=1;i<=n;i++){ cin>>a[i]; } ll ans=0; if(n==1){ cout<<a[1]<<endl; } else if(n==2){ cout<<(a[1]|a[2])<<endl; } else{ int j,k; for(i=1;i<=n;i++){ for(j=i+1;j<=n;j++){ for(k=j+1;k<=n;k++) ans=max(ans,a[i]|a[j]|a[k]); } } cout<<ans<<endl; } }