Codeforces Round 1129 (Div. 2) 题解

· · 题解

Link

A - Subset Selecting

直接从小到大贪心，维护当前没有使用的元素数量即可。

:::success[Code]

#include <bits/stdc++.h>

using namespace std;

constexpr int N = 105;

int n, k, a, c[N], s;
bool t;

void solve() {
    cin >> n >> k, s = t = 0;
    for(int i = 0; i <= n; ++i) {
        c[i] = 0;
    }
    for(int i = 1; i <= n; ++i) {
        cin >> a, ++c[a];
    }
    for(int i = 0; i <= n; ++i) {
        if(not c[i] or s + c[i] < k) {
            cout << i << '\n';
            return;
        }
        s += c[i] - k;
    }
    return;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int T = 1; cin >> T;
    while(T--) solve();
    return 0;
}

:::

B - Sequence Decreasing

先考虑长度为 m 的序列 b 什么时候是好的。注意到若 b 中有 0 则一定是好的。当 b 中没有 0 时，考虑造出一个 0。贪心地保留 \min(b)，因为一共只能进行 m - 1 次操作，所以当 \min(b) \lt m 时 b 是好的。对于长度为 n 的序列 a，若 \min(a) \lt n 则 a 本身是好的，答案为 n；否则不存在好的子序列，答案为 0。

:::success[Code]

#include <bits/stdc++.h>

using namespace std;

int n, a, mn;

void solve() {
    cin >> n, mn = n;
    for(int i = 1; i <= n; ++i) cin >> a, mn = min(mn, a);
    if(mn < n) cout << n << '\n';
    else cout << "0\n";
    return;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int T = 1; cin >> T;
    while(T--) solve();
    return 0;
}

:::

C - Edge Addeleting

感觉是很好的 D2C。

注意到如果 v 和 n 不在 1 的同一个子树中，(1, v) 一定是没用的，于是先忽略掉这种边。又发现 1 到 n 的路径上至多经过一条新加的边，于是我们可以独立考虑留下每一条边的最大答案。考虑加入 (1, v) 后，删除哪条边是最优的，发现是原树上 1 到 n 方向上的第一条边，此时的答案是 d_v + 1，其中 d_v 表示 v 与 n 在原树上的距离。最终答案就是所有边的答案的最大值，与 d_1 的最大值。

:::success[Code]

#include <bits/stdc++.h>

using namespace std;

constexpr int N = 500'005;

int n, m, d[N], ans;
vector<int> to[N];
queue<int> q;

void solve() {
    cin >> n >> m;
    for(int u = 1; u <= n; ++u) {
        d[u] = -1, to[u].clear();
    }
    for(int _ = 1; _ < n; ++_) {
        int u, v; cin >> u >> v;
        to[u].push_back(v);
        to[v].push_back(u);
    }
    d[n] = 0, q.push(n);
    while(q.size()) {
        int u = q.front();
        q.pop();
        if(u == 1) continue;
        for(int v : to[u]) {
            if(d[v] < 0) {
                d[v] = d[u] + 1;
                q.push(v);
            }
        }
    }
    ans = d[1];
    while(m--) {
        int v; cin >> v;
        ans = max(ans, d[v] + 1);
    }
    cout << ans << '\n';
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int T = 1; cin >> T;
    while(T--) solve();
    return 0;
}

:::

D - Number Operating

这题个人差似乎挺大的，可能会有点创人；感觉 D2 有点难，本来想放后面，但调度员没同意。最后看来 D2 也成为了整场最大的骂点。

容易想到把若干个操作一视作一组，即花费 k 的代价令 x \gets x + 2^k - 1，并且不允许出现连续的两组操作。设 n \in [2^k, 2^{k + 1}) (k \gt 1)，那么此时有两种选择：

容易证明此时进行代价 \lt k 的操作是一定不优的。于是有：

