VP 2024 女生赛

2024 China Collegiate Programming Contest (CCPC) Female Onsite (2024年中国大学生程序设计竞赛女生专场)

Problems	AC	Note
A. Box	○	签到
B. Aho-Corasick Automaton
C. CCPC	○	签到
D. Excellent Splitting
E. Centroid Tree	○	并查集
F. Perfect Square	⊕	数学、背包
G. Increasing Sequence	○	拆数位
H. Square Root	○	签到
I. String Duplication	⊕	SAM
J. Sum of Squares of GCDs
K. Xiao Kai’s Dream of Provincial Scholarship		模拟
L. Puzzle	○	思维
M. Covering a Tree	○	贪心

A. Box

Code >folded

void solve() {
    int z0 = read();
    int h = read();
    int u0 = read();
    int v0 = read();
    int u1 = read();
    int v1 = read();

    // u0 v0 z0
    // u1 v1 z0
    // u0 v1 z0
    // u1 v0 z0
    if (u0 > u1) {
        swap(u0, u1);
    }
    if (v0 > v1) {
        swap(v0, v1);
    }

    for (int q = read(); q--; ) {
        int x = read();
        int y = read();
        int z = read();

        if (x < u0 or x > u1 or y < v0 or y > v1 or z > z0 + h or z < z0) {
            puts("NO");
        } else {
            puts("YES");
        }
    }    
}

C. CCPC

Code >folded

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

    int a = 0, b = 0;
    for (auto ch : s) {
        if (ch == 'C') a++;
        if (ch == 'P') b++;
    }
    if (a < 3 or b < 1) {
        puts("0");
        return;
    }
    cout << min((a - 1) / 2, b) << '\n';
}

E. Centroid Tree

Code >folded

void solve() {
    int n = read();
    DSU dsu(n + 1);

    vector<int> c(n + 1);
    vector<vector<int>> e(n + 1);
    for (int i = 1; i <= n; i++) {
        c[i] = read();
        for (int j = 1; j <= c[i]; j++) {
            int x = read();
            e[i].eb(x);
        }
    }   

    vector<int> par(n + 1);
    for (int i = n; i >= 1; i--) {
        for (auto x : e[i]) {
            int now = dsu.find(x);
            par[now] = i;
            dsu.merge(i, now);
        }
    }

    for (int i = 2; i <= n; i++) {
        cout << par[i] << " " << i << '\n';
    }
}

F. Perfect Square

给出一个长度为 $n$ 的正整数序列 $a$，求所有序列 $d$ 满足 $d_i|a_i$ 且 $d_i$ 的乘积为完全平方数的乘积开方之和。

$1 \le n \le 10^6, 1 \le a_i \le 10^6$

每个质因子的贡献是独立的。

相当于 $n$ 个物品，每个物品可以拿最多 $c_i$ 个，问总共取偶数个的方案里，$p ^ \frac{取的数量}{2}$ 的和。

Code

void solve() {
    int n = read();
    vector<vector<int>> g(1e6);
    for (int i = 1; i <= n; i++) {
        for (int x = read(); x != 1; ) {
            int p = minp[x];
            int c = 0;

            while (x % p == 0) {
                x /= p;
                c++;
            }

            g[p].eb(c);
        }
    }

    auto go = [&](vector<int> c, int p) -> Z {
        int m = c.size();
        if (m == 0) return Z(1);

        int sum = std::accumulate(c.begin(), c.end(), 0);
        vector<int> pow(sum + 1);
        pow[0] = 1;
        for (int i = 1; i <= sum; i++) {
            pow[i] = pow[i - 1] * p;
        }

        vector<Z> dp(2);
        dp[0] = 1;

        for (int i = 0; i < m; i++) {
            vector<Z> ndp(2);
            for (int j = 0; j <= 1; j++) {
                for (int k = 0; k <= c[i]; k++) {
                    int nj = (j + k) % 2;
                    ndp[nj] += dp[j] * pow[(j + k) / 2];
                }
            }
            dp = std::move(ndp);
        }

        return dp[0];
    };

    Z ans = 1;
    for (auto p : primes) {
        ans *= go(g[p], p);
    }
    cout << ans << '\n';
}

G. Increasing Sequence

给定长度为 $n$ 的数列 $a$ 和整数 $k$，询问有多少整数满足 $x \in [0, k]$，且有 $a_1 \oplus x, a_2 \oplus x, \cdots , a_n \oplus x$ 是单调不降序列。

$1 \le n \le 2 \cdot 10^5, 1 \le k \le 10^{18}$

对于相邻两项 $a_i \oplus x \le a_{i + 1} \oplus x$，从高到低找到 $a_i$ 和 $a_{i + 1}$ 第一个不同的位。在这一位上，如果 $a_{i}$ 为 $0$，$a_{i + 1}$ 为 $1$，则 $x$ 必须为 $0$；反之 $x$ 必须为 $1$。

那么现在有一些限制，问你有多少个 $x \in [0, k]$，就是数位 DP 的板子。

