2025 ICPC 网络赛 第一场

The 2025 ICPC Asia East Continent Online Contest (I)
Date 2025.09.07
Solved 8 / 13

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

J - Moving on the Plane

令 $a_i = x_i + y_i,\quad b_i = x_i - y_i$，曼哈顿转成切比雪夫以后两维就独立了。

在一维上（以 a 为例），一个点 a[i]，走 m 步 ±1，能到达的位置是从 a[i] - m 到 a[i] + m，走到具体位置 j 的方案数为：$$\text{ways}(a[i] \to j) = \binom{m}{\frac{m + (j - a[i])}{2}}, \text{若 } m+(j-a[i]) \text{ 为偶}$$

枚举长度为 $k$ 的区间，算一下至多的方案，然后容斥一下即可得到恰好的方案

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

    vector<int> a(n), b(n);
    for (int i = 0; i < n; i++) {
        int x, y; cin >> x >> y;
        a[i] = x + y;
        b[i] = x - y;
    }

    auto calc = [&](auto x, int k) -> Z {
        Z ans = 0;
        for (int l = x[0] - m - k; l <= x[0] + m; l++) {
            int r = l + k;

            Z prod = 1;
            for (int i = 0; i < n; i++) {
                Z sum = 0;
                for (int j = l; j <= r; j++) {
                    int t = j + m - x[i];
                    if (t % 2 != 0) continue;
                    sum += comb.binom(m, t / 2);
                }
                prod *= sum;
            }
            ans += prod;
        }
        return ans;
    };

    Z ta = calc(a, k) - calc(a, k - 1);
    Z tb = calc(b, k) - calc(b, k - 1);
    cout << ta * tb << '\n';
}

D - Min-Max Tree

相当于给每个点分配一个 0 / -1 / 1 的系数

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

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

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

    vector f(n + 1, vector(3, 0ll));

    // 1 -, 2 +

    auto dfs = [&](this auto&& dfs, int u, int fa) -> void {

        int g = 0;
        int mx = 0;

        for (int v : adj[u]) if (v != fa) {
            dfs(v, u);
            g += f[v][0];

            if (!mx or f[v][1] - f[v][0] > f[mx][1] - f[mx][0]) {
                mx = v;
            }
        }

        f[u][0] = g, f[u][1] = g - a[u], f[u][2] = g + a[u];

        for (int v : adj[u]) if (v != fa) {
            int now = g - f[v][0];

            f[u][1] = max(f[u][1], now + f[v][1]);
            f[u][2] = max(f[u][2], now + f[v][2]);

            f[u][0] = max(f[u][0], now + f[v][1] + a[u]);
            f[u][0] = max(f[u][0], now + f[v][2] - a[u]);

            if (mx and mx != v) {
                f[u][0] = max(f[u][0], now + f[v][2] + (f[mx][1] - f[mx][0]));
            }
        }
    };

    dfs(1, 0);

    cout << f[1][0] << '\n';
}

C - Canvas Painting

调整法不难证明这样是最优的

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

    map<int, vector<int>> mp;
    for (int i = 0; i < m; i++) {
        int l, r;
        cin >> l >> r;
        mp[l].eb(r);
    }

    vector adj(mp.begin(), mp.end());
    multiset<int> s;
    int ans = n;

    for (int i = 0; auto &[l, vec] : adj) {
        for (auto r : vec) {
            s.insert(r);
        }

        int nl = i + 1 == adj.size() ? n : adj[i + 1].first;
        for (int j = l; j < nl; j++) {
            while (!s.empty() and *s.begin() <= j) {
                s.erase(s.begin());
            }

            if (s.empty()) break;

            ans--;
            s.erase(s.begin());
        }
        i++;
    }

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

M - Teleporter

struct Node {
    int x, dis;
    bool friend operator < (Node a, Node b) {
        return a.dis > b.dis;
    }
};
void solve() {
    int n = read();
    int m = read();
    
    using pii = pair<int, int>;
    vector<vector<pii>> g(n + 5);
    for (int i = 1; i < n; i++) {
        int u = read();
        int v = read();
        int dis = read();
        g[u].emplace_back(v, dis);
        g[v].emplace_back(u, dis);
    }
    const int inf = 1e18;
    vector<pii> path(m);
    for (auto &[x, y] : path) {
        x = read(), y = read();
    }

    vector dis(n + 5, vector(n + 5, inf));
    dis[0][1] = 0;

    vector<int> ans(n + 1);

    for (int k = 0; k <= n; k++) {
        if (k != 0) {
            for (auto [x, y] : path) {
                dis[k][x] = min(dis[k][x], dis[k - 1][y]);
                dis[k][y] = min(dis[k][y], dis[k - 1][x]);
            }
        }
        vector vis(n + 5, 0);
        priority_queue<Node> q;

        for (int i = 1; i <= n; i++) {
            if (dis[k][i] == inf) continue;
            q.push({i, dis[k][i]});
        }
        while (!q.empty()) {
            auto [u, _] = q.top(); q.pop();
            if (vis[u]) continue; 
            vis[u] = 1;
            for (auto [v, w] : g[u]) {
                if (dis[k][u] + w < dis[k][v]) {
                    dis[k][v] = dis[k][u] + w;
                    q.push({v, dis[k][v]});
                }
            }
        }
    }

    for (int k = 0; k <= n; k++) {
        for (int i = 2; i <= n; i++) {
            if (k >= 1) dis[k][i] = min(dis[k][i], dis[k - 1][i]);
            ans[k] += dis[k][i];
        }
        cout << ans[k] << "\n";
    }
}

