2025 CCPC 网络赛

第十一届中国大学生程序设计竞赛网络预选赛（CCPC Online 2025）
Date 2025/09/20
Solved(Upsolved) 9/13

A	B	C	D	E	F	G	H	I	J	K	L	M
O	Ø	Ø	Ø	O	Ø	O	Ø			O

B - 魔塔

对怪物 $i$，它会被攻击 $\lceil h_i/(X-d_i)\rceil$ 次，因此会反击
$$
v_i = \left\lfloor \frac{h_i-1}{X-d_i}\right\rfloor
$$
次。

设 $Y$ 为遇到怪物时的防御力，怪物对勇士生命的净变化为

$$
\Delta_i = v_i\cdot (Y - a_i)
$$

目标是从根出发遍历所有点，最大化

$$
\sum_{i=2}^{n} \Delta_i
$$

$$
\sum_{i=2}^{n} \Delta_i
= \sum_{\text{怪}} v_i Y - \sum_{\text{怪}} v_i a_i
$$

后一项和顺序无关，因此就是最大化 $\sum_{\text{怪}} v_i Y$

问题转化为：有两种物品 怪物和蓝宝石，遇到蓝宝石让 $Y \leftarrow Y + 1$，遇到怪物产生 $v_i Y$ 的贡献，安排顺序最大化贡献。

贪心让蓝宝石在前面，怪物在后面，且 $v_i$ 越大越后面

具体来说，放在 dfs 上面，$u$ 可以安排子树的合并顺序。

首先可以启发式合并，然后维护一个单调队列来维护合并

在维护 $u$ 的合并的时候，如果 $v_i < v_u$ 的话，都是可以确定在 $u$ 之前合并的，其他的可以放着等后面的来确定

因为用了 multiset::merge 复杂度只有一只 log

时间复杂度 $O(n \log n)$

struct Frac {
    int num;
    int den;
};
bool operator<(const Frac &a, const Frac &b) {
    return a.num * b.den < b.num * a.den;
}
Frac &operator+=(Frac &a, const Frac &b) {
    a.num += b.num;
    a.den += b.den;
    return a;
}

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

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

    int ans = 0;
    vector<int> v(n + 1);
    vector<multiset<Frac>> s(n + 1);

    int sum = 0;
    for (int i = 2; i <= n; i++) {
        int t = read();
        if (t == 1) {
            v[i] = -1;
        } else {
            int a = read(), d = read(), h = read();
            v[i] = (h - 1) / (X - d);
            ans -= v[i] * a;
        }
    }

    int tot = 0;

    auto dfs = [&](this auto&& dfs, int u, int fa) -> void {
        for (auto v : g[u]) {
            if (v == fa) continue;

            dfs(v, u);
            if (s[u].size() < s[v].size()) {
                swap(s[u], s[v]);
            }

            s[u].merge(s[v]);
            s[v].clear();
        }

        if (v[u] == -1) {
            s[u].ep(0, 1);
        } else if (s[u].empty()) {
            tot += v[u];
        } else {
            Frac f {v[u], 0};
            do {
                auto g = s[u].extract(s[u].begin()).value();

                ans += f.den * g.num;
                f += g;
            } while (!s[u].empty() and *s[u].begin() < f);
            s[u].ep(f);
        }
    };
    dfs(1, 0);

    int now = 0;
    for (auto [num, den] : s[1]) {
        ans += now * num;
        now += den;
    }
    ans += tot * now;

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

H - 教师