f(n) = \min(f(n - 2^k + 2) + k + 1, 2^{k + 1} - n + k)

每次递归 n 都大约减半，于是直接做即可。时间复杂度 O(\sum (r - l + 1) \log V)。以上是 D1。

但还可以更优。设 g(n) 为 f(n) 的前缀和。注意到 f(n) = O(\log^2 V)，于是在 [2^k, 2^{k + 1}) 只有后 O(\log^2 V) 个位置的 f(n) 可能取到后者。于是设阈值 B = O(\log^2 V)，预处理出 [2^{k + 1} - B, 2^{k + 1}) 中每个 n 的 f(n) 并求前缀和。计算 g(n) 时，将其分为 [0, 2^k), [2^k, \min(2^{k + 1} - B, n + 1)), [2^{k + 1} - B, n) 三段，其中第三段可能是滚木。对于第一段可以直接递归；对于第二段，因为这些位置满足 f(n) = f(n - 2^k + 2) + k + 1，所以也可以直接递归；对于第三段，我们前面已经预处理出来了，直接算即可。

注意到递归过程中我们只会访问 O(\log V) 个不是 2^k - 1 的位置，于是先把 g(2^k - 1) 预处理出来，询问复杂度就是 O(\log V) 的了。因为预处理要计算 O(\log^3 V) 个 f(n) 值，所以总复杂度是 O(\log^4 V + t \log V)。

但还可以更优。注意到 f(n) \le f(n + 1) + 1，即 h(n) = f(n) + n 单调不降。考虑 f(n) 的递归式子中，前者什么时候取到 \min，设 m = n - 2^k + 2，容易得到 h(m) \le 2^k - 1。因为 h(m) 单调不降，所以在 [2^k, 2^{k + 1}) 中，f(n) 取前者的一定是一个前缀，取后者的一定是一个后缀。考虑把这个分界点求出来，可以直接对 h(m) 二分。求出分界点后，前两段还是直接递归，第三段就变成一个等差数列了。时间复杂度 O(\log^3 V + t \log V)，注意到二分的范围只有 O(\log^2 V) 于是可以做到 O(\log^2 V \log \log V + t \log V)。

但还可以更优。考虑 h(m) 的意义，它本质上是给 f(m) 的每一步操作加上了这一步的变化量的代价。即每次可以花 2^k + 1 的代价令 x \gets x + 2^k，其中 k 表示已经连续做了几次；或免费令 x \gets x - 1。现在给定 h(m) \le 2^k - 1 最大化 m，本质上就是在做一个反过来的贪心，同样把连续的操作一视作一组，贪心地从大到小选即可，显然只会选 O(\log V) 组。时间复杂度 O(\log^2 V + t \log V)。

:::success[Code]

#include <bits/stdc++.h>

using namespace std;

#define int long long

constexpr int mod = 998'244'353;
constexpr int inv2 = (mod + 1) >> 1;

int l, r, pos[60], pre[60];

int g(int n) {
    if(n <= 1) return max(n, 0ll);
    if(n == 2) return 4;
    if(n == 3) return 6;
    int k = __lg(n), t = min(n - (1ll << k) + 2, pos[k]), res = 0;
    res = pre[k];
    res = (res + g(t) + mod - 1 + (t - 1) % mod * (k + 1)) % mod;
    t += (1ll << k) - 2, res = (res + ((1ll << (k + 2)) + 2 * k - t - n - 1) % mod * ((n - t) % mod) % mod * inv2) % mod;
    return res;
}

void solve() {
    cin >> l >> r;
    cout << (g(r) + mod - g(l - 1)) % mod << '\n';
    return;
}

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    for(int k = 0; k < 60; ++k) {
        int rem = (1ll << k) + 1;
        pos[k] = 1;
        for(int i = k; i >= 2; --i)
            if((1ll << i) + i - 1 <= rem)
                rem -= (1ll << i) + i - 1, pos[k] += (1ll << i) - 2;
        pre[k] = g((1ll << k) - 1);
    }
    int T = 1; cin >> T;
    while(T--) solve();
    return 0;
}

