2024-12-132024-12-15Contest Notes

VP 2023 ICPC 澳门

The 2023 ICPC Asia Macau Regional Contest (The 2nd Universal Cup. Stage 15: Macau)

Problems	AC	Note
A. (-1,1)-Sumplete	⊕	构造
B. Basic Equation Solving		不可做
C. Bladestorm		不可做
D. Graph of Maximum Degree 3	⊕	观察性质
E. Inverse Topological Sort	⊕	构造、拓扑排序
F. Land Trade		不可做
G. Parity Game		不可做
H. Random Tree Parking	⊕	树形背包、排列组合、随机生成数据
I. Refresher into Midas	○
J. Teleportation	○	分层图、构造
K. Understand		不可做

A. (-1,1)-Sumplete

$-1$ 都选上，其他的都不选。

这样的话问题就变成了 $n ^ 2$ 个格子，每个格子初始都是 $0$，可以选择变成 $1$。

贪心就做完了。

测了下 $O(n^2)$ 的桶排没 $O(n^2 \log n)$ 的堆排跑得快。

Code

void solve() {
    int n; cin >> n;
    vector a(n, vector<int>(n));
    vector b(n, vector<int>(n));
    for (int i = 0; i < n; i++) {
        string s;
        cin >> s;
        for (int j = 0; j < n; j++) {
            if (s[j] == '-') {
                b[i][j] = 1;
                a[i][j] = -1;
            } else {
                b[i][j] = 0;
                a[i][j] = 1;
            }
        }
    }

    vector<int> row(n);
    for (int &x : row) cin >> x;
    vector<int> col(n);
    for (int &x : col) cin >> x;

    for (int i = 0; i < n; i++) {
        // cerr << a[i] << '\n';
        for (int j = 0; j < n; j++) {
            row[i] += (a[i][j] == -1);
        }
    }
    for (int j = 0; j < n; j++) {
        for (int i = 0; i < n; i++) {
            col[j] += (a[i][j] == -1);
        }
    }

    // cerr << "---------\n";
    // cerr << row << '\n';
    // cerr << col << '\n';
    // cerr << "---------\n";

    std::priority_queue<Node> q;
    for (int j = 0; j < n; j++) {
        if (col[j]) {
            q.ep(j, col[j]);    
        }
    }

    for (int i = 0; i < n; i++) {
        vector<int> t;

        while (!q.empty() and row[i] > 0) {
            auto [j, _] = q.top();
            q.pop();

            b[i][j] ^= 1;
            row[i]--;
            col[j]--;

            if (col[j]) t.eb(j);
        }

        for (auto j : t) {
            q.ep(j, col[j]);
        }
    }

    for (int j = 0; j < n; j++) {
        if (row[j] != 0 or col[j] != 0) {
            cout << "No\n";
            return;
        }
    }

    cout << "Yes\n";
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cout << b[i][j];
        }
        cout << "\n";
    }
}

D. Graph of Maximum Degree 3

Bobo 最近得到了一个(无向)图 $G=(V, E)$ 。他注意到这个图的每条边都是红色或蓝色，并且这个图的最大度不大于 $3$ 。

现在，Bobo 想知道 $G$ 中有多少个非空诱导子图 $G[S]=(S, E’)$ ，使得满足以下两个条件：

仅保留 $G[S]$ 的红色边形成的图是连通的。

仅保留 $G[S]$ 的蓝色边形成的图也是连通的。

由于答案可能太大，您需要输出结果模数 $998\,244\,353$ (一个素数)。

被诈骗了，一看 $998244353$ 以为是很难的题。

由 $\frac{3m}{2} \ge 2(m - 1)$ 得 $m \le 4$。

枚举联通块数数就做完了。

Code

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

    vector<vector<int>> g(n + 1);
    std::set<pii> s;

    for (int i = 1; i <= m; i++) {
        int u = read();
        int v = read();
        int c = read();

        if (u > v) swap(u, v);
        if (c) {
            g[u].eb(v), g[v].eb(u);
        } else {
            s.ep(u, v);
        }
    }

    vector<int> path;

    auto check = [&]() {
        int m = path.size();
        DSU dsu(m);

        for (int i = 0; i < m; i++) {
            for (int j = i + 1; j < m; j++) {
                int u = path[i];
                int v = path[j];
                if (u > v) swap(u, v);
                if (s.find({u, v}) == s.end()) continue;

                dsu.merge(i, j);
            }
        }

        for (int i = 1; i < m; i++) {
            if (!dsu.same(0, i)) {
                return 0;
            }
        }
        return 1;
    };

    int ans = 0;
    vector<int> vis(n + 1);

    auto dfs = [&](this auto&& self, int u, int p) -> void {
        vis[u] = 1;
        path.eb(u);

        if (p > 1) ans += check();
        if (p < 4) {
            for (int v : g[u]) {
                if (vis[v]) continue;
                self(v, p + 1);
            }
        }
        vis[u] = 0;
        path.pop_back();
    };

    for (int i = 1; i <= n; i++) {
        dfs(i, 1);
    }

    cout << ans / 2 + n;
    
}

