Codeforces Round #680 (Div. 2)

传送门

A. Array Rearrangment

数学

题意

给定 \(A,B\) 数组和一个数 \(x\), 将 \(A\) 数组和 \(B\) 数组匹配，使得 \(A_i + B_i \le x\)

分析

\(A\) 的最大值 \(A_{max}\) 必须要找一个 \(B\) 数组的元素匹配。那么如果最小的 \(B_{min}\) 都无法满足，那么无解。否则存在解。

考虑假如存在一个解，那么它是不是一定也存在 \(A_{max}\) 与 \(B_{min}\) 匹配的解. 如果有一个满足的解 \(A_{max}\) 和 \(B_i\) 匹配，\(B_{min}\) 和 \(A_j\) 匹配.

那么 \(A_{max}+ B_i \le x\) 且 \(B_{min} + A_j \le x\) 其不是最大值与最小值匹配的情况. 那么交换 \(B_{min}\) 与 \(B_{i}\) . 可以证明 \(A_{max} + B_{min} \le A_{max} + B_i \le x\) 并且 \(B_{i} + A_{j} \le B_{i} + A_{max} \le x\) 然后发现交换后还满足. 那么把数组排序后，最大值与最小值匹配即可.

代码

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
#include <bits/stdc++.h>
using namespace std;
#define sz(x) ((int) (x).size())
typedef pair<int, int> pii;
typedef long long ll;
const int maxn = 5e5 + 5;
template<class T> void print(T & x){ cout << x; }
template<class T,class U> void print(pair<T,U> & p){cout << "("; print(p.first); cout << ", "; print(p.second); cout << ")"; }
template<class T> void print(vector<T> & v) {
    cout << "{";
    if (sz(v)) print(v[0]);
    for (int i = 1; i < sz(v); i++) cout << ", ", print(v[i]);
    cout << "}\n";
}


int n, m, T;

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> T;
    while (T--) {
        int x;
        cin >> n >> x;
        vector<int> A(n+1);
        vector<int> B(n+1);
        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(), greater<>());
        int ok = 1;
        for (int i = 1;i <= n; ++i) {
            if (A[i] + B[i] > x) { ok = 0; break; }
        }
        if (ok) cout << "YES" << endl;
        else cout << "NO" << endl;     
    }
    return 0;
}

B. Elimination

数学

题意

第一场比赛的排行榜中, 第 \(100\) 名分数为 \(a\) , 前 \(100\) 名选手在第二场比赛分数至少为 \(b\). 第二场比赛排行榜中，第 \(100\) 名选手分数为 \(c\) 前 \(100\) 名在第一场比赛的分数至少为 \(d\) . 每个选手总分为两场比赛分数之和，排行榜分数均降序排列，问总分排行榜第 \(100\) 名选手分数的最小可能值是多少.

分析

因为排行榜降序排列，所以第一场比赛所有选手总分 \(s_i \ge a + b\) ，第二场比赛前 \(100\) 名选手的总分 \(s_i \ge c + d\) . 所以总分前 \(100\) 名的总分最小可能值为 \(max(a+b,c+d)\) . 所以我们可以把最大值的那前 \(100\) 名就作为总分的前 \(100\) 名，符合题意.

代码

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
#include <bits/stdc++.h>
using namespace std;
#define sz(x) ((int) (x).size())
typedef pair<int, int> pii;
typedef long long ll;
const int maxn = 5e5 + 5;
template<class T> void print(T & x){ cout << x; }
template<class T,class U> void print(pair<T,U> & p){cout << "("; print(p.first); cout << ", "; print(p.second); cout << ")"; }
template<class T> void print(vector<T> & v) {
    cout << "{";
    if (sz(v)) print(v[0]);
    for (int i = 1; i < sz(v); i++) cout << ", ", print(v[i]);
    cout << "}\n";
}


int n, m, T;

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> T;
    while (T--) {
        int a, b, c, d;
        cin >> a >> b >> c >> d;
        cout << max(a+b, c+d) << endl;       
    }
    return 0;
}

C. Division

数学， 数论

题意

给定两个数 \(p, q\) ,求最大的 \(x\) 使得 \(p\) 是 \(x\) 的倍数，同时 \(x\) 是 \(q\) 的倍数.

分析

首先 \(x\) 最大不可能超过 \(p\) .假如令 \(x=p\) 如果 \(p\) 不是 \(q\) 的倍数，那么符合题意，输出 \(p\). 否则根据 唯一分解定理，\(q\) 有的因子 \(p\) 一定也有。我们枚举 \(q\) 的所有因子，用这个因子去约分 \(p\) 使得 \(p\) 不在是 \(q\) 的倍数。那么这些枚举的情况中，再取个最大值。

