Codeforces Round #648 (Div. 2) CodeForces

A. Matrix Game
先统计可以填的行数和列数，每次填行数和列数都会减小1 1 1 所以只需要判断行数和列数最小值的奇偶性即可。
AC代码：

int n, m, k; bool r[110], c[110]; int main() { int T; sd(T); while (T--) { sdd(n, m); mem(r, 0); mem(c, 0); rep(i, 1, n) { rep(j, 1, m) { int x; sd(x); if (x) r[i] = c[j] = true; } } int a = 0, b = 0; rep(i, 1, n) { if (!r[i]) a++; } rep(i, 1, m) { if (!c[i]) b++; } if (min(a, b) & 1) puts("Ashish"); else puts("Vivek"); } return 0; }

B. Trouble Sort
0 0 0 和1 1 1 如果都存在的话那么肯定是可以的，因为有可以置换的话，就可以通过不断的交换位置把每个数换到自己本来的位置。然后再判断只有0 0 0 或者只有1 1 1 的是否为递增即可。
AC代码：

int n, m, k; int a[1100], b[1100]; int main() { int T; sd(T); while (T--) { sd(n); bool flag = false, ok = false; rep(i, 1, n) sd(a[i]); rep(i, 1, n) { sd(b[i]); if (b[i]) flag = true; else ok = true; } if (flag && ok) { puts("Yes"); continue; } flag = true; rep(i, 2, n) { if (a[i] < a[i - 1]) { flag = false; break; } } if (flag) puts("Yes"); else puts("No"); } return 0; }

C. Rotation Matching
用一个数组存一下上面和下面相同的数字的位置差，然后找每个位置差可以产生的最大匹配数。
AC代码：

const int N = 5e5 + 50; int n, m, k; int a[N], b[N], pos[N], cnt[N]; int main() { int T; sd(n); rep(i, 1, n) cnt[i] = 0; rep(i, 1, n) sd(a[i]), pos[a[i]] = i; rep(i, 1, n) sd(b[i]); rep(i, 1, n) { if (pos[b[i]] < i) cnt[pos[b[i]] + n - i]++; else cnt[pos[b[i]] - i]++; } int ans = 0; rep(i, 0, n) ans = max(ans, cnt[i]); pd(ans); return 0; }

D. Solve The Maze
首先把坏人相邻的空格变成障碍物，因为好人肯定不会经过坏人周围的空格，否则坏人会顺着这个路逃走，然后找每一个好人是否可以走出去。好人如果和坏人紧挨着或者n , m n,m n,m 位置是墙，那么肯定不行，好人如果数量为0 0 0 这样输出Y e s Yes Yes 。
AC代码：

const int N = 5e5 + 50; int n, m; char c[100][100]; int vis[100][100]; int mp[4][2] = {0, 1, 0, -1, 1, 0, -1, 0}; void bfs() { queue q; vis[n][m] = 1, q.push(PII(n, m)); while (!q.empty()) { PII now = q.front(); q.pop(); rep(i, 0, 3) { int dx = now.fi + mp[i][0], dy = now.se + mp[i][1]; if (dx < 0 || dx > n || dy < 0 || dy > m || c[dx][dy] == '#' || vis[dx][dy] != -1) continue; vis[dx][dy] = 1, q.push(PII(dx, dy)); } } } int main() { int T; sd(T); while (T--) { sdd(n, m); rep(i, 1, n) ss(c[i] + 1); int cnt = 0; rep(i, 1, n) { rep(j, 1, m) { if (c[i][j] == 'G') cnt++; } } if (!cnt) { puts("Yes"); continue; } bool flag = true; rep(i, 1, n) { rep(j, 1, m) { if (c[i][j] == 'B') { rep(t, 0, 3) { int dx = i + mp[t][0], dy = j + mp[t][1]; if (dx < 0 || dx > n || dy < 0 || dy > m || c[dx][dy] == 'B') continue; if (c[dx][dy] == 'G') { flag = false; break; } c[dx][dy] = '#'; } } if (!flag) break; } if (!flag) break; } if (!flag || c[n][m] == '#') { puts("No"); continue; } rep(i, 1, n) { rep(j, 1, m) vis[i][j] = -1; } bfs(); flag = true; rep(i, 1, n) { rep(j, 1, m) { if (c[i][j] == 'G' && vis[i][j] != 1) { flag = false; break; } } } if (flag) puts("Yes"); else puts("No"); } return 0; }

E. Maximum Subsequence Value
首先肯定从最高位开始选，假设最高位是h h h 且有x x x 个数含有2 h 2^h 2h
如果x > = 3 x >= 3 x>=3 那么你以后无论再选什么数都会造成对于第j j j 位( 2 j ) (2^j) (2j) 的c n t + 1 , x + 1 cnt + 1, x + 1 cnt+1,x+1, 本质上m a x ( 1 , x ? 2 ) > c n t max(1, x - 2) > cnt max(1,x?2)>cnt 没变
所以我们要卡住k < = 3 k <= 3 k<=3, 找最大值就行了。
AC代码：

int n, m, k; ll a[N]; int main() { int t; sd(n); rep(i, 1, n) sld(a[i]); ll ans = a[1]; rep(i, 1, n) { rep(j, i, n) { rep(k, j, n) ans = max(ans, a[i] | a[j] | a[k]); } } pld(ans); return 0; }

F. Swaps Again
【Codeforces Round #648 (Div. 2)】很显然，对于对称的两个数（ a i 和 a n ? i + 1 ）（a_i 和 a_{n?i+1}）（ai?和an?i+1?），经过任意操作后，它俩还是对称的，就是只能和对称位置的交换，只要把对称的数捆绑在一起，然后判断可不可以变成想要的序列即可。
AC代码 :

const int N = 5e2 + 50; int n, m, k; int a[N], b[N]; map mp; int main() { int t; sd(t); while (t--) { sd(n); rep(i, 1, n) sd(a[i]); rep(i, 1, n) sd(b[i]); bool flag = true; mp.clear(); if (n % 2 == 1 && a[(n + 1) / 2] != b[(n + 1) / 2]) { puts("No"); continue; } rep(i, 1, n / 2) { int x = a[i], y = a[n - i + 1]; if (x > y) swap(x, y); mp[{x, y}]++; x = b[i], y = b[n - i + 1]; if (x > y) swap(x, y); mp[{x, y}]--; } for (auto i : mp) { if (i.se != 0) flag = false; } if (flag) puts("Yes"); else puts("No"); } return 0; }