:::

E - Tree Guessing

挺有意思的交互。这题原本放的 F，Token Re-Moving 原本放的 E，但是因为太多 tester 和这题对上脑电波就被放到 E 了。

交互库返回的东西的信息太杂了，考虑搞些有用的信息出来。若令根的权值为 n - 1，发现此时返回的恰好是权值为 n 的点的子树大小。于是有了一个简单的 O(n^2) 做法，每次选两个点，以一个点为根询问另一个点的子树大小，各问一次就可以验证这条边是否存在了。但这个做法跟正解没啥关系。

不妨令 1 为根。考虑先问出每个点的子树大小，此时还剩 n - 1 次询问，猜测需要对每个点询问一次求出它的父亲。一个性质是子树大小最大的点的父亲一定是 1，这启发我们按照子树大小从大到小排序。此时，每个点的父亲都排在它前面，于是考虑依次把每个点加到树中。加入一个点时，我们已经知道了它前面的点构成的树的形态，此时需要确定当前点的父亲。考虑以当前点为根询问，因为它前面的每个点都可能成为它的父亲，它后面的点并不重要，所以令前面的点的权值都大于当前点的权值，后面的点的权值都小于当前点的权值。

此时以当前点为根询问的结果等于以它的父亲为根询问的结果，于是只需要给它前面的点构造一个权值序列使得以每个点询问所得权值互不相同即可。容易想到按 BFS 序构造，并容易证明这是正确的。求出父亲后把它加到树上即可。

询问次数 2n - 2，稍微实现一下是可以做到 2n - 4 的，再精细实现一下在随机数据下的询问次数应该能更少，但没啥意义就只开了 2n - 2。之前问过 AI 好像没啥更优的做法。

:::success[Code]

#include <bits/stdc++.h>

using namespace std;

constexpr int N = 505;

int n, sz[N], p[N], a[N], cur, res, tmp;
vector<int> to[N];
queue<int> q;

int query(int x, int *p) {
    cout << "? " << x;
    for(int u = 1; u <= n; ++u) {
        cout << ' ' << p[u];
    }
    cout << endl;
    int res; cin >> res;
    return res;
}

void solve() {
    cin >> n;
    p[1] = n, p[2] = n - 1;
    for(int u = 3; u <= n; ++u) {
        p[u] = u - 2;
    }
    for(int u = 2; u <= n; ++u) {
        swap(p[u - 1], p[u]);
        sz[u] = query(1, p) - n * (n - 1);
        a[u] = u;
    }
    a[1] = 1;
    sort(a + 2, a + n + 1, [](int u, int v) {
        return sz[u] > sz[v];
    });
    for(int i = 2; i <= n; ++i) {
        cur = 1;
        q.push(1);
        while(q.size()) {
            int u = q.front();
            q.pop();
            p[u] = ++cur;
            for(int v : to[u]) {
                q.push(v);
            }
        }
        p[a[i]] = 1;
        for(int j = i + 1; j <= n; ++j) {
            p[a[j]] = j;
        }
        res = query(a[i], p);
        res -= (i + 1 + n) * (n - i) / 2 + i;
        for(int j = 1; j < i; ++j) {
            tmp = p[a[j]] - 1;
            if(res == tmp * (i - 1) + (i - tmp) * (i - tmp - 1) / 2) {
                to[a[j]].push_back(a[i]);
            }
        }
    }
    cout << "!\n";
    for(int u = 1; u <= n; ++u) {
        for(int v : to[u]) {
            cout << u << ' ' << v << '\n';
        }
        to[u].clear();
    }
    fflush(stdout);
    return;
}

int main() {
    int T = 1; cin >> T;
    while(T--) solve();
    return 0;
}

:::

