刚刚看一言看到了神秘的歇后语，符合当下心理状态。
大本钟下送快递——上面摆，下面寄。
A - Errich-Tac-Toe (Hard Version)
https://vjudge.net/contest/585791#problem/A
如果我们将地图按国际象棋式斜向黑白染色分组，规定黑组要么黑色要么无色，白组要么白色要么无色，那么这样是一定不会三连击的。
容易发现无色格子永远不会被更改，而在方式 A 中被更改的格子在方式 B 中一定不会被更改；相应地，在方式 A 中不被更改的格子在方式 B 中一定会被更改，故两种染色方式更改的格子数总和就是一开始非无色的格子数。所以根据抽屉原理，一定能找到一种染色方式，代价 \(\le \dfrac k2\)。
但是我们要找到的，是代价 \(\le \dfrac k3\) 的方案呀？我们观察到我们上面的分组方式，直接让相邻两个不一样了，连二连击都做不到；所以我们要使我们的染色方式更廉价。
我们仍然斜向染色，但是分为三组：
这样，因为刚才叙述过的原因，一定能找到一种染色方法，代价 \(\le \dfrac k3\)。
枚举三种方式，取代价最小的一种即可。
namespace XSC062 {
using namespace fastIO;
const int maxn = 305;
char a[maxn][maxn];
int col[maxn][maxn];
int T, n, res, id, typ;
int min(int x, int y) {
return x < y ? x : y;
}
int func(int x, int y) {
int res = 0;
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= n; ++j) {
if (col[i][j] == y)
res += (a[i][j] == 'X');
else if (col[i][j] != x)
res += (a[i][j] == 'O');
}
}
return res;
}
int main() {
scanf("%d", &T);
while (T--) {
scanf("%d", &n);
int cnt = 0;
for (int i = 1; i <= n; ++i)
scanf("%s", a[i] + 1);
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= n; ++j)
cnt += (a[i][j] != '.');
for (int j = 1; j <= i; ++j)
col[j][i - j + 1]
= (i - 1) % 3 + 1;
}
for (int i = 2; i <= n; ++i) {
for (int j = 1; j <= n - i + 1; ++j)
col[j + i - 1][n - j + 1]
= (n + i - 2) % 3 + 1;
}
res = func(1, 2), id = 1, typ = 2;
if (func(1, 3) < res)
res = func(1, 3), id = 1, typ = 3;
if (func(2, 1) < res)
res = func(2, 1), id = 2, typ = 1;
if (func(2, 3) < res)
res = func(2, 3), id = 2, typ = 3;
if (func(3, 1) < res)
res = func(3, 1), id = 3, typ = 1;
if (func(3, 2) < res)
res = func(3, 2), id = 3, typ = 2;
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= n; ++j) {
if (col[i][j] == typ) {
if (a[i][j] == 'X')
a[i][j] = 'O';
}
else if (col[i][j] != id) {
if (a[i][j] == 'O')
a[i][j] = 'X';
}
}
}
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= n; ++j)
putchar(a[i][j]);
putchar('\n');
}
}
return 0;
}
} // namespace XSC062
抽屉原理是构造中经常用到的手段，后面我们也会遇到运用了抽屉原理的更多题目。
B - Mine Sweeper II
https://vjudge.net/contest/585791#problem/B
观察到答案必须 \(\le \dfrac {n\times m}2\)，根据在上一道题目得到的经验，考虑找到两种地位相等、并完全相反的方案。
我们知道，把 B 变成 A 一定可以满足条件；从「完全相反」出发，考虑把所有雷变成空地、所有空地变成雷。
将空地上的数字视为由空地向周围八格的雷连边，可以连到的边的数量。将地图完全翻转后，边除了起点和终点翻转之外，没有任何变化。所以，数字之和不变。
由此我们就得到了分两组的方案，由抽屉原理，必有一组方案的代价 \(\le \dfrac {n\times m}2\)，取较小者即可。
namespace XSC062 {
using namespace fastIO;
const int maxn = 1e3 + 5;
int n, m, res1, res2;
char a[maxn][maxn], b[maxn][maxn];
int main() {
scanf("%d %d", &n, &m);
for (int i = 1; i <= n; ++i)
scanf("%s", a[i] + 1);
for (int i = 1; i <= n; ++i) {
scanf("%s", b[i] + 1);
for (int j = 1; j <= m; ++j) {
res1 += (a[i][j] != b[i][j]);
res2 += (a[i][j] == b[i][j]);
}
}
if (res1 < res2) {
for (int i = 1; i <= n; ++i)
puts(a[i] + 1);
}
else {
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) {
if (a[i][j] == '.')
putchar('X');
else putchar('.');
}
putchar('\n');
}
}
return 0;
}
} // namespace XSC062
C - Ehab's Last Corollary
https://vjudge.net/contest/585791#problem/C
我们尝试证明出题人的猜想……
-
如果整个图上没有环，就整个一棵树
树呢，是一个二分图对不对，然后抽屉原理，我们看两部节点中比较大的那一坨，它的大小一定是 \(\ge \dfrac n2\) 又 \(\ge \dfrac k2\) 的，直接输出就好了。
-
否则，对于一个环，如果它的点数小于等于 \(k\)，那我们直接将它作为第二个问题的答案输出。
-
否则，我们在图的最小环上隔一个点选一个点，一定能选出 \(\left\lfloor\dfrac k2\right\rfloor\) 个相互独立的点。你说为什么它们之间没有直接连边呢？因为我们是在一个比 \(k\) 大的最小环上选的，要是它们之间有直接连边，那就会又构成一个更小的环了。
所以我们只需要找到一个最小的环然后按上述操作得到答案…… 然而找最小环这一点本身不太现实……
这个时候我们怎么办呢？
我们用一点神奇科技。考虑图的 DFS 树。
-
如果有返祖边 \((v, u)\)，且深度 \(d_v-d_u< k\)，那么 \(u\to v\) 在树上的简单路径和返祖边 \((v, u)\) 共同构成一个长度不超过 \(k\) 的环，直接输出。
-
否则，因为 \(d_v-d_u\ge k\)，有 \(d_v\ge k\)，且对于任意 \(d_y-d_x<k\)，返祖边 \((y,x)\) 不存在。
我们仍然考虑上面提到的隔一个取一个的方法。从任意 \(d_v\ge k\) 开始取点，分别取 \(v\) 的 \(0\) 代父辈（即自身），\(2\) 代父辈（即爷爷），\(4\) 代父辈……
为什么这么取就不会出 bug 呢？因为我们上面提到的「对于任意 \(d_y-d_x<k\)，返祖边 \((y,x)\) 不存在」，所以不会有杂边干扰。
-
时间复杂度 \(\mathcal O(n + m)\)。只能说真是妙啊。jly 赛高！
namespace XSC062 {
using namespace fastIO;
const int maxn = 1e5 + 5;
bool vis[maxn];
int n, m, k, x, y;
int f[maxn], dep[maxn];
std::vector<int> g[maxn];
int col[maxn], cnt[5];
void color(int x, int fa, int now) {
col[x] = now, ++cnt[now];
for (auto i : g[x]) {
if (i == fa)
continue;
color(i, x, 3 - now);
}
return;
}
void DFS(int x, int fa) {
vis[x] = 1;
for (auto i : g[x]) {
if (i == fa)
continue;
if (vis[i]) {
if (dep[i] < dep[x] &&
dep[x] - dep[i] < k) {
print(2, '\n');
int p = x, cnt = 1;
while (p != i)
++cnt, p = f[p];
print(cnt, '\n'), p = x;
while (p != i)
print(p, ' '), p = f[p];
print(i, '\n');
exit(0);
}
continue;
}
f[i] = x;
dep[i] = dep[x] + 1;
DFS(i, x);
}
return;
}
void add(int x, int y) {
g[x].push_back(y);
return;
}
int main() {
read(n), read(m), read(k);
for (int i = 1; i <= m; ++i) {
read(x), read(y);
add(x, y), add(y, x);
}
if (m == n - 1) {
print(1, '\n');
color(1, -1, 1);
k = (k + 1) / 2;
x = cnt[1] > cnt[2] ? 1 : 2;
for (int i = 1; i <= n && k; ++i) {
if (col[i] == x)
print(i, ' '), --k;
}
putchar('\n');
return 0;
}
dep[1] = 1, DFS(1, -1);
for (int i = 1; i <= n; ++i) {
if (dep[i] >= k) {
print(1, '\n');
x = i, k = (k + 1) / 2;
while (k--) {
print(x, ' ');
x = f[f[x]];
}
putchar('\n');
break;
}
}
return 0;
}
} // namespace XSC062
D - 景点划分
https://vjudge.net/contest/585791#problem/D
（暴论）总有一天我会死于鼻炎！！！
（打喷嚏）（擤鼻涕）（试图嗑药然后发现自己水杯里的是隔夜水）（再打喷嚏）
? 前言
你打开了题目。你想，不就是从图里抠两个连通块出来吗，这也能进 IOI？
你开始打代码。你突然发现不对劲。你抠掉了一个大小为 \(a\) 的连通块，然后发现剩下的部分裂成了很多个块，其中根本找不到一个大小 \(\ge b\) 的块。
你发现，事情没有这么简单。
这是你吗？不，这不是你，这是我，小丑 lym ?
不妨设 \(a\le b\le c\)，则由抽屉原理，\(a\le \dfrac n3\)。
我们从最特殊的情况开始思考。假如图是树，那么答案怎么求呢？
对于任意一条边，在其左右两边的连通块中，根据抽屉原理，较大者的大小必定 \(\ge \dfrac{n}{2}\)，根据重心的定义，重心必然属于较大连通块。
E - Baggage
https://vjudge.net/contest/585791#problem/E
F - Strange Housing
https://vjudge.net/contest/585791#problem/F
是难得一见的小清新题目（经历过前两题的洗礼之后）。
我们从原图中抽一个生成树出来，比如 DFS 树。
然后我们又知道树是连通二分图，所以我们按照二分图来染色就可以了。
但这么做有个 bug，就是树里有返祖边，这就可能会导致二分图的一个部分里出现在原图中相连的点。
所以我们可以换一种思考方式，把二分图的染色方法带到原图里。
一个点当且仅当周围有染色点或自身为染色点时是可达的。
对于一个点，我们先检查其周围一圈有没有染色点；如果有就不能染色。在 DFS 遍历的时候直接染色即可。
namespace XSC062 {
using namespace fastIO;
const int maxn = 3e5 + 5;
int col[maxn];
bool vis[maxn];
int T, n, m, x, y, cnt;
std::vector<int> g[maxn];
void DFS(int x) {
vis[x] = 1;
for (auto i : g[x]) {
if (col[i] == 1) {
col[x] = 0;
break;
}
}
if (col[x] == -1)
++cnt, col[x] = 1;
for (auto i : g[x]) {
if (vis[i])
continue;
if (col[x] == 1)
col[i] = 0;
DFS(i);
}
return;
}
void add(int x, int y) {
g[x].push_back(y);
return;
}
int main() {
read(T);
while (T--) {
read(n), read(m);
for (int i = 1; i <= n; ++i) {
g[i].clear();
g[i].shrink_to_fit();
vis[i] = 0, col[i] = -1;
}
while (m--) {
read(x), read(y);
add(x, y), add(y, x);
}
cnt = 0, DFS(1);
for (int i = 2; i <= n; ++i) {
if (!vis[i]) {
puts("NO");
goto noSol;
}
}
puts("YES");
print(cnt, '\n');
for (int i = 1; i <= n; ++i) {
if (col[i] == 1)
print(i, ' ');
}
putchar('\n');
noSol: ;
}
return 0;
}
} // namespace XSC062