2024-11-122024-11-16Contest Notes

VP 2024 ICPC 南京

Problems	AC
A. Hey, Have You Seen My Kangaroo?
B. Birthday Gift	○
C. Topology	⊕
D. Toe-Tac-Tics
E. Left Shifting 3	○
F. Subway
G. Binary Tree	○
H. Border Jump 2
I. Bingo	⊕
J. Social Media	○
K. Strips	○
L. $P \oplus Q = R$
M. Ordainer of Inexorable Judgment

E

void solve() {
    int n = read(), k = read();
    string s;
    cin >> s;

    s = " " + s + s;

    if (n <= 6) {
        puts("0");
        return;
    }

    int ans = 0;
    string t = "nanjing";

    vector<int> a(2 * n + 1);

    for (int i = 1; i <= 2 * n; i++) {
        bool f = 1;
        for (int j = i; j <= i + 6 and j <= 2 * n; j++) {
            if (s[j] != t[j - i]) {
                f = 0;
                break;
            }
        }

        if (f) {
            a[i]++;
        }
    }


    for (int i = 1; i <= 2 * n; i++) {
        a[i] += a[i - 1];
    }
    for (int i = 1; i + n - 1 - 6 <= n + min(n, k) - 6; i++) {
        ans = max(ans, a[i + n - 1 - 6] - a[i - 1]);
    }
    cout << ans << "\n";
}

J

将边分为三类：老朋友–老朋友、新朋友–老朋友，新朋友–新朋友

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

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

    int ans = 0;

    using pii = std::pair<int, int>;
    #define fi first
    #define se second
    std::map<pii, int> mp;

    vector<int> f(k + 1);
    vector<vector<int>> g(k + 1);

    for (int i = 1; i <= m; i++) {
        int u = read(), v = read();
        if (bad[u] and bad[v]) {
            ans++;
            continue;
        }
        g[u].eb(v);
        g[v].eb(u);

        if (u > v) swap(u, v);
        if (u != v) mp[{u, v}]++;
        else f[u]++;
        // mp[{v, u}]++;
    }

    
    for (int i = 1; i <= k; i++) {
        if (bad[i]) continue;
        for (int v : g[i]) {
            if (bad[v]) {
                f[i]++;
            }
        }
        // f[i] += mp[{i, i}];
    }

    int res = 0;
    for (auto [it, cnt] : mp) {
        auto [u, v] = it;
        if (!bad[u] and !bad[v])
            res = max(res, f[u] + f[v] + cnt);
        else 
            res = max(res, f[u] + f[v]);
    }

    std::sort(f.begin() + 1, f.end());
    res = max(res, f[k] + f[k - 1]);

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

G 交互、树的重心

找出树的重心 $p$，根据重心的邻居数量 $d$ 进行讨论

$d = 0$，$p$ 就是答案
$d = 1$，询问 $p$ 和他的邻居，删点递归。
$d = 2$，询问两个邻居
$d = 3$，询问两个 siz 最大的邻居

void solve() {
    int n;
    cin >> n;
    cout.flush();

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

    for (int i = 1; i <= n; i++) {
        int ls, rs;
        cin >> ls >> rs;
        cout.flush();

        if (ls) {
            g[i].pb(ls);
            g[ls].pb(i);    
        }
        if (rs) {
            g[i].pb(rs);
            g[rs].pb(i);    
        }
    }

    vector<int> siz(n + 1);
    vector<int> w(n + 1);

    int p = 1, tot = n;
    vector<int> ban(n + 1);

    std::function<void(int, int)> dfs1 = [&](int u, int fa) {
        siz[u] = 1;
        for (int v : g[u]) {
            if (ban[v] or v == fa) continue;
            dfs1(v, u);
            siz[u] += siz[v];
        }
    };
    std::function<void(int, int)> dfs2 = [&](int u, int fa) {
        w[u] = 0;
        for (int v : g[u]) {
            if (ban[v] or v == fa) continue;
            dfs2(v, u);
            w[u] = max(w[u], siz[v]);
        }
        w[u] = max(w[u], tot - siz[u]);
        if (w[u] <= tot / 2) {
            p = u;
        }
    };

    using std::endl;
    auto qry = [&](int x, int y) {
        cout << "? " << x << " " << y << endl;
        cout.flush();
        int t; cin >> t;
        cout.flush();
        return t;
    };

    while (tot > 1) {
        dfs1(p, 0);
        tot = siz[p];
        dfs2(p, 0);

        int d = 0;
        for (int v : g[p]) {
            if (!ban[v]) d++;
        }

        if (d == 0) {
            cout << "! " << p << endl;
            cout.flush();
            return;
        } else if (d == 1) {
            int x = p, y = 0;
            for (int tmp : g[p]) {
                if (!ban[tmp]) {
                    y = tmp;
                    break;
                }
            }

            int t = qry(x, y);
            if (t == 0) {
                cout << "! " << x << endl;
                cout.flush();
                return;
            } else if (t == 2) {
                ban[x] = 1;
                p = y;
            }
        } else if (d == 2) {
            int x = 0, y = 0;
            for (int v : g[p]) {
                if (!ban[v]) {
                    if (!x) x = v;
                    else y = v;
                }
            }

            int t = qry(x, y);
            if (t == 0) {
                ban[p] = ban[y] = 1;
                p = x;
            } else if (t == 1) {
                cout << "! " << p << endl;
                cout.flush();
                return;
            } else {
                ban[p] = ban[x] = 1;
                p = y;
            }
            
        } else if (d == 3) {
            int x = g[p][0], y = g[p][1], z = g[p][2];
            int sx = siz[x], sy = siz[y], sz = siz[z];

            if (sx < sy) swap(x, y), swap(sx, sy);
            if (sx < sz) swap(x, z), swap(sx, sz);
            if (sy < sz) swap(y, z), swap(sy, sz);

            int t = qry(x, y);
            if (t == 1) {
                ban[x] = ban[y] = 1;
            } else if (t == 0) {
                ban[y] = ban[z] = ban[p] = 1;
                p = x;
            } else {
                ban[p] = ban[x] = ban[z] = 1;
                p = y;
            }
        }

    }
}

