A. Matrix Game
题意：
一个矩阵初始状态有些位置是 1 表示该位置对应的行和列都已经被占用。
现在两人轮流选一个未被占用的位置标记， A 是先手，谁动不了了谁就输了，输出赢家。
分析：
计算没有未被占的行数与列数，取 min，若 min 为奇数就是先手赢，反之后手赢。
void solve()
{
mst(stc, false), mst(str, false);
cin >> n >> m;
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= m; j++)
{
cin >> g[i][j];
if (g[i][j])
str[i] = stc[j] = true;
}
}
int idxr = 0, idxc = 0;
for (int i = 1; i <= n; i++)
{
if (!str[i])
idxr++;
}
for (int i = 1; i <= m; i++)
{
if (!stc[i])
idxc++;
}
int t = min(idxr, idxc);
if (t & 1)
cout << "Ashish" << endl;
else
cout << "Vivek" << endl;
}
B. Trouble Sort
题意：
给定一个数组以及 2 种类型，每次操作可以交换类型不同的两个数，在无限次操作之后能否将数组非递减
分析：
计算种类个数：
- 含有 2 类数即可实现任意两个数之间的交换：每个种类的数可以利用另一个种类的一个数作为中转进行内部排序
- 只含有一种数，因为无法实现交换，看原数组是否为非递减
void solve()
{
num0 = num1 = 0;
bool f = false;
cin >> n;
for (int i = 1; i <= n; i++)
{
cin >> a[i];
if (i > 1 && a[i] < a[i - 1])
f = true;
}
for (int i = 1; i <= n; i++)
{
cin >> b[i];
if (b[i])
num1++;
else
num0++;
}
if (f && (!num1 || !num0))
cout << "NO" << endl;
else
cout << "YES" << endl;
}
C. Rotation Matching
题意：
给定两个数组，对第二个数组的元素进行整体右移动 1 单元，求实现两个数组匹配数最大的最小操作步数
思路：
由于是整体移动，数与数之间的距离不会发生改变，固定一个数的位置，其他数位置也就固定，计算第二个数组中每个数到匹配位置的距离，最大匹配的最小操作数就是相同距离的最大的次数
void solve()
{
int res = 0;
cin >> n;
for (int i = 1; i <= n; i++)
{
cin >> a[i];
pos[a[i]] = i;
}
for (int i = 1; i <= n; i++)
{
cin >> b[i];
int t = (pos[b[i]] - i + n) % n;
cnt[t]++;
res = max(res, cnt[t]);
}
cout << res << endl;
}
D. Solve The Maze
题意：
\(n * m\) 的矩阵中，出口在 \([n, m]\) ，#不能走，G是好人B是坏人.可以走，将一些.换成#,是否有方法保证G都能出去B都出不去
分析：
先把B周围都围起来（注意出口是否能堵的情况），这样保证坏人出不去
对现在的地图从 [n, m]开始BFS，能到达的记为TRUE,最后看所有的G能否都出去，B是否都出不去
bool check(int x, int y)
{
if (x < 1 || x > n || y < 1 || y > m || g[x][y] == '#' || st[x][y])
return false;
return true;
}
void bfs(int n, int m)
{
queue<PII> q;
if (g[n][m] == '.' || g[n][m] == 'G')
{
st[n][m] = true;
q.push({n, m});
}
while (q.size())
{
auto t = q.front();
q.pop();
for (int i = 0; i < 4; i++)
{
int xx = t.x + dx[i], yy = t.y + dy[i];
if (check(xx, yy))
{
q.push({xx, yy});
st[xx][yy] = true;
}
}
}
}
void solve()
{
mst(st, false);
cin >> n >> m;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
cin >> g[i][j];
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
if (g[i][j] == 'B')
{
for (int k = 0; k < 4; k++)
{
int xx = i + dx[k], yy = j + dy[k];
if (xx < 1 || xx > n || yy < 1 || yy > m || g[xx][yy] == 'G' || g[xx][yy] == '#' || g[xx][yy] == 'B')
continue;
g[xx][yy] = '#';
}
}
bfs(n, m);
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= m; j++)
{
if (g[i][j] == 'G' && !st[i][j])
{
cout << "NO" << endl;
return;
}
else if (g[i][j] == 'B' && st[i][j])
{
cout << "NO" << endl;
return;
}
}
}
cout << "YES" << endl;
}
E. Maximum Subsequence Value
题意：
在给定的序列中选择一个子序列，若子序列里有 k 个数，当至少有 \(max(1, k - 2)\) 个数在二进制第 i 位上为 1 的时候，对答案就有 \(2^i\) 贡献，求最大贡献
分析：
对于 k ，若至少有 2（甚至更多） 个数的二进制的第 i 位是 1 ，那么这些数一定包含在：至少有 1 个数的二进制第 i 位是 1 ，这样能保证贡献的值更多
- 当 k <= 3 时，只需要一个数的该位有效即可产生贡献，可以直接选三个数使贡献更大
- 当 k > 3 时，此时需要至少 2 个数的第 i 位为 1 ，能证明此时的答案必定小于选一个数时的答案
void solve()
{
cin >> n;
for (int i = 1; i <= n; i++)
cin >> a[i];
int res = 0;
for (int i = 1; i <= n; i++)
for (int j = i; j <= n; j++)
for (int k = j; k <= n; k++)
res = max(res, a[i] | a[j] | a[k]);
cout << res << endl;
}