Code

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

    vector<int> a(n + 1);
    vector<int> b(65, -1);
    // vector<int> c(65, -1);
    for (int i = 1; i <= n; i++) {
        a[i] = read();
        
    }

    for (int i = 1; i < n; i++) {
        for (int j = 60; j >= 0; j--) {
            int x = a[i] >> j & 1;
            int y = a[i + 1] >> j & 1;

            if (x != y) {
                int now = x;
                if (b[j] != -1 and b[j] != x) {
                    puts("0");
                    return;
                }
                b[j] = x;
                break;
            }
        }
    }

    // for (int i = 0; i < 60; i++) {
    //     b[i] = b[i] == -1 ? 2 : 1;
    //     cerr << b[i] << " ";
    // }

    // int ans = 1;

    // for (int i = 60; i >= 0; i--) {
    //     int x = k >> i & 1;
    //     if (x) {
    //         cout << "i: " << i << '\n';
    //         int res = 1;
    //         // i - b[i]
    //         if (i - 1 >= 0)
    //             res *= 1LL << (i - b[i - 1]);
    //         // cout << "res: " << res << '\n';
    //         ans += res;
    //     }
    // }

    vector dp(65, vector<int>(2, -1));

    auto dfs = [&](auto&& self, int now, bool f) -> int {
        if (now == -1) return 1;
        if (~dp[now][f]) return dp[now][f];

        int res = 0;
        int lim = f ? (k >> now & 1) : 1;
        for (int j = 0; j <= lim; j++) {
            if (b[now] == -1 or b[now] == j) {
                res += self(self, now - 1, f && (j == lim));
            }
        }

        dp[now][f] = res;
        return res;
    };

    int ans = dfs(dfs, 60, 1);
    
    cout << ans << '\n';
}

H. Square Root

Code >folded

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

    int n = s.size();
    for (int i = 0; i + 1 < n; i++) {
        if (i - 1 < 0 or i + 1 >= n) continue;
        if (s[i - 1] == '1' and s[i] == '1' and s[i + 1] == '1') 
            s[i] = '0';
    }
    double ans = 0;
    s += '0';
    int cnt = 0;
    for (int i = 0; i <= n; i++) {
        if (s[i] == '0') {
            ans += pow(cnt, 0.5);
            // cout << cnt << '\n';
            cnt = 0;
        } else {
            cnt++;
        }
    }
    printf("%.10f", ans);
}   

I. String Duplication

给定一个字符串 $S$，求 $S$ 复制 $m$ 次拼接起来的的字符串的本质不同子串个数。

$1 \le |S| \le 3 \times 10^5, 1 \le m \le 10^9$

打表可以直接发现规律，以下是参考官方题解的证明：

令函数 $f(S, m)$ 表示 $S$ 复制 $m$ 次的本质不同子串个数。

当 $m \ge 3$ 时，如果一个串是 $SSS$ 的子串，而且不是 $SS$ 的子串，那么可以被写成 $x[S]y$ 的形式（$x$ 为 $S$ 的非空后缀，$y$ 为 $S$ 的非空前缀$。

同理一个串是 $SSSS$ 的子串，而且不是 $SSS$ 的子串，那么可以被写成 $x[SS]y$ 的形式

显然 $x[S]y$ 的数量等于 $x[SS]y$ 的数量。并且这个数量等于 $f(S, 3) - f(S, 2)$。

等差数列求和就做完了。求本质不同子串直接 sam 即可。

Code

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

    SAM sam;

    string s;
    cin >> s;

    vector<Z> ans(3);
    int p = 1;
    for (int k = 0; k < 3; k++) {
        for (auto c : s) {
            p = sam.extend(p, c - 'a');
        }
        for (int i = 2; i < sam.size(); i++) {
            ans[k] += sam.len(i) - sam.len(sam.link(i));
        }
    }

    if (m <= 2) {
        cout << ans[m - 1] << '\n';
    } else {
        cout << (ans[2] - ans[1]) * (m - 2) + ans[1] << '\n';
    }
}

J. Sum of Squares of GCDs

Code >folded

M. Covering a Tree

Code >folded

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

    vector<int> par(n + 1);
    vector<vector<int>> g(n + 1);
    for (int i = 2; i <= n; i++) {
        int p = read();
        par[i] = p;
        g[p].eb(i);
    }

    vector<int> dep(n + 1);

    vector<pii> leaf;

    auto dfs = [&](auto&& self, int u) -> void {
        for (int v : g[u]) {
            dep[v] = dep[u] + 1;
            self(self, v);
        }
        if (g[u].empty()) {
            leaf.eb(dep[u], u);
        }
    };
    dfs(dfs, 1);

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

    // for (auto [d, u] : leaf) {
    //     cerr << d << " " << u << "\n";
    // }

    int ans = 0;
    vector<int> vis(n + 1);
    for (auto [_, u] : leaf) {
        int res = 0;
        for (int v = u; par[v] != 0; v = par[v]) {
            // v -> par[v]
            res++;
            // cout << "vis" << v << " " << par[v] << "\n";
            if (vis[v]) break;
            vis[v] = 1;
            ans = max(ans, res);
        }
    }

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