2024-11-072024-12-10Contest Notes

VP 2024 CCPC 哈尔滨

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

Problems	AC	Note
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		DP、质因子分解
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';
    }
}

E 可撤销背包、多项式

$m$ 个球，速度为 $v_i$ , $n$ 个位置 $x_1, \cdots , x_n$ ，每个球都会随机选择一个位置，然后向正方向移动，求坐标中位数在原点的期望时间，对 $10^9 + 7$ 取模

$n, m \le 500$

设 $m = O(n)$，可能的时间答案一定是某个 $t = \frac{x_i}{v_j}$，那么一共有 $n \cdot m$ 个 $t$，对于每个 $t$，求恰好有 $\lfloor \frac{m}{2} \rfloor$ 个球还没经过原点的概率

对于每个球，可以枚举所有位置，计算出在 $t$ 时没经过原点的概率 $p_i$，经过原点的概率 $1-p_i$。求恰好有 $\lfloor \frac{m}{2} \rfloor$ 个球还没经过原点的概率，这东西是可以背包的。这样的复杂度是 $O(n^4)$。

实际上状态数量并没有那么多，看起来有 $O(n^3)$ 个 $p_i$ ($n^2$ 个 $t$ 和 $n$ 个球)，实际上对于每个球，假如我们将 $O(n^2)$ 个 $t$ 从小到大排序，并从小到大枚举这个 $t = \frac{x_i}{v_j}$，对于这个 $t$，只有对应的 $p_j$ 会发生改变，而其他的球都不会发生改变，也就是说实际上就 $O(n^2)$ 个状态。并且我们可以维护所有球的 $dp$ 数组，当某个球发生改变时，撤销那个球，然后把概率变化后的新球加上去。

更进一步地，根据可撤销背包的知识，我们知道单次的可撤销背包对应除一个单项式。我们可以将每个球看作 $p_i\cdot x + (1 - p_i)$，求的是生成函数的 $x^{m / 2}$ 项的系数。

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

    vector<int> x(n);
    for (int i = 0; i < n; i++) {
        x[i] = -read();
    }
    vector<int> v(m);
    for (int i = 0; i < m; i++) {
        v[i] = read();
    }

    vector<pii> t;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            t.eb(i, j);
        }
    }
    std::sort(t.begin(), t.end(), [&](pii a, pii b) {
        return x[a.fi] * v[b.se] < x[b.fi] * v[a.se];
    });

    Z ans = 0;
    Z invN = Z(n).inv();
    vector<Z> d(m + 1);
    vector<Z> f(m + 1);
    f[0] = power(Z(n), m);

    auto ins = [&](Z x) {
        Z y = n - x;
        for (int i = m; i >= 1; i--) {
            f[i] = f[i] * y + f[i - 1] * x;
        }
        f[0] *= y;
    };
    auto del = [&](Z x) {
        Z y = Z(n - x).inv();
        f[0] *= y;
        for (int i = 1; i <= m; i++) {
            f[i] = (f[i] - f[i - 1] * x) * y;
        }
    };

    for (auto [i, j] : t) {
        del(d[j]);
        ans += f[m / 2] * invN * x[i] / v[j];
        d[j] += 1;
        ins(d[j]);
    }

    ans *= power(invN, m - 1);

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

VP 2024 CCPC 哈尔滨

https://tosakaucw.github.io/vp-2024-ccpc-哈尔滨/

Author

TosakaUCW

Posted on

2024-11-07

Updated on

2024-12-10

Licensed under

#XCPC VP 哈尔滨

VP 2024 CCPC 哈尔滨

M

G

K 二分

L TreeDP、期望

A 构造

E 可撤销背包、多项式

Author

Posted on

Updated on

Licensed under

Comments

Catalogue