Select a result to preview

2025ICPC 亚洲区域赛（南京）题解

B - What, More Kangaroos?

Question

一条数轴上有 n 个袋鼠，每个袋鼠的初始坐标为 ci(ci>0) ，有 4 个按钮，按下一个按钮会让所有袋鼠一起执行一个操作

你可以按键任意次，问最大化操作后具有负坐标的袋鼠的数量

Solution

很容易可以看出这个题是需要求一个 (x,y) 满足 aix+biy+ci<0 的最多方程数

由于 ci>0 说明原点肯定不在这个半平面内

假设答案为 (x,y) 那么把 (x,y) 扩大 t 倍对答案没有影响，所以可以看成是在无限远处，所以 ci 可以看成 0

于是问题就转化为 n 个经过原点的半平面，求最大重叠次数

按照极角排序后统计即可

Code

#include <bits/stdc++.h>
using namespace std;

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

    map<long double, int> mp;
    int now = 0;
    for (int i = 0; i < n; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        if (a == 0 && b == 0) { continue; }
        long double s = atan2l(a, -b); // 必须long double
        long double t = atan2l(-a, b);
        mp[s]++;
        mp[t]--;    
        if (s > t) {
            now++;
        }
    }

    int ans = now;
    for (auto _ : mp) {
        int delta = _.second;
        now += delta;
        ans = max(ans, now);
    }
    cout << ans << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    int t; cin >> t;
    while (t--) solve();
    return 0;
}

C - Distributing Candies（签到题）

队友写的签到

Code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll Tex, n;
void AC() {
    cin >> n;
    if (n & 1) cout << "No\n";
    else cout << "Yes\n" << n / 2 << " " << n / 2 << "\n";
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    cin >> Tex;
    while (Tex --) AC();
    return 0;
}

F - Bitwise And Path

Question

给定一个初始没有边的 n 个节点的无向图，进行 q 次操作

n≤103,q≤106,V≤212

Solution

考虑建 212=4096 层图，在每一层图上跑并查集，如果第 S 层并查集上的 u 和 v 是在同一个联通块内，表示从 u 到 v 存在一条值大于等于 S 的边

先考虑查询，相当于倍增的写法，从高到低查询每一位是否可行

然后考虑合并，一个暴力的想法是，如果我要添加一条边权为 w 的边，我对于 w 的子集的层都要把 u,v 合并

其实有很多重复操作，而且子集关系具有传递性

我们可以提前预处理出一颗树，一个节点的儿子节点都是其子集，当处理到一个节点上的 u,v 已经在同一个联通块了，可以保证以这个树为根节点的子树中的点 u,v 都是在一个联通块内，就不用再链接了

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MAXN = 1e3 + 5;
ll Tex, f[(1 << 12) + 2][MAXN], n, q, vis[(1 << 12) + 2];
vector<ll> mp[(1 << 12) + 2];
void init_set(ll fa[]) {
    for (int i = 0; i <= n; i ++) {
        fa[i] = i;
    }
}
ll find_set(ll fa[], ll x) {
    return fa[x] = fa[x] == x ? fa[x] : find_set(fa, fa[x]);
}
void union_set(ll fa[], ll x, ll y) {
    x = find_set(fa, x);
    y = find_set(fa, y);
    if (x == y) return;
    fa[x] = y;
}
void dfs(ll val, ll x, ll y) {
    x = find_set(f[val], x);
    y = find_set(f[val], y);
    if (x == y) return;
    union_set (f[val], x, y);
    for (auto it : mp[val]) {
        dfs (it, x, y);
    }
}
void AC() {
    cin >> n >> q;
    for (int i = 0; i < (1 << 12); i ++) {
        init_set(f[i]);
    }
    ll ans = 0;
    while (q --) {
        char ch;
        ll x, y, w;
        cin >> ch >> x >> y;
        if (ch == '+') {
            cin >> w;
            dfs(w, x, y);
        }
        else {
            ll dq = 0;
            for (int i = 11; i >= 0; i --) {
                ll xx = find_set (f[dq | (1 << i)], x);
                ll yy = find_set (f[dq | (1 << i)], y);
                if (xx == yy) dq |= (1 << i);
            }
            if (find_set(f[0], x) != find_set(f[0], y)) dq = -1;
            ans += dq;
        }
        // cout << q << "\n";
    }
    cout << ans << "\n";
}
void calc(ll x) {
    vis[x] = 1;
    // cout << x << "\n";
    for (int i = 0; i < 12; i ++) {
        if ((x >> i) & 1) {
            ll xx = x - (1 << i);
            mp[x].push_back(xx);
            if (vis[xx]) continue;
            calc(xx);
        }
    }
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    calc((1 << 12) - 1);
    cin >> Tex;
    while (Tex --) AC();
    return 0;
}

G - Bucket Bonanza

Question

有 n 个水桶，第 i 个水桶有 vi 的水，每秒漏 li 的水

你可以在第 0 秒之前对任意个水桶进行合并，合并后的水桶中的水为 max{v}，漏的速度为 min{l}

有 q 组独立的询问，每次问第 ti 秒第时候，所有水桶中剩下水的和的最大值

Solution

思维好题，摘至官方题解

先不考虑有的水桶会漏完的情况。合并两个水桶等价于删除两者间较小的容量和较大的漏水率。可以发现答案和水桶容量-漏水对应关系无关，只和容量集合和漏水集合有关

对于每次询问，考虑贪心，每次尝试合并容量最小的水桶和漏水最多的水桶，直到最小容量大于最多漏水量。如果容量最小和漏水最多是同一个水桶，这个水桶不可能储水，等价于删除

接下来考虑有的水桶会漏完的情况，此时把漏完的水桶和其它桶合并，答案不会变得更差。所以至少存在一个最优答案是水漏不完的（或只保留 0 个水桶），直接用之前的贪心解决即可

所以，每次询问二分删多少个水桶即可

Code

#include <bits/stdc++.h>
using namespace std;
#define int long long

using ll = long long;

void solve() {
    int n; cin >> n;
    vector<int> a(n + 1, 0), b(n + 1, 0);

    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 1; i <= n; i++) cin >> b[i];
    sort(a.begin() + 1, a.end());
    reverse(a.begin() + 1, a.end());
    sort(b.begin() + 1, b.end());

    vector<ll> sum_a(n + 1, 0), sum_b(n + 1,0);
    
    for (int i = 1; i <= n; i++) sum_a[i] = sum_a[i - 1] + a[i];
    for (int i = 1; i <= n; i++) sum_b[i] = sum_b[i - 1] + b[i];

    int q; cin >> q;

    while (q--) {
        int t; cin >> t;
        int l = 1, r = n + 1;
        while (l + 1 < r) {
            int mid = (r + l) / 2;
            if (a[mid] - t * b[mid] >= 0) l = mid;
            else r = mid;
        }
        cout << max(sum_a[l] - 1ll * t * sum_b[l], 0ll) << ' ';
    }
    cout << '\n';
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    int t; cin >> t;
    while (t--) solve();
    return 0;
}

K - Xiangqi

Question

神秘象棋题

中国象棋棋盘上有一个车和一个马，给出车和马的位置，此时马先走

问，车是否能吃掉马

Solution

神秘结论题，如果车不能在马走了一步之后然后抓到马，那么就永远抓不死马