文章目录
- A - Matrix Game
- B - Trouble Sort
- C - Rotation Matching
- D - Solve The Maze
A - Matrix Game
题解:其实这个题细细一想,剩下可以化1的位置的数量就是整行不包含1的行数或整列不包含1的列数的两者最小值,最后在判断一下奇偶即可。
/*Keep on going Never give up*/#pragma GCC optimize(3,"Ofast","inline")#include <bits/stdc++.h>const int maxn = 55;const int MaxN = 0x3f3f3f3f;const int MinN = 0xc0c0c00c;typedef long long ll;const int mod = 100000000;using namespace std;int a[maxn][maxn];int main(){int t;cin>>t;while(t--){int n,m;cin>>n>>m;for(int i=0;i<n;i++){for(int j=0;j<m;j++){scanf("%d",&a[i][j]);}}int x=0,y=0;for(int i=0;i<n;i++){bool flag=true;for(int j=0;j<m;j++){if(a[i][j]==1) flag=false;}if(flag) x++;}for(int i=0;i<m;i++){bool flag=true;for(int j=0;j<n;j++){if(a[j][i]==1) flag=false;}if(flag) y++;}int ans=min(x,y);if(ans%2==0) cout<<"Vivek"<<endl;else cout<<"Ashish"<<endl;}return 0;}
B - Trouble Sort
题解:这个题因为不限制换位的次数,所以只要有奇偶不相同的数字类型,就可以换到任何想要去的位置,
/*Keep on going Never give up*/#pragma GCC optimize(3,"Ofast","inline")#include <bits/stdc++.h>const int maxn = 510;const int MaxN = 0x3f3f3f3f;const int MinN = 0xc0c0c00c;typedef long long ll;const int mod = 100000000;using namespace std;struct wazxy{int x,y;}a[maxn];int main(){int t;cin>>t;while(t--){int n;cin>>n;bool flag=true;for(int i=0;i<n;i++){scanf("%d",&a[i].x);}int ans1=0,ans0=0;for(int i=0;i<n;i++){scanf("%d",&a[i].y);if(a[i].y==0) ans0++;else ans1++;}for(int i=0;i<n-1;i++){if(a[i].x>a[i+1].x) flag=false;}if((ans0!=0&&ans1!=0)||flag==true) cout<<"Yes"<<endl;else cout<<"No"<<endl;}return 0;}
C - Rotation Matching
题解:看到所有元素都小于n并且只出现一次,这个信息十分关键,考虑开一个数组记录一下a[i]元素的位置,然后在输入b数组的时候要记录b的每个元素与a的对应的元素差的位置是多少,因为这里有可能会出现负数,所以当出现负数的时候,我们给他的位置加上n即可。
最后遍历一遍,看看哪个差值出现的最多,即为最大值。
/*Keep on going Never give up*/
#pragma GCC optimize(3,"Ofast","inline")
#include <bits/stdc++.h>
const int maxn = 2e5+10;
const int MaxN = 0x3f3f3f3f;
const int MinN = 0xc0c0c00c;
typedef long long ll;
const int mod = 100000000;
using namespace std;
int a[maxn],b[maxn];
int pos[maxn];
int rem[maxn];
int main(){int n;cin>>n;for(int i=0;i<n;i++){scanf("%d",&a[i]);pos[a[i]]=i;}for(int i=0;i<n;i++){scanf("%d",&b[i]);if(i-pos[b[i]]<0) rem[i-pos[b[i]]+n]++;else rem[i-pos[b[i]]]++;}int ans=0;for(int i=0;i<n;i++) ans=max(ans,rem[i]);cout<<ans<<endl;return 0;
}
D - Solve The Maze
昨天卡在这个题上还以为有坑点
我又又又又又又又又又又又又又又又又看错题了,因为第71个样例答案太靠后,系统给省略了,我又看不到答案,今上午找了一上午bug,实在没找出来,去看了一眼别人的题解才发现自己看错题了。
题意只有一个出口并且在右下角。
我理解所有的 . 都是出口
题解:我们先把B周围所有能方墙的位置放上墙(G不能方墙),在放墙的过程中如果发现B的旁边有G就可以直接输出No了,遍历地图把G的数量记录下来,从地图右下角进入地图开始遍历,数出所有G的数量,看看这两者G的数量是否相同,当然要特判一下出口是不是被放上墙了,如果有墙直接输出No。
/*Keep on going Never give up*/
#pragma GCC optimize(3,"Ofast","inline")
#include <bits/stdc++.h>
const int maxn = 55;
const int MaxN = 0x3f3f3f3f;
const int MinN = 0xc0c0c00c;
typedef long long ll;
const int mod = 100000000;
using namespace std;
char a[maxn][maxn];
bool zzz=false;
int dx[4]={1,-1,0,0};
int dy[4]={0,0,1,-1};
int n,m;
bool visited[maxn][maxn];
int cnt,ans;
void dfs(int x,int y){if(a[x][y]=='G') ans++;for(int i=0;i<4;i++){int nx=dx[i]+x;int ny=dy[i]+y;if((a[nx][ny]=='.'||a[nx][ny]=='G')&&visited[nx][ny]==false){visited[nx][ny]=true;dfs(nx,ny);}}return ;
}int main(){int t;cin>>t;while(t--){cin>>n>>m;cnt=0,ans=0;memset(a,-1,sizeof(a));memset(visited,false,sizeof(visited));for(int i=1;i<=n;i++){scanf("%s",a[i]+1);}bool res=true;for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){if(a[i][j]=='B'){if(a[i+1][j]!='G'&&a[i+1][j]!='B') a[i+1][j]='#';if(a[i][j+1]!='G'&&a[i][j+1]!='B') a[i][j+1]='#';if(a[i-1][j]!='G'&&a[i-1][j]!='B') a[i-1][j]='#';if(a[i][j-1]!='G'&&a[i][j-1]!='B') a[i][j-1]='#';if(a[i+1][j]=='G') res=false;if(a[i][j+1]=='G') res=false;if(a[i-1][j]=='G') res=false;if(a[i][j-1]=='G') res=false;}}}if(res==false){cout<<"No"<<endl;continue ;}for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){if(a[i][j]=='G') cnt++;}}if(cnt==0){cout<<"Yes"<<endl;continue ;}else if(a[n][m]=='#'){cout<<"No"<<endl;continue;}dfs(n,m);//cout<<ans<<endl;if(cnt==ans) cout<<"Yes"<<endl;else cout<<"No"<<endl;}return 0;}