类似 SOSdp 的思想，直接钦定某个老师给某个课程，状态就是每个课程有没有被钦定

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

    vector v(n, vector(k + 1, 0ll));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j <= k; j++) {
            v[i][j] = read();
        }
    }

    vector t(m, 0ll);
    vector val(m, vector(n, 0ll));

    for (int i = 0; i < m; i++) {
        int k = read();
        t[i] = read();

        for (int j = 0; j < k; j++) {
            int x = read() - 1, y = read();
            val[i][x] = y;
        }
    }

    int maxS = 1 << n;
    vector dp(T + 1, vector(maxS, -inf));
    dp[0][0] = 0;


    vector ans(T + 1, 0ll);
    for (int i = 0; i < m; i++) {
        for (int p = 0; p + t[i] <= T; p++) {

            auto ndp = dp[p];
            int np = p + t[i];

            for (int s = 0; s < maxS; s++) {
                for (int j = 0; j < n; j++) {
                    if ((s >> j) & 1) continue;

                    int ns = s | (1 << j);
                    ndp[ns] = max(ndp[ns], ndp[s] + v[j][val[i][j]]);
                }
            }

            for (int s = 0; s < maxS; s++) {
                dp[np][s] = max(dp[np][s], ndp[s]);
            }
            ans[np] = max(ans[np], dp[np][maxS - 1]);
        }
    }
    
    for (int i = 0; i < n; i++) ans[0] += v[i][0];
    for (int i = 1; i <= T; i++) ans[i] = max(ans[i], ans[i - 1]);
    for (int i = 1; i <= T; i++) cout << ans[i] << '\n';
}

F - 连线博弈

若干条线段会分成若干个子局面，子局面的 sg xor 起来就是答案

对 sg 打表，会发现有神秘循环节

mt19937_64 rnd(chrono::steady_clock::now().time_since_epoch().count());

int _sg[5000];
int sg(int x) { 
    int t = (x - 100) / 34;
    t = max(t, 0ll);
    return _sg[x - (t * 34)];
}

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

    map<int, u64> diff;
    while (m--) {
        int l = read(), r = read();

        auto x = rnd();
        diff[l] ^= x;
        diff[r] ^= x;
    }

    map<int, u64> a;
    diff[n] = 0;
    u64 sum = 0;
    for (int las = -1; auto [i, val] : diff) {
        a[sum] += i - las - 1;
        sum ^= val;
        las = i;
    }

    int ans = 0;
    for (auto [_, x] : a) {
        ans ^= sg(x);
    }
    if (ans) {
        cout << "YES\n";
    } else {
        cout << "NO\n";
    }
}

signed main() {
    for (int i = 1; i <= 200; i++) {
        _sg[i] = -1;
    }
    _sg[0] = 0;
    _sg[1] = 0;
    _sg[2] = 1;
    _sg[3] = 1;
    for (int n = 2; n <= 200; n++) {
        set<int> st;
        for (int i = 0; i <= n - 2; i++) {
            int j = n - 2 - i;
            st.insert(_sg[i] ^ _sg[j]);
        }

        int mex = 0;
        for (auto s : st) {
            if (s != mex) break;
            mex++;
        }
        _sg[n] = mex;
    }

    // for (int i = 0; i < 200; i++) {
    //     cout << _sg[i] << " ";
    // }

    for (int T = read(); T--; solve());
    return 0;
}

D - 通配符匹配

设 $s$ 被 * 分成了 $k$ 个串

每个 $s_1$ 匹配上以后，第 $2$ 到 $k - 1$ 个贪心匹配最前面的位置

那么后面的所有 $s_k$ 匹配数量就是当前 $s_1$ 匹配的答案

vector<int> getFail(string s) {
    int n = s.size();
    vector<int> f(n + 1);
    for (int i = 1, j = 0; i < n; i++) {
        while (j and s[i] != s[j]) {
            j = f[j];
        }
        j += (s[i] == s[j]);
        f[i + 1] = j;
    }
    return f;
}
vector<pii> kmp(string s, string t) {
    int n = s.size();
    int m = t.size();
    auto fail = getFail(s);
    vector<pii> pos;
    if (s == "") pos.eb(0, 0);
    for (int i = 0, j = 0; i < m; i++) {
        while (j and t[i] != s[j]) j = fail[j];
        if (t[i] == s[j]) j++;
        if (j == n) {
            pos.eb(i - j + 1, i + 1);
            j = fail[j];
        }
    }
    return pos;
}