F - Token Re-Moving

感觉这题会被骂，最开始投的 D2E 不知道为啥就给过了，后来又被换到 D2F 了。验题的时候有 CM 秒了，有 M 不会，有 IM 写其他做法没卡过去，也有 IGM 评价这题为 "Amazing problem"。不太懂。

这场本来有个叫 Token Moving 的题的，题目名在致敬 CF2119D，后来有了这题就自然而然地取名 Token Re-Moving 了（）。然而后来 Token Moving 被删了就只剩 Token Re-Moving 了。

直接做应该是没啥前途的，于是反过来考虑一个点 u 会给哪些根 r 产生贡献，条件是：以 r 为根时，不存在 u 的祖先比 u 更先操作，即 u 到 r 的路径上不存在比 u 更先操作的点。也即，若删去所有比 u 更先操作的点，此时 u 和 r 一定在同一个连通块内。同时注意到，若以 u 为根，对于它的每个儿子 v，u 对 v 子树内的贡献是相同的，均为 n 减去 v 的子树大小。

考虑维护这个过程。删点是困难的，考虑倒过来变成加点并维护重构树。于是剩下的就是简单的了。加入点 u 时，对于 u 的每个已经被加入的邻居 v，在 v 所在的连通块的根 w 上加上对应的贡献，并把 w 在重构树上的父亲设为 u。最后再在重构树上做一次 DFS 把贡献下放到子树即可，详见代码。

:::success[Code]

#include <bits/stdc++.h>

using namespace std;

constexpr int mod = 998'244'353;
constexpr int N = 500'005;

void M(int &x) { x -= (x >= mod ? mod : 0); }

int n, a[N], p[N], fa[N], ans[N], tmp;
vector<int> to[N], nto[N];
bool vis[N];

struct DSU {
    int fa[N];
    void init(int n) {
        for(int x = 1; x <= n; ++x) {
            fa[x] = x;
        }
    }
    int find(int x) {
        return fa[x] == x ? x : fa[x] = find(fa[x]);
    }
    void merge(int x, int y) {
        x = find(x), y = find(y);
        if(x == y) return;
        fa[x] = y;
    }
} dsu;

void dfs1(int u) {
    for(int v : to[u]) {
        if(v != fa[u]) {
            fa[v] = u, dfs1(v);
            M(a[u] += a[v]);
        }
    }
}

void dfs2(int u) {
    for(int v : nto[u]) {
        M(ans[v] += ans[u]);
        dfs2(v);
    }
}

void solve() {
    cin >> n;
    for(int u = 1; u <= n; ++u) {
        to[u].clear(), nto[u].clear(), ans[u] = 0;
    }
    for(int _ = 1; _ < n; ++_) {
        int u, v; cin >> u >> v;
        to[u].push_back(v);
        to[v].push_back(u);
    }
    for(int u = 1; u <= n; ++u) {
        cin >> a[u];
    }
    for(int i = 1; i <= n; ++i) {
        cin >> p[i];
    }
    dfs1(1);
    dsu.init(n);
    for(int u = 1; u <= n; ++u) {
        vis[u] = 0;
    }
    for(int i = n; i; --i) {
        int &u = p[i];
        for(int v : to[u]) {
            if(vis[v]) {
                if(v == fa[u]) {
                    v = dsu.find(v);
                    M(ans[v] += a[u]);
                } else {
                    M(tmp = a[1] + mod - a[v]);
                    v = dsu.find(v);
                    M(ans[v] += tmp);
                }
                nto[u].push_back(v);
                dsu.merge(v, u);
            }
        }
        vis[u] = 1;
    }
    M(ans[p[1]] += a[1]), dfs2(p[1]);
    for(int u = 1; u <= n; ++u) {
        cout << ans[u] << " \n"[u == n];
    }
    return;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int T = 1; cin >> T;
    while(T--) solve();
    return 0;
}

:::