C 组合数学、TreeDP、拓扑序

给定一棵由 $n$ 个点组成的外向树，满足父亲的编号小于儿子。对于每个 $1 \le i \le n$，求出这棵树的满足编号为 $i$ 的点出现在第 $i$ 个位置的拓扑序数量，对 $998244353$ 取模。

$n \le 5000$

考虑求出所有的 $dp(i, j)$，表示编号为 $i$ 的点在拓扑序中出现在第 $j$ 位的方案数。答案即为所有的 $dp(i, i)$。

为了方便转移，可以让 $dp(i, j)$ 先不考虑子树 $i$ 内部的顺序，最后求答案的时候再乘上子树 $i$ 的拓扑序个数。

设点 $u$ 的父亲为 $fa$，考虑从 $dp(fa, i)$ 转移到 $dp(u, j)$。

首先，需要安排在 $fa$ 子树中，但不在 $u$ 子树中的 $siz_{fa} - siz_{u} - 1$ 个点在拓扑序中的位置。已知条件是 $fa$ 出现在 $i$ 位置，后面的 $n - i$ 个位置里面 $u$ 的子树占了 $siz_u$ 个位置。那么可选的空位就是 $n - i - siz_u$ 个，要选 $siz_{fa} - siz_u - 1$ 个位置用来放这些点。方案数为 $\binom{n - i - siz_u}{siz_{fa} - siz_u - 1}$。

其次，需要确定在 $fa$ 子树中，但不在 $u$ 子树中的 $siz_{fa} - siz_{u} - 1$ 个点在拓扑序中的相对顺序。这是一个经典的子问题：一棵 $n$ 个点的外向树的拓扑序个数为 $\frac{n!}{\prod_{i = 1}^{n}siz_i}$。那么个数就是 $\frac{(siz_{fa} - siz_u - 1)!}{\prod_{v \in subtree(fa) \land v \notin subtree(u)}siz_v}$

因此，我们可以写出：

$$
dp(u, j) = \sum_{i = 1}^{j - 1} dp(fa, i) \cdot \binom{n - i - siz_u}{siz_{fa} - siz_u - 1} \cdot \frac{(siz_{fa} - siz_u - 1)!}{\prod_{v \in subtree(fa) \land v \notin subtree(u)}siz_v}
$$

观察到式子和 $j$ 没有关系，可以前缀和优化转移。总共 $O(n^2)$ 个状态，转移的复杂度为 $O(1)$。

因为一开始并没有考虑子树内部的顺序，所以最后求答案的时候要乘上子树的点位置的方案数和拓扑序的个数。

总时间复杂度 $O(n^2)$，可以通过此题。

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

    vector<int> p(n + 1);
    for (int i = 2; i <= n; i++) {
        cin >> p[i];
    }

    vector<int> siz(n + 1, 1);
    vector<Z> prod(n + 1, 1);

    for (int i = n; i >= 1; i--) {
        prod[i] *= siz[i];
        if (p[i]) {
            siz[p[i]] += siz[i];
            prod[p[i]] *= prod[i];
        }
    }

    vector dp(n + 1, vector<Z>(n + 1));
    dp[1][1] = 1;
    for (int u = 2; u <= n; u++) {
        int fa = p[u];

        auto ndp = dp[fa];

        Z coef = comb.fac(siz[fa] - siz[u] - 1) / (prod[fa] / prod[u] / siz[fa]);

        for (int i = 1; i <= n; i++) {
            ndp[i] *= comb.binom(n - i - siz[u], siz[fa] - siz[u] - 1);
        }
        for (int i = 1; i <= n; i++) {
            ndp[i] += ndp[i - 1];
        }
        for (int i = 1; i <= n; i++) {
            dp[u][i] = coef * ndp[i - 1];
        }
    }

    for (int i = 1; i <= n; i++) {
        Z res = dp[i][i];
        res *= comb.binom(n - i, siz[i] - 1);
        res *= comb.fac(siz[i]) / prod[i];
        cout << res << " \n"[i == n];
    }
}

