2025 ICPC 成都区域赛

A. A Lot of Paintings

有点恶心

如果取整后为 $a_i$ ，说明其原来的占比应该为 $[\max(0,a_i-0.5), a_i+0.5)$ . 我们计算出下界和上界，判断 $100$ 是否在界内. 若不在，则不行.

接着就是构造. 如果 $\sum a_i\gt 100$ ，那么我们只需要让其中的一些 $a_j\gets a_j-0.5$ 即可（直到和为 $100$ ）；否则如果 $\sum a_i\lt 100$ ，那么我们需要让其中的一些 $a_j\gets a_j+0.499999$ 并让一个 $a_j\gets a_j+0.000001\times T$ ，其中 $T=2(100-\sum a_i)$ .

需要注意的是浮点数误差问题. 建议在实现的时候使用整数代替.

AC Code

#include <bits/stdc++.h>
constexpr int N = 2e5 + 10;
constexpr int V = 1e9, M = 2e5;
using ll = long long;

ll n, a[N], b[N];

void gen() {
    std::mt19937 rng(std::random_device{}());
    n = rng() % M + 1;
    long long sum = 0;
    for (int i = 1; i <= n; i++) b[i] = rng() % V + 1, sum += b[i];
    for (int i = 1; i <= n; i++) a[i] = std::round(1.0L * b[i] / sum * 100.0);
    std::cerr << n << "\n";
    for (int i = 1; i <= n; i++) std::cerr << a[i] << " \n"[i == n];
}