E. Inverse Topological Sort

对于一个有向无环图(DAG) $G=(V,E)$ ，有 $|V|=n$ 个顶点，编号从 $1$ 到 $n$

给定两个序列 $A=(a _ 1,a _ 2,\dots,a _ n)$ 和 $B=(b _ 1,b _ 2,\dots,b _ n)$ ，其中 $A$ 是 $G$ 的字典序最小拓扑序，而 $B$ 是 $G$ 的字典序最大拓扑序，构造原图 $G=(V,E)$

$1\leq n\leq 10^5$

假设一张图只有点没有边，那么最小就是 $1,2,3,\cdots,n$，最大就是 $n, n - 1, \cdots, 1$。

假如在这张图上连了条边 $2 \rightarrow 1$，那么最小就变成了 $2,1,3,\cdots,n$。

因此 $A$ 中的逆序对应当在原图上有边，$B$ 中的顺序对同理。

但是这样是 $O(n^2)$ 条边。

发现边是有传递性的，每个 $A_i$ 只需要向后面最近的一个逆序数连边，这样即可满足限制。

无解的情况只有构造出来的图不是 DAG 或者最小最大拓扑序和 $A$ $B$ 不同。

Code >folded

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

    vector<int> a(n), b(n);
    for (int &x : a) cin >> x, x--;
    for (int &x : b) cin >> x, x--;

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

    vector<int> stk;
    for (int i = 0; i < n; i++) {
        while (not stk.empty() and stk.back() < a[i]) stk.pop_back();
        if (not stk.empty()) g[stk.back()].eb(a[i]);
        stk.eb(a[i]);
    }
    stk.clear();
    for (int i = 0; i < n; i++) {
        while (not stk.empty() and stk.back() > b[i]) stk.pop_back();
        if (not stk.empty()) g[stk.back()].eb(b[i]);
        stk.eb(b[i]);
    }

    // for (int i = 0; i < n; i++) {
    //     cerr << i << ' ' << g[i] << '\n';
    // }

    std::priority_queue<int> q;

    vector<int> ind(n);
    vector<int> A;
    for (int i = 0; i < n; i++) {
        std::sort(g[i].begin(), g[i].end());
        for (int j : g[i]) {
            // cout << i + 1 << ' ' << j + 1 << '\n';
            ind[j]++;
        }
    }
    for (int i = 0; i < n; i++) {
        if (!ind[i]) {
            q.ep(-i);
            // cerr << "inque: " << i + 1 << '\n';
        }
    }
    while (!q.empty()) {
        int u = -q.top(); q.pop();
        A.eb(u);
        // cerr << "deque: " << u + 1 << '\n';
        for (int v : g[u]) {
            if (!--ind[v]) {
                q.ep(-v);
                // cerr << "inque: " << v + 1 << '\n';
            }
        }
    }

    ind.assign(n, 0);

    vector<int> B;
    for (int i = 0; i < n; i++) {
        std::sort(g[i].rbegin(), g[i].rend());
        for (int j : g[i]) {
            ind[j]++;
        }
    }
    for (int i = n - 1; ~i; i--) {
        if (!ind[i]) {
            q.ep(i);
        }
    }
    while (!q.empty()) {
        int u = q.top(); q.pop();
        B.eb(u);
        for (int v : g[u]) {
            if (!--ind[v]) {
                q.ep(v);
            }
        }
    }

    // cerr << A << '\n';
    // cerr << B << '\n';

    if (a != A or b != B) {
        cout << "No\n";
        return;
    }

    cout << "Yes\n";

    vector<pii> ans;
    for (int i = 0; i < n; i++) {
        for (int j : g[i]) {
            ans.eb(i + 1, j + 1);
        }
    }
    cout << ans.size() << '\n';
    for (auto [u, v] : ans) cout << u << ' ' << v << '\n';
}

H. Random Tree Parking

