目录

A. Matrix Game

B. Trouble Sort

C. Rotation Matching

D. Solve The Maze

E. Maximum Subsequence Value

A. Matrix Game

题意：给一个n*m的01矩阵，两人轮流将0转化为1，若点pos可以被转化，那么要求x行和y列没有1。谁不能转谁输。

思路：计算所有满足的点的数量，根据奇偶性判断。

AC代码：

 /*---------------------------------  *File name: A.cpp  *Creation date: 2020-06-07 22:28  *Link:   *-------------------------------*/ #include<set> #include<map> #include<cmath> #include<queue> #include<vector> #include<cstdio> #include<string> #include<cstring> #include<iostream> #include<algorithm> #define fi first #define se second #define pb push_back #define LL long long #define PII pair<int, int> #define Pque priority_queue  using namespace std; const int maxn = 1e5 + 5; const int inf = 0x3f3f3f3f; const LL mod = 1e9 + 7; const double EPS = 1e-8;  int main(){  int t;  scanf("%d", &t);  while(t--){   int n, m;   scanf("%d %d", &n, &m);   vector<bool> col(m + 1, 0), row(n + 1, 0);   for(int i = 1; i <= n; ++i){    for(int j = 1; j <= m; ++j){     int a;     scanf("%d", &a);     if(a){      col[j] = 1;      row[i] = 1;     }    }   }   int ans = 0;   for(int i = 1; i <= n; ++i){    for(int j = 1; j <= m; ++j){     if(col[j] == 0 && row[i] == 0){      ans++;      col[j] = 1;      break;     }    }   }   if(ans % 2 == 1){    printf("Ashishn");   }   else printf("Vivekn");  }  return 0; }

B. Trouble Sort

题意：给长度为为n的数组，每个数拥有属性（0或1），问是否能够将数组通过swap操作变为非递减数组，交换的两个数的属性必须不相同。

思路：想想就可以明白如果要排序属性为0的，只要有一个1 存在，就可以用这个1作为媒介交换两个0，反之也是这样，因此如果属性1和属性0的数都有，必定可以排序。如果0或1没有，那么直接判断原数组是否是非递减序列。

AC代码：

 /*---------------------------------  *File name: A.cpp  *Creation date: 2020-06-07 23:17  *Link:   *-------------------------------*/ #include<set> #include<map> #include<cmath> #include<queue> #include<vector> #include<cstdio> #include<string> #include<cstring> #include<iostream> #include<algorithm> #define fi first #define se second #define pb push_back #define LL long long #define PII pair<int, int> #define Pque priority_queue  using namespace std; const int maxn = 1e5 + 5; const int inf = 0x3f3f3f3f; const LL mod = 1e9 + 7; const double EPS = 1e-8;   struct node {  LL a;  int b ; }T[505]; int t, n, o, z;  void solve(){  for(int ct = 1; ct <= t; ++ct){   cin >> n;   o = 0 , z = 0 ;   bool vis = true ;   for(int i = 1 ; i <= n ; ++i){    scanf("%lld", &T[i].a);    if(T[i].a - T[i - 1].a < 0) vis = false;   }   bool flag = true;   int i = 1;   while(i <= n){    scanf("%d",&T[i].b);    if(T[i].b)++o;    else ++z;    ++i;   }   if((!o || !z) && !vis) flag = false;   if(flag) printf("Yesn");   else printf("Non");  } }  int main(){  cin >> t;  solve();  return 0; }

C. Rotation Matching

题意：给定两个排列，问能否通过左移右移操作将a序列和b序列相同数在同一位置的数量最多。左移右移操作定义为：对于序列c: 左移操作为将所有数循环地向左移动一个位置，即变为：c1:=c2,c2:=c3,…,cn:=c1。右移类似。

思路：因为是排列，所以每个数出现且只出现一次，那么对于b排列中的任意一个数x，记录下x在a排列中的位置，即是要将b中的x与a对齐所需要的操作次数。记录下每一个操作次数所能够对齐的数量，取max即是答案。

AC代码：

 /*---------------------------------  *File name: A.cpp  *Creation date: 2020-06-07 23:41  *Link:   *-------------------------------*/ #include<set> #include<map> #include<cmath> #include<queue> #include<vector> #include<cstdio> #include<string> #include<cstring> #include<iostream> #include<algorithm> #define fi first #define se second #define pb push_back #define LL long long #define PII pair<int, int> #define Pque priority_queue  using namespace std; const int maxn = 2e5 + 5; const int inf = 0x3f3f3f3f; const LL mod = 1e9 + 7; const double EPS = 1e-8;  const int MaxN = 2e5 + 5; const long long Inf = 0x3f3f3f3f3f3f3f3f;  int n , a[maxn] , b[maxn]; int num[maxn] , pos[maxn];  void solve(){  for(int i = 1; i <= n ; ++i){   scanf("%d", a + i);   pos[a[i]] = i ;  }  for(int i = 1 ; i <= n; ++i){   scanf("%d", b + i);   int res = i - pos[b[i]];   if(res < 0) res += n;   num[res]++;  }  int ans = 1;   int i = 0;  while(i < n){   ans = max(ans, num[i++]);  }  printf("%dn", ans); }  int main(){  scanf("%d",&n);  solve();  return 0; }

D. Solve The Maze

题意：给一个n*m的迷宫，里面有好人坏人和墙壁，问能不能通过增加墙壁使的所有好人能够到达出口而所有坏人不能。出口在点（n，m）。