I - Knapsack Problem

struct Node {
    int x, f, g;
    bool friend operator < (Node a, Node b) {
        if (a.f != b.f) return a.f > b.f;
        return a.g > b.g;
    }
};
void solve() {
    int n = read();
    int m = read();
    int V = read();
    int T = read();
    
    using pii = pair<int, int>;
    vector<vector<pii>> g(n + 1);
    const int inf = 1e18;
    vector<pii> path(m);
    for (int i = 0; i < m; i++) {
        int x = read(), y = read(), w = read();
        g[x].emplace_back(y, w);
        g[y].emplace_back(x, w);
    }

    vector<int> dis(n + 1, inf), vis(n + 1);
    vector<int> F(n + 1, inf), G(n + 1, inf);

    F[T] = 1, G[T] = 0;
    priority_queue<Node> q;
    q.push({T, 0}); dis[T] = 0;

    while (!q.empty()) {
        auto [u, _, __] = q.top(); q.pop();
        if (vis[u]) continue;
        vis[u] = 1;
        for (auto [v, w] : g[u]) {
            int nG = G[u] + w;
            int nF = F[u];
            if (nG > V) nG = w, nF++;
            if (nF < F[v] or (nF == F[v] and nG < G[v])) {
                F[v] = nF, G[v] = nG;
                q.push({v, F[v], G[v]});
            }

            if (dis[u] + w < dis[v]) {
                dis[v] = dis[u] + w;
            }
        }
    }

    vector<int> ans(n + 1);
    for (int i = 1; i <= n; i++) {
        if (dis[i] == inf) ans[i] = -1;
        else ans[i] = F[i];
    }

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


signed main() {
    solve();
    return 0;
}

G - Sorting

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

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

    bool ok = 1;
    for (int i = 2; i <= n; i++) {
        if (!vis[i]) ok = false;
    }

    if (ok) cout << "Yes\n";
    else cout << "No\n";
}

B - Creating Chaos

void solve() {
    int n = read();
    int k = read();
    
    for (int i = n - k + 1; i <= n; i++) {
        cout << i << " ";
    }
}

A - Who Can Win

struct Node {
    int id, prob, tim, sta;
};

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

    vector<Node> a(n);

    unordered_map<string, int> buk; buk.reserve(n);
    unordered_map<int, string> Name; Name.reserve(n);
    set<string> winner;

    int cnt = 0;
    for (auto &[id, prob, tim, sta] : a) {
        string s; cin >> s;
        if (!buk.count(s)) buk[s] = cnt++, Name[cnt - 1] = s;
        id = buk[s];

        cin >> s; prob = s[0] - 'A';
        cin >> tim;
        cin >> s; sta = s == "Accepted" ? 1 : 0;
    }

    ranges::sort(a, [&](auto i, auto j) {
        return i.tim < j.tim;
    });

    vector penalty(cnt, 0);
    vector ac(cnt, 0);
    vector pntime(cnt, vector(26, 0));
    
    for (auto &[id, prob, tim, sta] : a) if (tim < 240) {
        if (pntime[id][prob] == -1) continue;

        if (sta == 1) {
            penalty[id] += tim + pntime[id][prob];
            ac[id]++;
            pntime[id][prob] = -1;
        } else {
            pntime[id][prob] += 20;
        }
    }

    vector<int> p(cnt);
    ranges::iota(p, 0);
    ranges::sort(p, [&](int i, int j) {
        if (ac[i] != ac[j]) return ac[i] > ac[j];
        return penalty[i] < penalty[j];
    });

    int best_pnt = penalty[p[0]];
    int best_ac = ac[p[0]];
    winner.insert(Name[p[0]]);

    for (int i = 1; i < cnt; i++) {
        int id = p[i];
        if ((ac[id] > best_ac) or (ac[id] == best_ac and penalty[id] <= best_pnt)) {
            winner.insert(Name[id]);
        }
    }

    for (auto &[id, prob, tim, sta] : a) if (tim >= 240) {
        if (pntime[id][prob] == -1) continue;

        penalty[id] += tim + pntime[id][prob];
        ac[id]++;
        pntime[id][prob] = -1;

        if ((ac[id] > best_ac) or (ac[id] == best_ac and penalty[id] <= best_pnt)) {
            winner.insert(Name[id]);
        }
    }


    for (auto x : winner) {
        cout << x << " ";
    }
    cout << "\n";
}