Codeforces Round 919 (Div. 2) 题解 | JorbanS

A - Satisfying Constraints

int solve() {
    cin >> n;
    vector<int> e;
    int l = 1, r = 1e9;
    for (int i = 0; i < n; i ++) {
        int op, x; cin >> op >> x;
        if (op == 3) e.push_back(x);
        else if (op == 1) l = max(l, x);
        else r = min(r, x);
    }
    if (l > r) return 0;
    sort(e.begin(), e.end());
    int ll = lower_bound(e.begin(), e.end(), l) - e.begin();
    int rr = upper_bound(e.begin(), e.end(), r) - e.begin() - 1;
    return r - l + 1 - (rr - ll + 1);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

B - Summation Game

cin >> n >> k >> x;
for (int i = 1; i <= n; i ++) cin >> a[i];
sort(a + 1, a + n + 1);
for (int i = 1; i <= n; i ++) pre[i] = pre[i - 1] + a[i];
int res = -2e9;
if (n == k) res = 0;
for (int r = max(1, n - k); r <= n; r ++) {
    int l = max(1, r - x + 1);
    int cost = pre[l - 1] - (pre[r] - pre[l - 1]);
    res = max(res, cost);
}
return res;
1
2
3
4
5
6
7
8
9
10
11
12

C - Partitioning the Array

对于两个数 $x,y$，对 $m$ 取模，则 $x=k_{1}m+b$，$y=k_{2}m+b$，则对于 $m$ 的任意因数 $c$，$\because c|m$，$\therefore c|k_{1}m,c|k_{2}m$，而 $b\equiv b(\mathrm{mod}m)$。所以对于 $m$ 的任意因数 $c$，只要 $m$ 符合，$c$ 也符合，而 $gcd$ 为最大公因数，使得尽可能成立，因此只要让 $k_0,k_1,...,k_n$ 都代入，使得均起到限制最终 $gcd$ 的作用，若 $gcd=1$ 则没有 $m\ge 2$ 成立

// 赛时 code
int n, m;
int a[N];
int cnt, primes[N];
bool vis[N];

void getPrimes() {
    for (int i = 2; i <= 2e5; i ++) {
        if (vis[i]) continue;
        primes[cnt ++] = i;
        for (int j = i; j <= 2e5; j += i) vis[j] = true;
    }
}

bool check(int t, int mod) {
    for (int i = 0; i < t; i ++)
        for (int j = i + t; j < n; j += t)
            if (a[j] % mod != a[i] % mod) return false;
    return true;
}

int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }

int get(int t) {
    int d = abs(a[0] - a[t]);
    for (int i = 0; i < t; i ++)
        for (int j = i + t; j < n; j += t)
            d = gcd(d, abs(a[i] - a[j]));
    return d;
}

int solve() {
    cin >> n;
    for (int i = 0; i < n; i ++) cin >> a[i];
    int res = 1;
    bool st[N] = {0};
    for (int i = n; i >= 2; i --) {
        if (n % i || st[n / i]) continue;
        int d = get(n / i);
        if (d == 1) continue;
        for (int j = 0; j < cnt; j ++)
            if (check(n / i, primes[j])) {
                for (int k = n / i; k < n; k += n / i) {
                    if (n % k || st[k]) continue;
                    st[k] = true;
                    res ++;
                }
                break;
            }
    }
    return res;
}

int main() {
    getPrimes();
    FastIO
    Cases
    cout << solve() << endl;
    return 0;
}
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

inline int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }

int getD(int t) {
    int d = 0;
    for (int i = 0; i < n - t; i ++)
        d = gcd(d, abs(a[i] - a[i + t]));
    return d;
}

int solve() {
    cin >> n;
    for (int i = 0; i < n; i ++) cin >> a[i];
    int res = 1;
    bool st[N] = {0};
    for (int i = n; i >= 2; i --) {
        if (n % i) continue;
        if (getD(n / i) != 1) res ++;
    }
    return res;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20