VP 2024 CCPC 哈尔滨

2024 China Collegiate Programming Contest (CCPC) Harbin Onsite (The 3rd Universal Cup. Stage 14: Harbin)
比赛链接

Problems	AC
A. Build a Computer	⊕
B. Concave Hull	⊕
C. Giving Directions in Harbin	○
D. A Simple String Problem
E. Marble Race
F. 1D Galaxy
G. Welcome to Join the Online Meeting!	○
H. Subsequence Counting
I. A Brand New Geometric Problem
J. New Energy Vehicle	○
K. Farm Management	○
L. A Game On Tree	⊕
M. Weird Ceiling	○

M

void solve() {
    int n = read();

    vector<int> a;
    // a.eb(1);

    for (int i = 1; i * i <= n; i++) {
        if (n % i == 0) {
            a.eb(i);

            if (n / i != i) {
                a.eb(n / i);
            }
        }
    }

    std::sort(a.begin(), a.end());

    int ans = 0;
    int m = a.size();
    for (int i = 1; i < m; i++) {
        // cout << "a: " << a[i] << '\n';
        ans += n / a[i - 1] * (a[i] - a[i - 1]);
    }

    ans += n / a[m - 1] * (n - a[m - 1] + 1);

    cout << ans << '\n';
}

G

void solve() {
    int n = read(), m = read(), k = read();

    vector<int> bad(n + 1);
    for (int i = 1; i <= k; i++) {
        int x = read();
        bad[x] = 1;
    }

    vector<int> vis(n + 1);
    vector<vector<int>> g(n + 1);

    using pii = std::pair<int, int>;

    int timer = 0;
    vector<int> idx(n + 1);
    vector<vector<int>> ans(n + 1);

    std::function<void(int)> dfs = [&](int u) {

        vis[u] = 1;
        if (bad[u]) return;

        for (int v : g[u]) {
            if (!vis[v]) {
                idx[++timer] = u;
                break;
            }
        }

        for (int v : g[u]) {
            if (!vis[v]) {

                ans[u].eb(v);
                dfs(v);
            }
        }
    };

    for (int i = 1; i <= m; i++) {
        int u = read();
        int v = read();
        g[u].eb(v);
        g[v].eb(u);
    }
    for (int i = 1; i <= n; i++) {
        if (!bad[i]) {
            dfs(i);
            break;
        }
    }

    for (int i = 1; i <= n; i++) {
        if (!vis[i]) {
            cout << "No\n";
            return;
        }
    }

    cout << "Yes\n";
    cout << timer << '\n';
    for (int i = 1; i <= timer; i++) {
        int u = idx[i];
        cout << u << ' ' << ans[u].size();

        for (int v : ans[u]) {
            cout << ' ' << v;
        }
        puts("");
    }
}

K 二分

按 w 从大到小排序，枚举操作的 i。那么比这个收益小的都卡底线。收益大的是一段前缀，二分这个前缀就做完了。

void solve() {
    int n = read(), m = read();

    vector<Node> a(n + 1);
    for (int i = 1; i <= n; i++) {
        a[i].w = read();
        a[i].l = read();
        a[i].r = read();
    }

    std::sort(a.begin() + 1, a.end());

    int ans = 0;

    int tim = 0;
    int tot = 0;
    for (int i = 1; i <= n; i++) {
        tim += a[i].l;
        tot += a[i].l * a[i].w;
    }

    vector<int> sum(n + 1);
    vector<int> sumw(n + 1);
    for (int i = 1; i <= n; i++) {
        sum[i] = sum[i - 1] + a[i].r - a[i].l;
        sumw[i] = sumw[i - 1] + (a[i].r - a[i].l) * a[i].w;
    }

    for (int i = 1; i <= n; i++) {
        int res = tot - a[i].l * a[i].w;

        int rem = max(0LL, m - tim + a[i].l);

        int pos = 0;
        for (int l = 1, r = i - 1; l <= r; ) {
            int mid = l + r >> 1;
            if (sum[mid] <= rem) {
                pos = mid, l = mid + 1;
            } else {
                r = mid - 1;
            }
        }

        // cout << pos << " ";
        // cout << rem << " ";
        // cout << res << " ";
        // cout << " | ";

        res += sumw[pos];
        rem -= sum[pos];
        pos++;
        res += rem * a[pos].w;

        // cout << i << " ";
        // cout << pos << " ";
        // cout << rem << " ";
        // cout << res << " ";
        // cout << '\n';

        ans = max(ans, res);
    }

    cout << ans << '\n';
}

L TreeDP、期望

首先期望是假的，算总收益再除去方案数即可。

考虑拆下这个期望，平方拆开来是每个数的平方加上选两个项乘起来。

$$
\left(\left|e_1\right|+\left|e_2\right|+\ldots+\left|e_k\right|\right)^2=\sum_{i=1}^k\left|e_i\right|^2+\sum_{1 \leq i, j \leq k}\left|e_i\right| \cdot\left|e_j\right|
$$