考虑一个停车场，其形式为树 $T$ ，标签为 $[n]=\{1,2,\dots,n\}$ ，根节点为 $1$ 。树的边朝向根顶点。我们有一系列 $n$ 司机，每个司机都有自己喜欢的停车位，这是树中的一个顶点。司机一个接一个地到达，每个司机 $i$ $(1 \leq i \leq n)$ 都试图停在他们喜欢的停车位 $s _ i\in [n]$ 。如果停车位是空的，他们就停在那里。否则，他们沿着边向根顶点行驶，停在遇到的第一个空顶点。如果没有空顶点，他们就会离开停车场，即树，而无需停车。

如果所有司机都成功，即所有司机都能找到停车位，那么顶点序列 $\mathbf{s} \in [n]^n$ 就被称为树 $T$ 的停车函数。

现在，给定一棵有 $n$ 个顶点的树 $T$ ，Bobo 想知道 $T$ 的停车函数数量是多少。由于 Bobo 也痴迷于随机性，他决定树 $T$ 应该按以下方式随机生成：

对于 $i=2,\dots,n$ ，顶点 $i$ 指向的点是从 $\{1,2,\dots,i-1\}$ 中独立均匀随机选择的。

由于答案可能太大，您应该输出答案模数 $998\,244\,353$ (一个素数)。

$2\leq n\leq 10^5$

对于 $u$ 的子树，可以选择的点的数量是 $[siz_u, siz_u + dep_i]$。最少的情况是每个点恰好选一次，一共 $siz_u$ 次，才可以填满子树。那么填满之后还可以任选最多 $dep_u$ 次，可以往上填到根。

那么可以做一个树形背包，把 $u$ 的每个儿子 $v$ 合并到 $u$ 上面，一路往上合并。转移的时候枚举选了多少个，然后乘上一个排列的系数（因为位置可以交换）。

由于数据的随机生成方式，树高是期望 $\log$ 的，所以复杂度是 $O(n \log n)$。

Code

void solve() {
    int n; cin >> n;
    
    vector<int> dep(n + 1);
    dep[1] = 1;
    vector<vector<int>> g(n + 1);
    for (int i = 2; i <= n; i++) {
        int x; cin >> x;
        dep[i] = dep[x] + 1;
        g[x].eb(i);
    }

    vector<int> siz(n + 1);
    vector<vector<Z>> dp(n + 1);
    for (int u = n; u; u--) {
        dp[u].assign(dep[u] + 1, 1);
        for (int v : g[u]) {

            vector<Z> ndp(dep[u] + 1);
            for (int i = 0; i <= dep[u]; i++) {
                for (int j = 0; i + j <= dep[u]; j++) {
                    ndp[i + j] += dp[u][i] * dp[v][j]
                                * comb.binom(siz[u] + siz[v] + i + j, siz[u] + i);
                }
            }
            dp[u] = std::move(ndp);
            siz[u] += siz[v];
        }

        siz[u]++;
        for (int i = 0; i < dep[u]; i++) {
            dp[u][i] = dp[u][i + 1];
        }
    }
    cout << dp[1][0];
}

I. Refresher into Midas

队友秒了。

J. Teleportation

（并不）容易想到，操作过操作一之后，可以在任意时刻直接从 $u$ 走向 $u + 1$，代价为 $1$。

所以建两层图就做完了。

Code

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

    int nod = 2 * n;
    vector<int> a(nod);
    for (int i = 0; i < n; i++) {
        a[i] = read();
        a[i + n] = a[i];
    }

    vector<int> vis(nod);
    vector<int> dis(nod, inf);

    std::priority_queue<Node> q;

    dis[0] = 0;
    q.ep(0, 0);

    auto relax = [&](int u, int v, int dist) {
        if (dis[v] > dis[u] + dist) {
            dis[v] = dis[u] + dist;
            if (!vis[v]) q.ep(v, dis[v]);
        }
    };

    while (!q.empty()) {
        auto [u, _] = q.top();
        q.pop();

        if (vis[u]) continue;
        vis[u] = 1;

        if (u < n) {
            relax(u, (u + a[u]) % n, 1);
            relax(u, n + (u + a[u] + 1) % n, 2);
        } else {
            relax(u, n + (u + a[u]) % n, 1);
            relax(u, n + (u + 1) % n, 1);
        }
    }
    cout << min(dis[T], dis[T + n]);
}

VP 2023 ICPC 澳门

https://tosakaucw.github.io/vp-2023-icpc-澳门/

Author

TosakaUCW

Posted on

2024-12-13

Updated on

2024-12-15

Licensed under

#XCPC VP 澳门

VP 2023 ICPC 澳门

A. (-1,1)-Sumplete

D. Graph of Maximum Degree 3

E. Inverse Topological Sort

H. Random Tree Parking

I. Refresher into Midas

J. Teleportation

Author

Posted on

Updated on

Licensed under

Comments

Catalogue