void solve() {
    string s, t;
    cin >> s >> t;

    int n = s.size();
    int m = t.size();

    if (s == string(n, '*')) {
        cout << (m + 1) * m / 2;
        return;
    }

    vector<string> ss;
    if (s[0] == '*') ss.eb("");
    for (int l = 0, r = 0; r <= n; r++) {
        if (r == n or s[r] == '*') {
            string tmp = s.substr(l, r - l);
            if (tmp != "") ss.eb(tmp);
            l = r + 1;
        }
    }
    if (s.back() == '*') ss.eb("");

    // debug(ss);

    int k = ss.size();
    vector<vector<pii>> pos(k);
    vector next(k, vector(m + 1, pii{inf, inf}));

    for (int i = 0; i < k; i++) {
        auto s = ss[i];

        pos[i] = kmp(s, t);

        auto &nex = next[i];
        for (auto [l, r] : pos[i]) {
            nex[l] = {l, r};
        }
        for (int j = m - 1; j >= 0; j--) {
            nex[j] = min(nex[j], nex[j + 1]);
        }
    }

    vector<int> cnt(m + 1);
    for (auto [l, r] : pos.back()) {
        cnt[l]++;
    }
    if (k > 1) {
        for (int i = m - 1; i >= 0; i--) {
            cnt[i] += cnt[i + 1];    
        }    
    }
    
    // debug(ss[0]);
    // debug(pos[0]);

    int ans = 0;
    for (auto [l, r] : pos[0]) {
        for (int i = 1; i < k; i++) {
            if (l > m) break;
            tie(l, r) = next[i][r];
        }
        // debug(l);
        if (l > m) continue;

        ans += cnt[l];
    }

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

C - 造桥与砍树

TosakaUCW: 09-21 13:44:50
唉，理解prim了。感觉我原来是，只会kruskal

TosakaUCW: 09-21 13:44:55
普及组算法没学好

TosakaUCW: 09-21 13:45:02
[呲牙][流泪]

xxx: 09-21 13:53:38
不会prim

xxx: 09-21 13:53:50
有没有这题prim省流

TosakaUCW: 09-21 13:54:57
边做边维护最优的边

TosakaUCW: 09-21 13:55:22
每个x最优的边，就是最靠近，k-x的。

TosakaUCW: 09-21 13:55:34
只需要动态维护这个就行了

TosakaUCW: 09-21 13:56:10
[图片]

struct node {
    int dis, v, u;
    bool friend operator < (node a, node b) {
        return a.dis > b.dis;
    };
};

void solve() {
    int n = read(), k = read();
    vector<int> a(n);
    multiset<int> s;
    for (auto &x : a) {
        x = read() % k;
        s.ep(x);
    }

    priority_queue<node> q;

    auto x = *s.begin();
    s.erase(s.begin());

    auto get = [&](int x) -> int {
        auto it = s.lower_bound(k - x);
        return *(it == s.end() ? s.begin() : it);
    };

    auto y = get(x);
    q.ep((x + y) % k, y, x);

    int ans = 0;
    while (!s.empty()) {
        int y;
        auto [w, x, p] = q.top(); q.pop();

        if (!s.contains(x)) continue;

        s.extract(x);
        ans += w;

        y = get(p);
        q.ep((p + y) % k, y, p);

        y = get(x);
        q.ep((x + y) % k, y, x);
    }

    cout << ans << "\n";
}

A - 整点正方形计数2

需要解决的是一个子问题：给定 $a, b, c$，统计有多少个正整数 $x, y$ 满足 $1 \le x \le a, 1 \le y \le b, 1 \le x + y \le c$。

时间复杂度 $O(nm)$

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

    auto calc = [&](int a, int b, int c) -> int {
        if (a < 1 or b < 1) return 0;
        if (c - 1 <= 0) return 0;

        a = min(c, a);
        if (b >= c - 1) {
            return (c - 1 + c - a) * a / 2;
        } else {
            int k = min(c - b, a);
            int res = b * k;
            res += (a - k) * (c - k - 1 + c - a) / 2;
            return res;
        }
    };
    
    for (int i = 0; i <= n; i++) {
        for (int j = 0; j <= m; j++) {
            int res = 0;

            res += max(0LL, min(i, j));
            res += max(0LL, min(i, m - j));
            res += max(0LL, min(n - i, j));
            res += max(0LL, min(n - i, m - j));

            res += calc(j, m - j, n - i);
            res += calc(j, m - j, i);
            res += calc(i, n - i, j);
            res += calc(i, n - i, m - j);

            cout << res << " \n"[j == m];
        }
    }
}