值得注意的是：用 \(\sqrt{q}\) 来枚举因子的时候和判断素数略有不同，别忘了 \(q\) 自己本身也是一个因子，而且每枚举一个数，可以产生两个因子：

如果 \(a\) 是 \(q\) 的一个因子，那么 \(a/q\) 也是 \(q\) 的一个因子.

代码

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
#include <bits/stdc++.h>
using namespace std;
#define sz(x) ((int) (x).size())
typedef pair<int, int> pii;
typedef long long ll;
const int maxn = 5e5 + 5;
template<class T> void print(T & x){ cout << x; }
template<class T,class U> void print(pair<T,U> & p){cout << "("; print(p.first); cout << ", "; print(p.second); cout << ")"; }
template<class T> void print(vector<T> & v) {
    cout << "{";
    if (sz(v)) print(v[0]);
    for (int i = 1; i < sz(v); i++) cout << ", ", print(v[i]);
    cout << "}\n";
}

int n, m, T;


int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> T;
    while (T--) {
        ll p, q;
        cin >> p >> q;
        if (p % q != 0) {
            cout << p << endl;
            continue;
        }
        ll ans = 1;
        for (int i = 2;i <= sqrt(q); ++i) {
            if (q % i == 0) {
                ll tp = p;
                while (tp % q == 0) tp /= i;
                ans = max(ans, tp);
                tp = p;
                while (tp % q == 0) tp /= (q/i);
                ans = max(ans, tp);
            } 
        }
        while (p % q == 0) p /= q;
        ans = max(ans, p);
        cout << ans << endl;
    }
    return 0;
}

D. Divide and Sum

组合数学，数学

题意

把一个长度为 \(2n\) 的序列分为 \(n\) 和 \(n\) 长度的两部分。其中一个部分从小到大排序，记为 \(a_i\) . 另一个从大到小排序记为 \(b_i\) . 把这个分割的价值定义为 \[ f(a,b) = \sum_{i=1}^{n}|a_i-b_i| \] 问所有分割数组的可能性中，把所有可能的价值加起来的和是多少，答案对 \(998244353\) 取模

分析

对于两个数组中的位置 \(i\) 有 \(a_i\) 和 \(b_i\). 那么这个位置的价值就是 \(max(a_i,b_i) - min(a_i,b_i)\) . 那么对于数组中最大的那个数，不论它放到哪里，它都是大的那个。我们把原数组从小到大排序后，较大的那一半作为另一个数组 \(b\)，发现 \(b\) 都是在 \(b\) 中取最大值。加入把 \(b\) 中的某个元素和 \(a\) 中的交换，排序后小的那个数会排序到 \(b\) 数组的最后一位。而大的那个数也会排序到 \(a\) 数组的最后一位。发现交换后还是大的那个数取最大值。所以在分析一下，发现不论怎么交换，总价值不会改变。所以我们只需要计算一下从小到大排序的那种情况，然后乘以所有分割的可能性 \(C_{2n}^{n}\) 就是总的答案了

代码

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
#include <bits/stdc++.h>
using namespace std;
#define sz(x) ((int) (x).size())
typedef pair<int, int> pii;
typedef long long ll;
const int maxn = 5e5 + 5;
template<class T> void print(T & x){ cout << x; }
template<class T,class U> void print(pair<T,U> & p){cout << "("; print(p.first); cout << ", "; print(p.second); cout << ")"; }
template<class T> void print(vector<T> & v) {
    cout << "{";
    if (sz(v)) print(v[0]);
    for (int i = 1; i < sz(v); i++) cout << ", ", print(v[i]);
    cout << "}\n";
}
const int MOD = 998244353;

ll A[maxn], inv[maxn], f[maxn], rf[maxn];
ll n, m;
// 需要逆元数组，费马尔小定理求逆元
inline ll mul(ll a, ll b) {
    return (a * b) % MOD;
}
inline ll add(ll a, ll b) { // 带减法
    return ((a + b) % MOD + MOD) % MOD;
}
ll c(int n, int k) {
    return (k < 0 || k > n) ? 0 : mul(f[n], mul(rf[n-k], rf[k]));
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n;
    n *= 2;
    inv[1] = 1;
    for(int i = 2; i <= n; ++ i) {
        inv[i]=(ll)(MOD-MOD/i)*inv[MOD%i]%MOD;
    }
    f[0] = rf[0] = 1;
    for (int i = 1;i <= n; ++i) {
        f[i] = mul(f[i-1], i);
        rf[i] = mul(rf[i-1], inv[i]);
    }

    for (int i = 1;i <= n; ++i) {
        cin >> A[i];   
    }
    sort(A+1, A+n+1);
    ll ans = 0;
    for (int i = 1;i <= n/2; ++i) {
        ans = add(ans, abs(A[i] - A[n-i+1]));
    }
    cout << mul(c(n, n/2), ans) << endl;
    return 0;
}