这里的 $e_i$ 均为 $1$。

一种选法的贡献可以分为两种：

• 一种是由公共边 $e_i$ 产生的
• 一种是由有序对 $(e_i, e_j)$ 产生的

不妨设 $siz[u]$ 为 $u$ 的子树大小，$sum[u] = \sum_{v \in subtree_u}{(siz[v])^2}$。

分别讨论下这个贡献怎么算就行了，sol 写的很清楚了不再赘述

void solve() {
    int n = read();

    vector<vector<int>> g(n + 1);

    for (int i = 1; i < n; i++) {
        int u = read();
        int v = read();
        g[u].eb(v);
        g[v].eb(u);
    }

    Z ans = 0;
    vector<Z> siz(n + 1), sum(n + 1);
    std::function<void(int, int)> dfs = [&](int u, int fa) {
        siz[u] = 1;

        for (int v : g[u]) {
            if (v == fa) continue;

            dfs(v, u);
            siz[u] += siz[v];
            sum[u] += sum[v];
        }

        Z t = sum[u];
        sum[u] += siz[u] * siz[u];

        
        for (int v : g[u]) {
            if (v == fa) continue;

            ans += siz[v] * siz[v] * (n - siz[v]) * (n - siz[v]);
            ans += 2 * (n - siz[v]) * (n - siz[v]) * (sum[v] - siz[v] * siz[v]);
            ans += (t - sum[v]) * sum[v];
        }

    };
    dfs(1, 0);

    // for (int i = 1; i <= n; i++) {
    //     cout << siz[i] << '\n';
    // }
    // puts("------");
    // for (int i = 1; i <= n; i++) {
    //     cout << sum[i] << '\n';
    // }
    // puts("------");

    ans /= n * (n - 1) / 2;
    ans /= n * (n - 1) / 2;
    cout << ans << '\n';
}

A 构造

唉唉 VP 的时候被这个痛苦折磨。构造解的时候不应该想着具体化的最优策略，应该好好想想形式化的表述的

void solve() {
    int L = read();
    int R = read();

    vector<int> d(1000);
    
    int st = 1;
    int ed = 2;
    d[0] = ed;

    using pii = std::pair<int, int>;
    vector<vector<pii>> g(1000);

    for (int i = 1; i <= 20; i++) {
        d[i] = ed + i;

        g[d[i]].eb(d[i - 1], 0);
        g[d[i]].eb(d[i - 1], 1);
    }

    int cur = 22; // 20(log) + 1(st) + 1(ed)
    vector ts(1000, vector<int>(2, -1)); // trie

    auto get_id = [&](int p) {
        vector<int> s;
        for (; p; p >>= 1) s.eb(p % 2);
        std::reverse(s.begin(), s.end());
        int now = st;
        for (auto x : s) {
            if (ts[now][x] == -1) {
                ts[now][x] = ++cur;
                g[now].eb(cur, x);
            }
            now = ts[now][x];
        }
        return now;
    };

    auto cons = [&](this auto &&self, int l, int r, int lb, int rb, int lv, int p) -> void {
        if (l == lb and r == rb) {
            int w = 0, f = p / 2;
            if (f * 2 + 1 == p) {
                w = 1;
            }

            int id = get_id(f);
            g[id].eb(d[lv], w);
            return;
        }
        int mid = lb + rb >> 1;
        if (r <= mid) {
            self(l, r, lb, mid, lv - 1, p * 2);
        } else if (mid < l) {
            self(l, r, mid + 1, rb, lv - 1, p * 2 + 1);
        } else {
            self(l, mid, lb, mid, lv - 1, p * 2);
            self(mid + 1, r, mid + 1, rb, lv - 1, p * 2 + 1);
        }
        return;
    };

    cons(L, R, 0, (1 << 20) - 1, 20, 0);

    // for (int i = 1; i <= cur; ++i) {
    //     printf("Node %d:  ", i);
    //     for (auto v : g[i]) 
    //         printf("%d|%d ", v.first, v.second); 
    //     puts("");
    // }

    int n = 1;
    std::map<int, int> idx;
    idx[1] = 1;
    vector<int> vis(1000);
    auto dfs = [&](this auto &&self, int u) -> void {
        vis[u] = 1;
        for (auto [v, dis] : g[u]) {
            if (vis[v]) continue;
            self(v);
        }
    };
    dfs(1);
    for (int i = 2; i <= cur; i++) {
        if (!vis[i]) continue;
        idx[i] = ++n;
    }

    vector<vector<pii>> G(1000);
    for (int i = 1; i <= cur; i++) {
        if (!vis[i]) continue;
        for (auto [j, dis] : g[i]) {
            int u = idx[i];
            int v = idx[j];
            G[u].eb(v, dis);
        }
    }

    cout << n << '\n';
    for (int u = 1; u <= n; u++) {
        cout << G[u].size();
        for (auto [v, dis] : G[u]) {
            cout << " " << v;
            cout << " " << dis;
        }
        cout << '\n';
    }
}