G - 序列与整数对

void solve() {
    int n = read();
    int m = read();
    
    vector<int> a(n), v;
    vector<pii> q(m);
    for (auto &x : a) {
        x = read();
        v.eb(x);
    }
    for (auto &[x, y] : q) {
        x = read(), y = read();
        v.eb(x), v.eb(y);
    }

    ranges::sort(v);
    v.erase(unique(v.begin(), v.end()), v.end());
    for (auto &x : a) {
        x = ranges::lower_bound(v, x) - v.begin();
    }
    for (auto &[x, y] : q) {
        x = ranges::lower_bound(v, x) - v.begin();
        y = ranges::lower_bound(v, y) - v.begin();
    }

    auto vv = q;
    sort(vv.begin(), vv.end());
    vv.erase(unique(vv.begin(), vv.end()), vv.end());
    map<pii, int> ans;

    int N = v.size();
    vector<vector<int>> buk(N);
    for (int i = 0; i < n; i++) {
        buk[a[i]].eb(i);
    }

    for (auto [x, y] : vv) {
        auto& v1 = buk[x];
        auto& v2 = buk[y];

        if (v1.empty() or v2.empty()) {
            ans[{x, y}] = 0;
            continue;
        }

        int n1 = v1.size();
        int n2 = v2.size();
        int res = 0;

        if (n1 <= n2) {
            for (auto i : v1) {
                int j = ranges::upper_bound(v2, i) - v2.begin();
                res += n2 - j;
            }
        } else {
            for (auto j : v2) {
                int i = ranges::lower_bound(v1, j) - v1.begin();
                res += i;
            }
        }
        
        ans[{x, y}] = res;
    }

    for (auto t : q) cout << ans[t] << '\n';
}

K - 置换环

void solve() {
    int n = read();
    
    vector<int> a(n);

    auto best_a = a;
    auto best_res = 0;
    

    for (int i = 0; i < n; i++) a[i] = i + 1;
    do {

        // for (int i = 0; i < n; i++) cout << a[i] << " \n"[i == n - 1];
        auto calc = [&](vector<int> a) -> int {
            int ans = 0;
            for (int k = 0; k < n; k++) {
                vector<vector<int>> g(n + 1);
                for (int i = 0; i < n; i++) {
                    int u = a[i];
                    int v = (i + k) % n;
                    g[u].emplace_back(v);
                    g[v].emplace_back(u);
                }
                int res = 0;
                vector<int> vis(n + 1);
                auto dfs = [&](auto self, int u) -> void {
                    vis[u] = 1;
                    for (int v : g[u]) if (!vis[v]) self(self, v);
                };
                for (int i = 0; i < n; i++) {
                    if (!vis[i]) res++, dfs(dfs, i);
                }
                ans += res;
            }
            return ans;
        };

        int res = calc(a);
        // cout << res << '\n';

        if (best_res < res) {
            best_res = res;
            best_a = a;
        }
    } while (next_permutation(a.begin(), a.end()));

    cout << best_res << '\n';
    for (int i = 0; i < n; i++) cout << best_a[i] << " \n"[i == n - 1];
}

void solve() {
    int n = read();
    
    int ans = (1 + n) * n / 2;

    vector<int> a(n + 1);
    a[1] = 1;
    int t = 2;
    for (int i = n; i >= 2; i--) {
        a[i] = t;
        t++;
    }

    cout << ans << '\n';
    for (int i = 1; i <= n; i++) {
        cout << a[i] << " ";
    }
}

E - 看比赛回放

void solve() {
    int n, m;
    cin >> n >> m;

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