https://codeforces.com/contest/1344/
可能是因为大家都unrate之后弃坑了，导致AB题过得快的我假装可以加分。
A - Hilbert's Hotel
题意：有无穷个房间，无穷个整数（包括负整数和零），每个整数正好对应一个房间（大小为 (i) 的整数恰好在编号为 (i) 的房间）。现在设计一种规则让这些整数调换房间，问调换房间之后是否仍然是“每个整数正好对应一个房间”？
这种规则是：输入一个 (n) 个数的数组 (a) ，然后大小为 (i) 的整数会被传送去 (i+a_{k mod n}) 。
题解：看了一下样例好像只需要验证输入的数组 (a) 恰好是 ([0,n-1]) 就可以了。简单想了一下确实是这样，只需要每 (n) 个数一组进行组内轮换就可以。
排序，去重，然后看看是不是刚好有 (n) 个。
int a[200005];
void TestCase() {
int n;
scanf("%d", &n);
for(int i = 1; i <= n; ++i) {
scanf("%d", &a[i]);
a[i] = (a[i] % n + n) % n;
a[i] = (i + a[i]) % n;
}
sort(a + 1, a + 1 + n);
int m = unique(a + 1, a + 1 + n) - (a + 1);
if(n == m)
puts("YES");
else
puts("NO");
return;
}
B - Monopole Magnets
题意：给一个 (n*m) 个网格图，上面有一些黑色格子和一些白色格子。在这些格子上面可以放任意个S磁铁和任意个N磁铁，一个格子可以放任意多个磁铁（可以同种也可以不同种），求最少放多少个N磁铁使得“每个黑色格子都存在一种操作序列被从‘初始状态’开始的某个N磁铁经过，而每个白色格子都不存在任何操作序列被从‘初始状态’开始的某个N磁铁经过”。
限制：注意一种合法的放法要求每行和每列都至少有一个S磁铁。
一次操作是选择一个S磁铁和一个N磁铁，若他们在同一行或者同一列，但是并不在同一个格子，那么N磁铁会向S磁铁移动一格，注意S磁铁是不会移动的。
题解：先看了下面的样例解释（点赞CF每次都有样例解释，还举了很多边界情况的例子），然后可以推断出几个推论：
推论1：黑色格子全部放S磁铁，且黑色格子直线连接之间的格子不能有白色格子。
证明：反正每个黑色格子都是要被N磁铁遍历到，由于“限制”的存在，初始图中放的N磁铁必定可以经过到同行或者同列的S磁铁处，所以“黑色格子直线连接之间的格子不能有白色格子”。多放一些S磁铁只会使得操作更加无脑。
推论2：N磁铁的最少数量与黑色格子的连通块数量相等。
证明：显然？
推论3：若有“全是白色格子的行”，则必须有“全是白色格子的列”才是合法方案。若有“全是白色格子的列”，则必须有“全是白色格子的行”才是合法方案。
证明：由于“限制”的存在，某些白色格子必须要放S磁铁，这时候只能放在“全是白色格子的行”和“全是白色格子的列”的交叉点上，放在这些点上才不会吸引其他的N磁铁经过这些白色格子。
char g[1005][1005];
int L[1005];
int R[1005];
int U[1005];
int D[1005];
bool vis[1005][1005];
int dx[] = {0, 0, -1, 1};
int dy[] = {-1, 1, 0, 0};
void dfs(int si, int sj) {
vis[si][sj] = 1;
for(int k = 0; k < 4; ++k) {
int i = si + dx[k];
int j = sj + dy[k];
if(g[i][j] == '#' && vis[i][j] == 0)
dfs(i, j);
}
return;
}
void TestCase() {
int n, m;
scanf("%d%d", &n, &m);
for(int i = 1; i <= n; ++i)
scanf("%s", g[i] + 1);
for(int i = 1; i <= n; ++i) {
int firstblack = -1;
for(int j = 1; j <= m; ++j) {
if(g[i][j] == '#') {
firstblack = j;
break;
}
}
L[i] = firstblack;
firstblack = -1;
for(int j = m; j >= 1; --j) {
if(g[i][j] == '#') {
firstblack = j;
break;
}
}
R[i] = firstblack;
}
for(int j = 1; j <= m; ++j) {
int firstblack = -1;
for(int i = 1; i <= n; ++i) {
if(g[i][j] == '#') {
firstblack = i;
break;
}
}
U[j] = firstblack;
firstblack = -1;
for(int i = n; i >= 1; --i) {
if(g[i][j] == '#') {
firstblack = i;
break;
}
}
D[j] = firstblack;
}
int Rm1 = 0, Cm1 = 0;
for(int i = 1; i <= n; ++i) {
if(L[i] != -1) {
for(int j = L[i]; j <= R[i]; ++j) {
if(g[i][j] != '#') {
puts("-1");
return;
}
}
} else
Rm1 = 1;
}
for(int j = 1; j <= m; ++j) {
if(U[j] != -1) {
for(int i = U[j]; i <= D[j]; ++i) {
if(g[i][j] != '#') {
puts("-1");
return;
}
}
} else
Cm1 = 1;
}
if(Rm1 + Cm1 == 1) {
puts("-1");
return;
}
int ans = 0;
for(int i = 1; i <= n; ++i) {
for(int j = 1; j <= m; ++j) {
if(g[i][j] == '#' && vis[i][j] == 0) {
++ans;
dfs(i, j);
}
}
}
printf("%d
", ans);
return;
}