Codeforces Round 899 (Div. 2) A~D 题解 | JorbanS

A - Increasing Sequence

int solve() {
    int n; cin >> n;
    int res = 0;
    while (n --) {
        int x; cin >> x;
        res ++;
        if (res == x) res ++;
    }
    return res;
}
1
2
3
4
5
6
7
8
9
10

B - Sets and Union

int solve() {
    int n; cin >> n;
    vector<vector<int>> e(N), g(N);
    set<int> st;
    for (int i = 1; i <= n; i ++) {
        int k; cin >> k;
        while (k --) {
            int x; cin >> x;
            st.insert(x);
            e[i].push_back(x); // 集合 i 存放的数
            g[x].push_back(i); // 数 x 存放的集合序号
        }
    }
    int res = 0;
    for (auto u : st) { // 枚举删除每个变量
        vector<bool> vis(N);
        set<int> s;
        for (auto i : g[u]) vis[i] = true; // vis[i] 表示集合 i 被删除
        for (int i = 1; i <= n; i ++)
            if (!vis[i])
                for (auto j : e[i]) s.insert(j);
        res = max(res, (int)s.size());
    }
    return res;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

C - Card Game

题解 从后面往前面删掉每一个奇数位的正数，不会影响前面的数

如果删掉位置 $2$ 的数，那么后面所有的正数都可以被删掉

接下来只要特判位置 $1$ 和位置 $2$ 的数，取 $max$ 即可

ll solve() {
    int n; cin >> n;
    ll res = 0;
    for (int i = 1; i <= n; i ++) {
        cin >> a[i];
        if (i >= 3 && a[i] > 0) res += a[i];
    }
    res += max(0, a[1] + (n > 1) * max(0, a[2]));
    return res;
}
1
2
3
4
5
6
7
8
9
10

D - Tree XOR

题意 给定一棵树，节点编号为 $1\sim n$，点权分别为 $a_i$

给定操作：选定点 $r$ 和数值 $c$，将 $r$ 子树所有节点（包括 $r$）都异或上 $c$，代价为 $r$ 子树大小与 $c$ 的乘积

对于树根为 $1,2,...,n$ 时，使得数中的点权值全部相等，花费的最小代价

题解 考虑树根为 $1$ 的情况，分治思想，从叶子节点往上回溯处理，每次将子节点全部异或上一个值使得与父节点相等。因为两个节点间和菊花图都只有一种情况，因此回溯上去的结果也只有一种情况，由于异或顺序时可以调换的，所以所有乱序的操作，都可以排序成回溯操作，因此有且只有一种情况能够使得所有操作后，所有点权相等

对于节点 $v$，它的父节点为 $u$，此时已经保证了 $v$ 的所有子节点的点权都等于 $v$ 的点权，由于有 $a_v\oplus c=a_u$，故 $c=a_u\oplus a_v$。由于在叶节点，所有子节点的点权已相等（只有一个点），故此分治是合法的

故树根为 $1$ 的代价为 $\sum size_v\times (a_v\oplus a_u) \$

接下来进行换根操作：

当将根由 $u$ 换成其子节点 $v$，对于 $v$ 的所有节点，无需再进行异或操作，故代价减小 $siz{e}_v\times (a_v\oplus a_u)$，但需要对 $u$ 这一子树的所有节点进行异或操作，代价增加 $(n-siz{e}_v)\times (a_v\oplus a_u)$

则 $an{s}_v=an{s}_u+(n-2\times siz{e}_v)\times (a_v\oplus a_u)$

void solve() {
    int n; cin >> n;
    vector<int> a(n + 1);
    for (int i = 1; i <= n; i ++) cin >> a[i];
    vector<vector<int>> e(n + 1);
    for (int i = 1; i < n; i ++) {
        int u, v; cin >> u >> v;
        e[u].push_back(v), e[v].push_back(u);
    }
    vector<ll> sz(n + 1, 1), ans(n + 1);
    function<void(int, int)> dfs = [&](int u, int fa) {
        for (auto v : e[u]) {
            if (v == fa) continue;
            dfs(v, u);
            sz[u] += sz[v];
            ans[1] += (a[u] ^ a[v]) * sz[v];
        }
    };
    dfs(1, 1);
    function<void(int, int)> dfs2 = [&](int u, int fa) {
        for (auto v : e[u]) {
            if (v == fa) continue;
            ans[v] = ans[u] + (a[u] ^ a[v]) * (n - sz[v] * 2);
            dfs2(v, u);
        }
    };
    dfs2(1, 1);
    for (int i = 1; i <= n; i ++) cout << ans[i] << ' ';
    cout << endl;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30