2024-11-122024-12-10Contest Notes

VP 2024 ICPC 南京

The 2024 ICPC Asia Nanjing Regional Contest (The 3rd Universal Cup. Stage 16: Nanjing)
比赛链接

Problems	AC	Note
A. Hey, Have You Seen My Kangaroo?		Medium-Hard
B. Birthday Gift	○
C. Topology	⊕	拓扑序、组合数学
D. Toe-Tac-Tics		Hard
E. Left Shifting 3	○
F. Subway	⊕
G. Binary Tree	○
H. Border Jump 2		Hard
I. Bingo	⊕	min-max容斥
J. Social Media	○
K. Strips	○
L. $P \oplus Q = R$		Impossible
M. Ordainer of Inexorable Judgment		Medium-Hard、计算几何

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";
}

F 最短路、李超树

有 $n$ 个地铁站和 $k$ 条地铁线路，可以乘坐地铁或者在某站处换乘。乘坐第 $i$ 条线路的第 $j$ 段需要 $w_{i,j}$ 单位时间。从某站的 $x$ 号线路换乘到 $y$ 号线路需要 $a_x \cdot by$ 单位时间。

求出从站点 $1$ 到每个站点的最短路。

$n$, $k$, $\sum(p_i − 1) \le 2 \times 10^5$

复读题解

考虑用状态 $(i, j)$ 表示当前在第 $i$ 个站，并在第 $j$ 条线路上。在状态间求最短路来得到答案。

乘坐地铁的转移是简单的，只需要从 $(i, j)$ 转移到第 $j$ 条线路的下一站 $x$ 对应的状态 $(x, j)$ 即可。

考虑如何处理换乘的转移。将一个站点的线路按照 $b$ 从小到大排序，可以发现转移到 $b$ 较小的线路一定代价比 $b$ 较大的线路小，也就是说，$b$ 较小的状态一定先于较大的状态被加入优先队列。于是可以考虑进行懒惰转移，在每个结点较小的 $b$ 被转移出去之后再考虑下一条线路。

对于一个结点上换乘的转移，相当于是给定若干直线，查询某个 $x$ 处的最小值。使用李超树或者动态凸包可以维护。

时间复杂度 $O((n + k + \sum p_i) \log(n + k + \sum p_i))$。

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

    vector<int> a(k), b(k);
    for (int i = 0; i < k; i++) {
        b[i] = read();
    }
    for (int i = 0; i < k; i++) {
        a[i] = read();
    }

    vector<vector<int>> x(k);
    vector<vector<int>> w(k);

    for (int i = 0; i < k; i++) {
        int p = read();

        x[i].resize(p);
        w[i].resize(p - 1);
        for (int j = 0; j < p; j++) {
            x[i][j] = read() - 1;
            if (j < p - 1) w[i][j] = read();
        }
    }

    vector<pii> t;
    vector<vector<pii>> g(n);
    for (int i = 0; i < k; i++) {
        for (int j = 0; j < x[i].size(); j++) {
            t.eb(i, j);
            g[x[i][j]].eb(b[i], t.size() - 1);
        }
    }

    vector<lichao> tt;
    for (int i = 0; i < n; i++) {
        std::sort(g[i].begin(), g[i].end());
        vector<int> x;
        for (auto [b, _] : g[i]) {
            x.eb(b);
        }
        tt.eb(x);
    }

    int nn = t.size();
    vector<int> dis(nn + n, inf);

    std::set<pii> pq;
    for (auto [_, i] : g[0]) {
        dis[i] = 0;
        pq.ep(0, i);
    }

    vector<int> cur(n, 0);

    while (!pq.empty()) {
        auto p = pq.begin();
        auto [d, v] = *p;
        pq.erase(p);

        if (v < nn) {
            auto [i, j] = t[v];

            if (j + 1 < x[i].size()) {
                int nd = d + w[i][j];
                int u = v + 1;
                if (nd < dis[u]) {
                    pq.erase({dis[u], u});
                    dis[u] = nd;
                    pq.ep(dis[u], u);
                }
            }

            int f = x[i][j];
            if (cur[f] < g[f].size()) {
                int u = f + nn;
                pq.erase({dis[u], u});
                tt[f].add(a[i], d);
                dis[u] = tt[f].calc(cur[f]);
                pq.ep(dis[u], u);
            }

        } else {
            v -= nn;

            int u = g[v][cur[v]].se;

            int nd = tt[v].calc(cur[v]);
            if (nd < dis[u]) {
                pq.erase({dis[u], u});
                dis[u] = nd;
                pq.ep(dis[u], u);
            }

            cur[v]++;

            if (cur[v] < g[v].size()) {
                dis[nn + v] = tt[v].calc(cur[v]);
                pq.ep(dis[nn + v], nn + v);
            }
        }
    }

    for (int i = 1; i < n; i++) {
        int res = inf;
        for (auto [_, j] : g[i]) {
            res = min(res, dis[j]);
        }
        cout << res << " ";
    }
    cout << "\n";
}

VP 2024 ICPC 南京

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

Author

TosakaUCW

Posted on

2024-11-12

Updated on

2024-12-10

Licensed under

#XCPC VP 南京

VP 2024 ICPC 南京

E

J

G 交互、树的重心

C 组合数学、TreeDP、拓扑序

I min–max 容斥、多项式

F 最短路、李超树

Author

Posted on

Updated on

Licensed under

Comments

Catalogue