构造杂题。
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 XSC062C - 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 XSC062D - 景点划分
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}\)，根据重心的定义，重心必然属于较大连通块。
后面鸽了。总之先放个代码在这里。
namespace XSC062 {
using namespace fastIO;
const int maxn = 1e5 + 5;
int org[5];
bool book[maxn];
int solFlag, sumFa, faP;
int siz[maxn], col[maxn];
int n, m, a, b, c, x, y, P;
bool vis[maxn], legSon[maxn];
std::vector<int> w[maxn], g[maxn];
void DFS(int x, int fa) {
bool flag = 1;
vis[x] = 1, siz[x] = 1;
for (auto i : w[x]) {
if (vis[i]) continue;
DFS(i, x);
if (siz[i] > n / 2) flag = 0;
siz[x] += siz[i];
g[x].push_back(i);
}
if (n - siz[x] > n / 2) flag = 0;
if (flag && !P) {
P = x, faP = fa;
if (n - siz[x] >= a)
solFlag = fa;
else {
for (auto i : g[x]) {
if (siz[i] >= a) {
solFlag = i;
break;
}
}
}
}
return;
}
void fillA(int x) {
if (a == 0) return;
col[x] = 1, --a;
for (auto i : g[x]) fillA(i);
return;
}
void fillB(int x) {
if (b == 0) return;
col[x] = 2, --b;
for (auto i : g[x]) {
if (x == P && i == solFlag)
continue;
fillB(i);
}
return;
}
void fillC(void) {
for (int i = 1; i <= n; ++i)
if (!col[i]) col[i] = 3;
return;
}
void DFS1(int x) {
if (!a || x == P) return;
col[x] = 1, --a;
for (auto i : g[x]) DFS1(i);
return;
}
void DFS2(int x) {
if (b == 0) return;
if (!col[x]) col[x] = 2, --b;
for (auto i : g[x]) DFS2(i);
return;
}
void func(void) {
int pos[5] = {};
if (a >= b && b >= c) // cba
org[1] = 3, org[2] = 2, org[3] = 1;
else if (a >= b && a >= c) // bca
org[1] = 2, org[2] = 3, org[3] = 1;
else if (a >= b) // bac
org[1] = 2, org[2] = 1, org[3] = 3;
else if (c >= b) // abc
org[1] = 1, org[2] = 2, org[3] = 3;
else if (c >= a) // acb
org[1] = 1, org[2] = 3, org[3] = 2;
else // cab
org[1] = 3, org[2] = 1, org[3] = 2;
pos[1] = a, pos[2] = b, pos[3] = c;
std::sort(pos + 1, pos + 4);
a = pos[1], b = pos[2], c = pos[3];
return;
}
void ADD(int x) { // 判断儿子是否合法
if (x == P)
return;
book[x] = 1;
for (auto i : w[x]) {
if (i == P && x != faP) legSon[x] = 1;
if (!book[i]) ADD(i);
}
return;
}
void DFS3(int x) { // Sub2 染头上
if (!a || x == P) return;
col[x] = 1, --a;
for (auto i : g[x]) DFS3(i);
return;
}
void DFS4(int x) { // Sub2 染儿子
if (a == 0) return;
col[x] = 1, --a;
for (auto i : g[x]) DFS4(i);
return;
}
void DFS5(int x) { // Sub2 染 B 色
if (b == 0) return;
col[x] = 2, --b;
for (auto i : g[x]) {
// 如果子树加入了 A
// 那么起码子树的根是会被染的。
if (col[i]) continue;
DFS5(i);
}
return;
}
int main() {
read(n), read(m);
read(a), read(b), read(c), func();
while (m--) {
read(x), read(y), ++x, ++y;
w[x].push_back(y), w[y].push_back(x);
}
DFS(1, -1);
if (solFlag) {
if (solFlag == faP) DFS1(1), DFS2(P);
else fillA(solFlag), fillB(1);
fillC();
}
else {
ADD(1), sumFa = n - siz[P];
auto now = g[P].begin(), ex = now;
while (sumFa < a) {
while (now != g[P].end() && !legSon[*now]) ++now;
if (now == g[P].end()) goto noSol;
sumFa += siz[*(ex = now++)];
}
auto pos = g[P].begin();
DFS3(1);
for (;; ++pos) {
if (!legSon[*pos]) continue;
DFS4(*pos);
if (pos == ex) break;
}
DFS5(P), fillC();
}
noSol: ;
for (int i = 1; i <= n; ++i) {
#ifdef ONLINE_JUDGE
print(org[col[i]], ' ');
#else
print(col[i], ' ');
#endif
}
putchar('\n');
return 0;
}
} // namespace XSC062
int main() {
XSC062::main();
return 0;
}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