void run() {
    // gen();
    std::cin >> n;
    int low = 0, high = 0;
    ll sum = 0;

    for (int i = 1; i <= n; i++) {
        std::cin >> a[i];
        b[i] = 0;
        low += a[i] == 0 ? 0 : 1;
        sum += a[i];
        high += a[i] == 100 ? 0 : 1;
    }

    if (!(sum * 2 - low <= 200 && 200 < sum * 2 + high || (sum == 100))) {
        std::cout << "No\n";
        return;
    }
    std::cout << "Yes\n";
    sum -= 100;
    ll t = -2 * sum;

    if (sum > 0) {
        sum *= 2;
        for (int i = 1; i <= n && sum > 0; i++)
            if (a[i] >= 1) {
                b[i] = 1;
                sum--;
            }
    } else {
        sum = -2 * sum;
        int i = 1;
        for (; i <= n && sum > 0; i++) {
            if (a[i] < 100) {
                b[i] = -1;
                sum--;
            }
        }
        bool put = false;
        for (; i <= n; i++) {
            if (a[i] < 100) {
                b[i] = -2;
                put = true;
                break;
            }
        }
    }
    assert(sum == 0);

    ll base = 1000000, ssum = 0;
    for (int i = 1; i <= n; i++) {
        if (b[i] == 0) b[i] = a[i] * base;
        else if (b[i] > 0) b[i] = a[i] * base - 500000;
        else if (b[i] == -1) b[i] = a[i] * base + 499999;
        else if (b[i] == -2) b[i] = a[i] * base + t;
        ssum += b[i];
    }

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

int main() {
    int t = 1;
    std::cin >> t;
    while (t--) run();
}

B. Blood Memories

居然是神秘矩阵

因为 $n\le 6$ ，想到了可以用 bitmask 通过枚举上一轮和下一轮的技能，计算 cost 和 attack. 所以我们可以构建出有向图（边权为攻击力，如果有边就说明 cost $\le m$ ）. 题目转化成在有向图上移动，使得走 $R$ 条边后走过的边权和最大.

一个经典 trick 就是把有向图表示成矩阵， $M_{i,j}=v$ 表示 $i\to j$ 有边，且边权为 $v$ （当没有边时，设为 $-\infin$ ）. 然后重新定义一下“加法”和“乘法”：

a\oplus b=\max(a,b)\\ a\otimes b=a+b

考虑矩阵元素的加法与乘法的实际含义：考察 $X=MM$ ，因为 $M$ 代表了走一步，所以 $X$ 代表走两步. 故 $X_{i,j}=\sum_{k=1}^{L} M_{i,k}\otimes M_{k,j}$ ，即枚举 $i\to k\to j$ . 既然我们想要最大化边权和，所以这里的 $\oplus$ 代表的就是 $\max$ 操作；而走两步的边权和就是两条边加起来.

根据上面的分析，最终的答案就是矩阵 $X=M^R$ 中最大的那个元素. 时间复杂度 $O(2^{3n} \log R)$

AC Code

#include <bits/stdc++.h>
using ll = long long;
constexpr int N = 6, M = 1 << N;
constexpr ll inf = 1e18;

int n, m, k, r, a[N], c[N];
int state;

struct Mat : public std::array<std::array<ll, M>, M> {
    Mat() { clear(0); }
    Mat(ll val) { clear(val); }
    void clear(ll val) {
        for (int i = 0; i < state; i++)
            for (int j = 0; j < state; j++) at(i).at(j) = val;
    }
    Mat operator*(Mat &rhs) {
        Mat res(-inf);

        for (int i = 0; i < state; i++)
            for (int j = 0; j < state; j++)
                for (int k = 0; k < state; k++) res[i][j] = std::max(res[i][j], (*this)[i][k] + rhs[k][j]);

        return res;
    }

    void debug() const {
        for (int i = 0; i < state; i++) {
            for (int j = 0; j < state; j++) {
                if (at(i).at(j) == -inf) std::cout << std::setw(5) << "-inf";
                else std::cout << std::setw(5) << at(i).at(j);
            }
            std::cout << "\n";
        }
    }
};

ll assign(int m1, int m2) {
    int totcost = 0;
    ll atk = 0;
    for (int i = 0; i < n; i++) {
        if (m2 >> i & 1) {
            atk += a[i];
            totcost += c[i];
            m1 >> i & 1 ? totcost += k : 0;
        }
    }

    return totcost <= m ? atk : -inf;
}

void run() {
    std::cin >> n >> m >> k >> r;
    state = 1 << n;
    for (int i = 0; i < n; i++) std::cin >> a[i] >> c[i];

    Mat x(-inf);
    for (int i = 0; i < state; i++)
        for (int j = 0; j < state; j++) x[i][j] = assign(i, j);
    // x.debug();

    Mat res(0);
    while (r) {
        if (r & 1) res = res * x;
        x = x * x;
        r >>= 1;
    }

    ll ans = 0;
    for (int i = 0; i < state; i++)
        for (int j = 0; j < state; j++) ans = std::max(ans, res[i][j]);

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

int main() {
    std::cin.tie(0)->sync_with_stdio(0), std::cout.tie(0);
    int t;
    std::cin >> t;
    while (t--) run();
}

G. GCD of Subsets

智障了…… WA 了三发

思路很简单，我们把数字分成两部分，一部分 $A=\set{x:k|x}$ ，另一部分 $B=\set{x:k \nmid x}$ . 如果我们有 $m$ 次操作，我们先把 $B$ 集合里的数，先变成 $k$ ，这样就可以值选一个数算 gcd，可以操作 $\min(m, |B|)$ 次.

如果 $m\gt |B|$ ，那么剩下的次数可以把 $A$ 中的一部分元素也变成 $k$ ，然后让 $A$ 中剩下的元素两两配对 $\gcd(ki, k(i+1))=k$ . 因为 $A$ 中的元素 $k$ 必定是单独取走，所以最多可以转化 $f=\min(|A|-1, m-|B|)$ 个元素.

AC Code

#include <bits/stdc++.h>
using ll = long long;

void run() {
    ll n, k, m;
    std::cin >> n >> k >> m;

    ll c = n / k;
    ll rem = m - std::min(n - c, m);
    ll tf = std::min(rem, c - 1);

    ll ans = 0;
    ans = std::max(ans, std::min(n - c, m) + tf + (c - 1 - tf) / 2 + 1);

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

int main() {
    std::cin.tie(0)->sync_with_stdio(0), std::cout.tie(0);
    int t;
    std::cin >> t;
    while (t--) run();
}

J. Judging Papers

简单的模拟题，先计算一开始有哪些 paper 过了（记为 $a$ ），只保留没有过的 paper 然后对于每张 paper 计算 rebuttal 后的新分数，判断 rebuttal 后有多少 paper 可以过. 假设有 $f$ 张，因为最多 rebuttal $b$ 张 paper，所以答案就是 $a+\min(f,b)$

AC Code

#include <bits/stdc++.h>
constexpr int M = 11;

int n, m, k, b;

void run() {
    std::cin >> n >> m >> k >> b;

    std::vector r(n, std::vector<int>(m, 0));
    std::vector low(n, 0), high(n, 0), sum(n, 0);

    int ans = 0;
    std::vector<int> uns;
    for (int i = 0; i < n; i++) {
        for (auto &p : r[i]) {
            std::cin >> p;
            sum[i] += p;

            if (p <= 0) low[i]++;
            else high[i]++;
        }

        if (sum[i] >= k) ans++;
        else uns.push_back(i);
    }

    int cnt = 0;
    for (auto i : uns) {
        if (sum[i] - high[i] + low[i] >= k) cnt++;
    }

    std::cout << ans + std::min(cnt, b) << "\n";
}

int main() {
    std::cin.tie(0)->sync_with_stdio(0), std::cout.tie(0);
    int t;
    std::cin >> t;
    while (t--) run();
}

L. Label Matching

题目意思很直白，对于 $T_i$ ，判断子树能否互相 match. 令 $c_a[v],c_b[v]$ 分别表示对 $u\in T_i$ 的 $a_u,b_u$ 进行计数，则失配的 $a,b$ 标签分别为 $r_a=\sum_v \max(0, c_a[v]-c_b[v])$ 和 $r_b=\sum_v \max(0, c_b[v]-c_a[v])$ ，则能够成功匹配的条件为

c_a[0]\ge r_b \texttt{ and }c_b[0]\ge r_a

我们发现，添加或删去一个节点对 $r_a, r_b$ 的影响可以在 $O(1)$ 的时间内计算出来，并且检查匹配成功的条件也可以 $O(1)$ 完成. 所以，我们可以使用启发式合并在 $O(n\log n)$ 的时间内解决.

AC Code

#include <bits/stdc++.h>
constexpr int N = 2e5 + 10;

int n, a[N], b[N], ans[N];
int L[N], R[N], stamp, size[N], son[N], ord[N], dfn[N];
std::vector<int> g[N];
int remainA{0}, remainB{0};
int cnta[N], cntb[N];

void clean() {
    for (int i = 0; i <= n; i++) cnta[i] = cntb[i] = 0;
    for (int i = 1; i <= n; i++) {
        g[i].clear(), ans[i] = 0;
        L[i] = R[i] = 0;
        size[i] = 0;
        son[i] = 0;
    }
    stamp = 0;
    remainA = remainB = 0;
}

void dfs(int u, int fa) {
    dfn[u] = ++stamp;
    ord[stamp] = u;
    L[u] = dfn[u];
    size[u] = 1;

    for (auto v : g[u]) {
        if (v == fa) continue;
        dfs(v, u);
        size[u] += size[v];
        if (size[v] > size[son[u]]) son[u] = v;
    }

    R[u] = stamp;
}

void modify(int *x, int val, int v = 1) {
    if (val == 0) {
        x[val] += v;
        return;
    }

    int da_old = std::max(0, cnta[val] - cntb[val]);
    int db_old = std::max(0, cntb[val] - cnta[val]);
    x[val] += v;
    int da_new = std::max(0, cnta[val] - cntb[val]);
    int db_new = std::max(0, cntb[val] - cnta[val]);
    remainA += da_new - da_old;
    remainB += db_new - db_old;
}

void add(int u) {
    modify(cnta, a[u], 1);
    modify(cntb, b[u], 1);
}

void del(int u) {
    modify(cnta, a[u], -1);
    modify(cntb, b[u], -1);
}

int getans() { return cnta[0] >= remainB && cntb[0] >= remainA; }

void compute(int u, int fa, bool keep) {
    for (auto v : g[u]) {
        if (v == fa or v == son[u]) continue;
        compute(v, u, false);
    }

    if (son[u]) compute(son[u], u, true);

    for (auto v : g[u]) {
        if (v == fa or v == son[u]) continue;
        for (int i = L[v]; i <= R[v]; i++) add(ord[i]);
    }
    add(u);
    ans[u] = getans();

    if (!keep)
        for (int i = L[u]; i <= R[u]; i++) del(ord[i]);
}

void run() {
    std::cin >> n;
    clean();

    for (int i = 1; i <= n; i++) std::cin >> a[i];
    for (int i = 1; i <= n; i++) std::cin >> b[i];
    for (int i = 1, u, v; i < n; i++) {
        std::cin >> u >> v;
        g[u].push_back(v), g[v].push_back(u);
    }

    dfs(1, 0);
    compute(1, 0, true);

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

int main() {
    std::cin.tie(0)->sync_with_stdio(0), std::cout.tie(0);
    int t;
    std::cin >> t;
    while (t--) run();
}