DDOSvoid's Blog

2021-2022 ACM-ICPC Latin American Regional Programming Contest B Because, Art!

发表于 分类于
本文字数： 3.8k 阅读时长 ≈ 3 分钟

题目描述

简要题意：给定两个长度均为 $n$ 的序列 $a_i,b_i$，定义一个数对 $(a_i,b_j)$ 的价值为 $a_i\times b_j$，现在每个 $a_i$ 和 $b_i$ 都只能使用一次，求对于 $k\in[1,n]$，选出 $k$ 个数对的最大价值和以及最小价值和

$n\le 10^5,-10^4\le a_i,b_i\le 10^4$

Solution

我们只需要考虑最大价值和，求最小价值和只需要将其中一个序列全部取反用同样的方法做即可

我们首先考虑如果没有负数，那么最大价值和一定是将 $a$ 和 $b$ 排序后对应位置匹配，如果有负数的话，能够发现，我们一定先凑价值为正的数对，即正正匹配，负负匹配，注意到这里的匹配也是按照绝对值的大小对应位置匹配

我们现在考虑剩下的那一段，可以发现，一定是一个序列全负，一个序列全正，我们按照绝对值递增来排序，可以发现我们如果我们需要在这里选 $k$ 对，那么匹配一定是 $\sum_{i=0}^ka_ib_{k-i}$，很显然这是一个卷积的形式，观察一下权值范围为 $10^{13}$，可以直接使用 $FFT$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <cmath>
#define maxn 100010
#define INF 1000000000000000000
#define ll long long
using namespace std;

typedef std::vector<ll> Poly;
namespace Pol {
    //const int N = 4200000; // 200MB
    const int N = 2100000; // 100MB
    const double pi = acos(-1);
    struct Complex {
        double x, y;

        Complex(double x = 0, double y = 0) : x(x), y(y) {}

        friend Complex operator + (const Complex &u, const Complex &v) { return Complex(u.x + v.x, u.y + v.y); }
        friend Complex operator - (const Complex &u, const Complex &v) { return Complex(u.x - v.x, u.y - v.y); }
        friend Complex operator * (const Complex &u, const Complex &v) {
            return Complex(u.x * v.x - u.y * v.y, u.x * v.y + u.y * v.x); 
        }
    } a[N], b[N];
 
    int P[N];
    void init_P(int n) {
        int l = 0; while ((1 << l) < n) ++l;
        for (int i = 0; i < n; ++i) P[i] = (P[i >> 1] >> 1) | ((i & 1) << l - 1);
    }
    vector<Complex> init_W(int n) {
        vector<Complex> w(n); w[1] = 1;
        for (int i = 2; i < n; i <<= 1) {
            auto w0 = w.begin() + i / 2, w1 = w.begin() + i;
            Complex wn(cos(pi / i), sin(pi / i));
            for (int j = 0; j < i; j += 2)
                w1[j] = w0[j >> 1], w1[j + 1] = w1[j] * wn;
        }
        return w; 
    } auto w = init_W(1 << 21);
    void DIT(Complex *a, int n) {
        for (int k = n >> 1; k; k >>= 1)
            for (int i = 0; i < n; i += k << 1)
                for (int j = 0; j < k; ++j) {
                    Complex x = a[i + j], y = a[i + j + k];
                    a[i + j + k] = (x - y) * w[k + j], a[i + j] = x + y;
                }
    }
    void DIF(Complex *a, int n) {
        for (int k = 1; k < n; k <<= 1)
            for (int i = 0; i < n; i += k << 1)
                for (int j = 0; j < k; ++j) {
                    Complex x = a[i + j], y = a[i + j + k] * w[k + j];
                    a[i + j + k] = x - y, a[i + j] = x + y;
                }
        for (int i = 0; i < n; ++i) a[i].x /= n, a[i].y /= n;
        reverse(a + 1, a + n);
    }
    Poly Mul(const Poly &A, const Poly &B, int n1, int n2) {
        int n = 1; while (n < n1 + n2 - 1) n <<= 1; init_P(n);
        for (int i = 0; i < n1; ++i) a[i] = Complex(A[i], 0);
        for (int i = 0; i < n2; ++i) b[i] = Complex(B[i], 0);
        fill(a + n1, a + n, Complex(0, 0)); fill(b + n2, b + n, Complex(0, 0));
        DIT(a, n); DIT(b, n);
        for (int i = 0; i < n; ++i) a[i] = a[i] * b[i];
        DIF(a, n); Poly ans(n1 + n2 - 1); for (int i = 0; i < n1 + n2 - 1; ++i) ans[i] = (ll) (a[i].x + 0.5);
        return ans;
    }
}  // namespace Pol

int n;
ll a[maxn], b[maxn];

ll ans[2][maxn];
void solve(ll *ans) {
    sort(a + 1, a + n + 1); sort(b + 1, b + n + 1);
    int pre = 0, suf = n + 1;
    for (int i = 1; i <= n; ++i)
        if (a[i] <= 0 && b[i] <= 0) pre = i;
    for (int i = n; i; --i)
        if (a[i] > 0 && b[i] > 0) suf = i;
    int k = suf - pre - 1; 
    for (int o = 1, p = 1, s = n; o <= n - k; ++o) {
        ans[o] = max({ 0ll, a[p] * b[p], a[s] * b[s] });
        if (p <= pre && ans[o] == a[p] * b[p]) ++p;
        else --s;
        ans[o] += ans[o - 1]; 
    } if (!k) return ;
    Poly A(k), B(k);
    for (int i = 0; i < k; ++i) A[i] = a[pre + i + 1], B[i] = b[pre + i + 1];
    if (A[0] < 0) {
        for (auto &t : A) t = -t;
        reverse(A.begin(), A.end());
    } else {
        for (auto &t : B) t = -t;
        reverse(B.begin(), B.end());
    }
    Poly res = Pol::Mul(A, B, k, k);
    for (int i = 0; i < k; ++i) ans[i + n - k + 1] = ans[n - k] - res[i];
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    cin >> n;
    for (int i = 1; i <= n; ++i) cin >> a[i];
    for (int i = 1; i <= n; ++i) cin >> b[i];
    solve(ans[1]);
    for (int i = 1; i <= n; ++i) a[i] = -a[i];
    solve(ans[0]);
    for (int i = 1; i <= n; ++i) cout << -ans[0][i] << " " << ans[1][i] << "\n";
    return 0;
}