I min–max 容斥、多项式

给定一个长度为 $nm$ 的整数序列，将其打乱之后按顺序填入 $n \times m$ 的网格中。定义 bingo 整数为最小的整数 $k$，满足存在至少一行或者一列，其中所有的数都 $\le k$。求出所有 $(nm)!$ 种打乱方式的 bingo 整数之和，对 $998244353$ 取模。

$nm \le 2 \times 10^5$

定义一行或一列的 bingo 整数为其中填入的数的 $\max$，则所求的 bingo 整数为所有行列的 bingo 整数的 $\min$。

对于 $\min$ 不好处理的情况，考虑使用 $\min − \max$ 容斥：

$$
\min_{x \in S}x = \sum_{T \subseteq S, T \neq \varnothing}(-1)^{\lvert T \rvert - 1} \max_{x \in T}x
$$

$S$ 即为所有行和列的集合。$\max_{x \in T}x$ 即为 $T$ 中所有行和列的 bingo 数的最大值。

假设 $T$ 有 $x$ 行 $y$ 列，$T$ 覆盖了 $c = mx + ny - xy$ 个格子。

将数列从小到大排序。当这 $c$ 个格子的最大值是 $a_i$ 时，当且仅当，$a_i$ 在这 $c$ 个格子中出现，且 $a_{i + 1}, a_{i + 2}, \cdots, a_{nm}$ 均没有出现，方案数为：

$$
\binom{i - 1}{c - 1}c!(nm - c)!
$$

对于一个 $c$，暴力求出答案是 $O((nm)^2)$ 的。容易发现将这个式子拆开是可以卷积加速的。

具体地，

\begin{aligned}
&\sum_{i=1}^{nm}\binom{i - 1}{c - 1}c!(nm - c)!a_i \\
&= \frac{(i - 1)!}{(c - 1)!(i - c)!}c!(nm - c)!a_i \\
&= \frac{a_i(i - 1)!}{(i - c)!} \cdot c(nm - c)! \\
\end{aligned}

我们令多项式 $f_i = a_i \cdot (i - 1)!$，$g_i = \frac{1}{(nm - 1 - i)!}$，令 $p$ 是 $f$ 和 $g$ 的卷积

\begin{aligned}
p_c &= \sum_{i + j = c} {f_i}{g_j} \\
&= \frac{a_i \cdot (i - 1)!}{(nm - 1 - j)!} \\
&= \frac{a_i \cdot (i - 1)!}{(nm + i - 1 - c)!} \\
\end{aligned}

再令 $p$ 左移 $nm - 1$ 位，

$$
p_c \gets p_{c + nm - 1} = \frac{a_i \cdot (i - 1)!}{(i - c)!}
$$

再令 $p_c \gets p_c \cdot c(nm - c)!$，即可求出 $c$ 对应的答案 $p_c$。

这样，当我们对每个 $c$ 求出答案以后，枚举 $T$ 中选择了 $x$ 行 $y$ 列，则选择 $T$ 的方案数为 $\binom{n}{x}\binom{m}{y}$，乘上容斥系数求和即可。

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

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

    vector<int> a(n * m + 1);
    for (int i = 1; i <= n * m; i++) {
        a[i] = read();
    }

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

    Poly<P> f, g;
    f.resize(n * m + 1);
    g.resize(n * m);
    for (int i = 1; i <= n * m; i++) {
        f[i] = a[i] * comb.fac(i - 1);
    }
    for (int i = 0; i < n * m; i++) {
        g[i] = comb.invfac(n * m - 1 - i);
    }

    f *= g;
    f = f.shift(- (n * m - 1));
    for(int i = 1; i <= n * m; i++) {
        f[i] *= i * comb.fac(n * m - i);
    }

    Z ans = 0;
    for (int x = 0; x <= n; x++) {
        for (int y = 0; y <= m; y++) {
            if (x + y == 0) {
                continue;
            }

            Z coef = (x + y - 1) % 2 == 0 ? 1 : -1;

            Z res = coef * comb.binom(n, x) * comb.binom(m, y);
            res *= f[m * x + n * y - x * y];

            /*
            Z t = 0;
            for (int i = 1; i <= n * m; i++) {
                t += comb.binom(i - 1, c - 1)
                    * comb.fac(c)
                    * comb.fac(n * m - c)
                    * a[i];
            }
            res *= t;
            */

            ans += res;
        }
    }

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

VP 2024 ICPC 南京

https://tosakaucw.github.io/vp-2024-icpc-南京/

Author

TosakaUCW

Posted on

2024-11-12

Updated on

2024-11-16

Licensed under

#XCPC

VP 2024 ICPC 南京

E

J

G 交互、树的重心

C 组合数学、TreeDP、拓扑序

I min–max 容斥、多项式

Author

Posted on

Updated on

Licensed under

Comments

Catalogue