思路：暴力找出所有坏人的位置，在他们四周放上墙壁，在过程中判断放墙壁的位置是否有好人，有的话则不行。若堵住了所有坏人且没有好人在坏人相邻的格子情况下，从出口BFS标记所有能到达出口的点，再暴力循环一遍找所有好人的位置，只要所有好人的位置都被标记，那么好人就可以到达出口，反之不行。

AC代码：

 /*---------------------------------  *File name: A.cpp  *Creation date: 2020-06-07 23:17  *Link:   *-------------------------------*/ #include<set> #include<map> #include<cmath> #include<queue> #include<vector> #include<cstdio> #include<string> #include<cstring> #include<iostream> #include<algorithm> #define fi first #define se second #define pb push_back #define LL long long #define PII pair<int, int> #define Pque priority_queue  using namespace std; const int maxn = 1e5 + 5; const int inf = 0x3f3f3f3f; const LL mod = 1e9 + 7; const double EPS = 1e-8;  int n, m, t; char a[55][55]; int dx[] = {-1, 0, 1, 0}; int dy[] = {0, -1, 0, 1}; bool vis[55][55];  bool bfs(int x, int y){  queue<PII> q;  q.push(PII(x, y));  vis[x][y] = 1;  while(!q.empty()){   PII cur = q.front();   q.pop();   for(int i = 0; i < 4; ++i){    int nx = cur.fi + dx[i];    int ny = cur.se + dy[i];    if(nx < 1 || nx > n || ny < 1 || ny > m) continue;    if(a[nx][ny] == '#') continue;    if(vis[nx][ny]) continue;    vis[nx][ny] = 1;    q.push(PII(nx, ny));   }  }  bool ex = 1;  for(int i = 1; i <= n && ex; ++i){   for(int j = 1; j <= m; ++j){    if(a[i][j] == 'G' && vis[i][j] == 0){     ex = 0;     break;    }   }  }  return ex; }  void solve(){  scanf("%d %d", &n, &m);  memset(a, 0, sizeof(a));  memset(vis, 0, sizeof(vis));  for(int i = 1; i <= n; ++i){   scanf(" %s", a[i] + 1);  }  bool G = 0;  bool ex = 1;  for(int i = 1; i <= n; ++i){   for(int j = 1; j <= m; ++j){    if(a[i][j] == 'B'){     for(int k = 0; k < 4; ++k){      if(a[i + dx[k]][j + dy[k]] == '.'){       a[i + dx[k]][j + dy[k]] = '#';      }      else if(a[i + dx[k]][j + dy[k]] == 'G'){       ex = 0;      }     }    }    else if(a[i][j] == 'G') G = 1;   }  }  if(ex == 0 || (G != 0 && a[n][m] == '#')) printf("Non");  else{   if(G == 0) printf("Yesn");   else{    ex = bfs(n, m);    printf("%sn", ex ? "Yes" : "No");   }  } }  int main(){  cin >> t;  while(t--) solve();  return 0; }

E. Maximum Subsequence Value

题意：有点难解释。。建议自己看题。我这里就粗略解释：给定一个数组a，要求选出具有最大价值的子序列。假设此子序列的长度为k，那么最大价值的计算方法为：对于这个序列中的所有数的二进制表示，第 i （从0开始）位上是1的数的数量若大于等max(k – 2, 1)，那么价值就可以 += 。（还没理解的可以看看样例解释）。

思路：（赛后容易知道）子序列的选择其实长度最大为3，再大的话，就不仅仅对答案的贡献不大，还把答案的贡献缩小了。因为序列长度在3以内时都只需要1个数在第 i 位上是1就可以，若长度为4，那么可能会导致一些数位只有一个数满足，而要求的计算价值至少需要两个，这样有可能还会拖累到价值的计算，但是又不会给价值增加答案：对于本身第 i 位已经有1个的，若新增的数第 i 位也有1，对答案不会有增加，对本身第 i 位没有1的，新增的数第 i 位有1，也无法计入答案，因此选择三个以内是可以保证价值的最大化的。由于n只有500，所以可以暴力枚举所有方案，价值的计算就转化为了：对于第 i 位，若有1，则价值+=。而第 i 位上是否有1，直接按位或就能知道枚举的3个数哪里有1了。

AC代码：

 /*---------------------------------  *File name: E.cpp  *Creation date: 2020-06-08 08:25  *Link:   *-------------------------------*/ #include<set> #include<map> #include<cmath> #include<queue> #include<vector> #include<cstdio> #include<string> #include<cstring> #include<iostream> #include<algorithm> #define fi first #define se second #define pb push_back #define LL long long #define PII pair<int, int> #define Pque priority_queue  using namespace std; const int maxn = 1e5 + 5; const int inf = 0x3f3f3f3f; const LL mod = 1e9 + 7; const double EPS = 1e-8;  int main(){  int n;  scanf("%d", &n);  LL ans = 0;  vector<LL> a(n);  for(int i = 0; i < n; ++i){   scanf("%lld", &a[i]);  }  for(int i = 0; i < n; ++i){   for(int j = 0; j < n; ++j){    for(int k = 0; k < n; ++k){     LL tmp ;     tmp = a[k] | a[i] | a[j];     ans = max(ans, tmp);    }       }  }  printf("%lldn", ans);  return 0; }