以后再卡构造我是狗
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();
}