专栏文章

题解：AT_arc195_b [ARC195B] Uniform Sum

22huk
AT_arc195_b题解参与者 3已保存评论 2

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
2 条
当前快照
1 份
快照标识符
@miptaskf
此快照首次捕获于
2025/12/03 17:35
3 个月前
此快照最后确认于
2025/12/03 17:35
3 个月前
查看原文
令 f(z)f(z) 表示最多能找到多少个对 (i,j)(i, j) 使得 ai+bj=za_i + b_j = z，且每个对的 ii 互不相同，jj 互不相同。比如当 a=[1,1],b=[2,2]a=[1,1],b=[2,2] 时 f(3)=2f(3)=2。
令数组 aa 中 −1-1 的个数为 cac_a，数组 bb 中 −1-1 的个数为 cbc_b。
如果最终我们希望 a1+b1=a2+b2=⋯=za_1+b_1=a_2+b_2=\dots=z，首先我们会尽可能多地将已经确定的数字（不是 −1-1 的数字）配对，这样总共会配成 f(z)f(z) 个对。
此时数组 aa 中还剩于有 cac_a 个 −1-1 和 n−ca−f(z)n-c_a-f(z) 个非 −1-1，数组 bb 中有 cbc_b 个 −1-1 和 n−cb−f(z)n-c_b-f(z) 个非 −1-1。现在这些非 −1-1 的数已经没法两两配对了（因为上一步匹配完了），因此每个非 −1-1 的数都会找一个 −1-1 进行配对。于是 zz 合法等价于 ca≥n−cb−f(z)c_a \ge n-c_b-f(z) 且 cb≥n−ca−f(z)c_b \ge n-c_a-f(z)。
当然，因为 −1-1 不能替换为负数，所以 z≥max⁡(a1,a2,…,an,b1,b2,…,bn)z \ge \max(a_1,a_2,\dots,a_n,b_1,b_2,\dots,b_n) 是必要的。
首先特判掉一个特殊情况：如果 ca≥n−cbc_a \ge n -c_b 且 cb≥n−cac_b \ge n-c_a（即 f(z)=0f(z) =0），那么直接输出 Yes。这个的含义是，每个非 −1-1 的数都能找到一个 −1-1 配对。显然这样是可以构造的，把 zz 取到非常大即可。
现在我们只需要求解所有 f(z),0≤z≤2×109f(z),0 \le z \le 2\times 10^9 就好了。全求出来显然不可能，但显然满足 f(z)≠0f(z) \ne 0 的 zz 是 n2n^2 级别的。这样复杂度就对了。
但是怎样快速的求出这 n2n^2 个 f(z)f(z) 的值呢？首先将 a,ba,b 放到桶里，令 AxA_x 表示 aa 中 xx 的出现次数，BxB_x 表示 bb 中 xx 的出现次数，n2n^2 枚举 i,ji,j，将 f(i+j)f(i+j) 加上 min⁡(Ai,Bj)\min(A_i,B_j) 即可。
CPP
#include <bits/stdc++.h>

using namespace std;

const int N = 2010;

int n, a[N], b[N];
unordered_map<int, int> A, B, f;

signed main() {
    cin >> n;

    int mx = 0;
    for (int i = 1; i <= n; ++ i ) {
        cin >> a[i];
        A[a[i]] ++ ;
        mx = max(mx, a[i]);
    }
    
    for (int i = 1; i <= n; ++ i ) {
        cin >> b[i];
        B[b[i]] ++ ;
        mx = max(mx, b[i]);
    }
    
    for (auto [i, x] : A)
        if (i != -1)
            for (auto [j, y] : B)
                if (j != -1)
                    f[i + j] += min(x, y);

    if (A[-1] >= n - B[-1]) {
        cout << "Yes\n";
        return 0;
    }

    for (auto [i, x] : f)
        if (i >= mx && A[-1] >= n - B[-1] - x) {
            cout << "Yes\n";
            return 0;
        }

    cout << "No\n";
    
    return 0;
}

评论

共 2 条评论，欢迎与作者交流。

正在加载评论...