以后再卡构造我是狗
1227G. Not Same
给定 $n$ 个 $[1, n]$ 的数，要求操作至多 $n + 1$ 次数，每次操作将一个独特的下标集合的数减一，要求将所有数变成 $0$。
1110G. Tree-Tac-Toe
给一个树，树上有些点染了先手的颜色，其余点没染色。现在先后手轮流给没染色的点染黑白，如果某种颜色形成了一个大小不小于 3 的同色联通块则立刻获胜，如果染满了则平局。问最优策略下的游戏结果。
spolier 烂掉了，手动分割线
Solutions
Sol 1227G
我尝试的第一种构造是：第 $i$ 次操作强制删 $i$，不删 $i \bmod n+ 1$。但是这样对于
5
5 1 1 1 1
的数据就解掉了，因为会在输出两行 1 0 0 0 0。后来改成了 $i – 1$ 才行，Tommy 证了，是真的。
#include <bits/stdc++.h>
using namespace std;
#define N 1005
int n;
int a[N], b[N][N];
pair<int, int> c[N];
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i++) scanf("%d", a + i);
for (int i = 1; i <= n; i++) c[i] = {a[i], i};
sort(c + 1, c + n + 1);
memset(b, -1, sizeof b);
for (int i = 1; i <= n; i++) {
a[c[i].second]--;
b[i][c[i].second] = 1;
b[i + 1][c[i].second] = 0;
}
for (int i = 1; i <= n; i++) {
for (int j = 1; a[c[i].second] && j <= n + 1; j++) {
if (b[j][c[i].second] == -1) b[j][c[i].second] = 1, a[c[i].second]--;
}
}
bool flag = 0;
for (int i = 1; i <= n; i++) flag |= b[n + 1][i] == 1;
printf("%d\n", n + flag);
for (int i = 1; i <= n + flag; i++) {
for (int j = 1; j <= n; j++) {
printf("%d", max(0, b[i][j]));
}
puts("");
}
}
Sol 1110G
Tommy 太神啦！什么题都做过不愧是体重比我重 60 斤的 Tommmmmmmmmmmmy。 首先和井字棋相同，先手必不败，我不会直接证但是感受下外加后面的构造可以证明，我们先不考虑初始颜色，讨论如下：
- 存在度数为 4 的点，则先手必胜；
- 存在度数为 3 的点存在两个出度的度数不小于 2，则先手必胜。
- 存在两个距离为偶数的度数为 3 的点，则先手必胜，这一种情况可以看成 1 的拓展。
- 其余情况为平局，包括只有两个度数为 3 的距离为奇数的点以及链。
这么讨论很显然，我就差这么 一 点就想到第三个了，但是很可惜做不到。我是狗！
接下来还要处理有颜色的点，可以转化为：先手选择了这个点，那么后手必然要选择我新建的辅助节点。这其实可以通过外接一个根度数为 $2$ 的大小为 $3$ 的子树来做到。于是就做完了。
#include <bits/stdc++.h>
using namespace std;
#define N 2011111
int n, node;
vector <int> E[N];
char s[N / 4];
bool ans;
int dep[N];
bool vis[2];
void dfs(int x, int fa) {
if (E[x].size() >= 4) ans = 1;
else if (E[x].size() == 3) {
int tot = 0;
for (auto v : E[x]) tot += E[v].size() > 1;
if (tot >= 2) ans = 1;
if (vis[dep[x]]) ans = 1;
vis[dep[x]] = 1;
}
for (auto v : E[x]) if (v != fa) dep[v] = dep[x] ^ 1, dfs(v, x);
}
void work() {
scanf("%d", &n);
node = n;
for (int i = 1; i < n; i++) {
int u, v;
scanf("%d%d", &u, &v);
E[u].push_back(v);
E[v].push_back(u);
}
scanf("%s", s + 1);
for (int i = 1; i <= n; i++) {
if (s[i] == 'W') {
E[i].push_back(++node);
E[node].push_back(i);
node += 2;
E[node - 2].push_back(node - 1);
E[node - 1].push_back(node - 2);
E[node - 2].push_back(node - 0);
E[node - 0].push_back(node - 2);
}
}
vis[0] = vis[1] = 0;
ans = 0;
dfs(1, -1);
if (ans) puts("White");
else puts("Draw");
for (int i = 1; i <= node; i++) E[i].clear();
}
int main() {
int T;
scanf("%d", &T);
while (T--) work();
}