Part 2: $[140, 180)$
acm.sgu.ru@CodeForces

Continue reading

以后再卡构造我是狗

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。 首先和井字棋相同，先手必不败，我不会直接证但是感受下外加后面的构造可以证明，我们先不考虑初始颜色，讨论如下：

1. 存在度数为 4 的点，则先手必胜；
2. 存在度数为 3 的点存在两个出度的度数不小于 2，则先手必胜。
3. 存在两个距离为偶数的度数为 3 的点，则先手必胜，这一种情况可以看成 1 的拓展。
4. 其余情况为平局，包括只有两个度数为 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();
}

呐，人总是要有点梦想，万一实现了呢。

acm.sgu.ru@CodeForces
Part 1: $[100, 140)$

100. A+B

print(sum(map(int, input().split())))

Continue reading