Codeforces Round 673 (Div. 2)

十月 23, 2020 11640

做题情况

上一天有事耽搁了一题没写，早上补完了，今天的题因为时间不够都是 Practice。

A. Copy-paste

题意简述

给定一个长为 n 的正整数序列和正整数 k ，定义一次操作 (i, j)(1\leq i, j\leq n \text{ and } i \neq j) 为令 a_j := a_j + a_i ，且一旦序列里出现 > k 或操作会产生 > k 的数，那么这次操作就不能完成。求最多能进行多少次操作。

解题思路

一个很显然的想法是，每次取最小的两个数，然后把最小的加到次小的里面，用优先队列维护。多记一个值表示序列中的最大值。

代码实现

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
inline int read() {
    int s = 0, x = 1; char ch = getchar();
    while (!isdigit(ch)) { if (ch == '-') x = -x; ch = getchar(); }
    while (isdigit(ch)) { s = s * 10 + ch - '0'; ch = getchar(); }
    return s * x;
}


int main() {
    int T = read();
    while (T --> 0) {
        int n = read(); int k = read(); int maxx = 0;
        std::priority_queue<int, std::vector<int>, std::greater<int> > q;
        for (int i = 1; i <= n; ++i) {
            int x = read();
            q.push(x); maxx = std::max(maxx, x);
        } int ans = 0;
        while (maxx <= k) {
            int mn = q.top(); q.pop();
            int tmn = q.top(); q.pop();
            if (mn + tmn > k) break;
            ++ans;
            q.push(mn + tmn); q.push(mn);
        }
        printf("%d\n", ans);
    }
    return 0;
}

B. Two Arrays

题意简述

给定一个长度为 n 的序列，和一个整数 T 。定义 f(a, T) 为无序数对 (i, j) 满足 a_i + a_j = T 的个数。现在让你把这个序列的每个元素分成两组 \{a\}, \{b\} ，满足 f(a, T) + f(b, T) 最小。输出方案。

解题思路

把序列分成三组，一组所有的数都小于 \frac{T}{2} ，一组所有的数都等于 \frac{T}{2} ，一组所有的数都大于 \frac{T}{2} 。显然把第二组的数均匀分配到第一组和第三组是最优的。

代码细节

在判断 \frac{T}{2} 与 a_i 的关系的时候，使用 a[i] * 2 < T 而不是 a[i] < T / 2 可以有效兼容 T 为奇数的情况。

代码实现

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
inline int read() {
    int s = 0, x = 1; char ch = getchar();
    while (!isdigit(ch)) { if (ch == '-') x = -x; ch = getchar(); }
    while (isdigit(ch)) { s = s * 10 + ch - '0'; ch = getchar(); }
    return s * x;
}

const int MAXN = 1e5 + 10;

int n, ss;
std::pair<int, int> less[MAXN]; int lcnt;
std::pair<int, int> equal[MAXN]; int ecnt;
std::pair<int, int> greater[MAXN]; int gcnt;
int ans[MAXN];

int main() {
    int T = read();
    while (T --> 0) {
        n = read(); ss = read(); lcnt = ecnt = gcnt = 0;
        for (int i = 1; i <= n; ++i) {
            int a = read();
            if (2 * a < ss) less[++lcnt] = {a, i};
            else if (2 * a == ss) equal[++ecnt] = {a, i};
            else greater[++gcnt] = {a, i};
        }
        for (int i = 1; i <= lcnt; ++i) {
            ans[less[i].second] = 0;
        }
        for (int i = 1; i <= ecnt; ++i) {
            ans[equal[i].second] = i % 2;
        }
        for (int i = 1; i <= gcnt; ++i) {
            ans[greater[i].second] = 1;
        }
        for (int i = 1; i <= n; ++i) {
            printf("%d ", ans[i]);
        }
        puts("");
    }
    return 0;
}

C. k-Amazing Numbers

题意简述

给定一个长为 n 的序列，定义一个 k-Amazing Number 为长度为 k 的所有区间中都出现的最小的数，没有就是 -1。对于每一个 k \in [1, n] ，求出 k-Amazing Number。

解题思路

考虑每个数对 k-Amazing Number 的影响。

注意到一个数成为 k-Amazing Number 的必要条件是它被所有长度为 k 的区间包含，也就是说，我们可以求出每个数被所有长为 k 的区间包含的最小的 k，它等于这个东西：

令 t 为这个数字出现的次数， p 为这个数字出现的下标序列， p_0 = 0, p_{k + 1} = n + 1 ，那么 k_{\min} = \max_{1 \leq i \leq n+1} p_{i} - p_{i - 1}

因为这个 k 具有单调性，即如果 k 成立，那么 k + 1 一定成立，所以知道了每个数被所有长 k 区间包含的最小的 k ，就能很方便地求出每个 k 的 k-Amazing Number。

代码实现

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
inline int read() {
    int s = 0, x = 1; char ch = getchar();
    while (!isdigit(ch)) { if (ch == '-') x = -x; ch = getchar(); }
    while (isdigit(ch)) { s = s * 10 + ch - '0'; ch = getchar(); }
    return s * x;
}

const int MAXN = 3e5 + 10;

int n;
int aa[MAXN];
int ind[MAXN];
int kmin[MAXN], mink[MAXN];

int main() {
    int t = read();
    while (t --> 0) {
        n = read();
        for (int i = 1; i <= n; ++i) {
            aa[i] = read();
            mink[aa[i]] = std::max(mink[aa[i]], i - ind[aa[i]]);
            ind[aa[i]] = i;
        }
        for (int nw = 1; nw <= n; ++nw) {
            int mk = std::max(mink[nw], n - ind[nw] + 1);
            for (int j = mk; j <= n; ++j) {
                if (!kmin[j]) kmin[j] = nw;
                else break;
            }
        }
        for (int i = 1; i <= n; ++i) {
            printf("%d ", !kmin[i] ? -1 : kmin[i]);
            kmin[i] = mink[i] = ind[i] = 0;
        }
        puts("");
    }
    return 0;
}

D. Make Them Equal

题意简述

给你一个长为 n 的序列，每个数都必须保存在 0~n 之间（不一定是排列），现在定义一种操作 (i, j, k)(0\leq k \leq 10^9) 为让 a_i := a_i - i\cdot k, a_j := a_j + i\cdot k ，也就是从 a_i 里拿出 i \cdot k 放到 a_j 里。现在问你，是否存在一个操作序列满足，操作次数 \leq 3n 且操作完后所有数字都是相同的。

注意每一次操作过后 a 都是需要保持非负的。

解题思路

注意到一个性质（我也不知道该怎么注意到）：

当 a_1 足够大时，我们可以通过构造操作 (1, j, k) 来向任何数赋任何值。

有了这个性质就很好做题了。

我们考虑把所有的数字先转移到 a_1 上，然后再从 a_1 一个一个往其他的数字分配。

具体地，考虑构造形如 (i, 1, k) 的方案，实为 a_i := a_i - i \cdot k, a_1 := a_1 + i \cdot k 。可以看出，这里 k = \frac{a_i}{i} 。

但是 k 只能为整数，这意味着我们只能对满足 i \mid a_i 的数字进行转移。剩下的数字怎么办？

很简单，先把能转移的数字转移了，然后对于每一个不能转移的数字，我们先从 a_1 那里拿一点凑整，然后再转移到 a_1 里面去就可以了。

具体地，构造形如 (1, i, i - (a_i \bmod i)) 的方案，把 a_i 凑成 i 的倍数，然后再构造形如 (i, 1, \frac{a_i}{i}) 的方案把数字转移过去。

所有数字都转移过去之后，我们就可以把它转移回来了。具体地，对于 i \in [2, n] ，构造操作 (1, i, \frac{S}{n}) ，其中 S 为所有数字之和，将 S 平分成 n 份，转移 n - 1 份出去。如果 n \nmid S ，自然就无解。

前两种转移操作一共 2(n - 1) 次，第三种操作 n - 1 次，一共 3n - 3 次操作，可以通过本题。

代码实现

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
inline int read() {
    int s = 0, x = 1; char ch = getchar();
    while (!isdigit(ch)) { if (ch == '-') x = -x; ch = getchar(); }
    while (isdigit(ch)) { s = s * 10 + ch - '0'; ch = getchar(); }
    return s * x;
}

const int MAXN = 1e4 + 10;

struct Operation {
    int i, j, x; Operation(int _i = 0, int _j = 0, int _x = 0) {
        i = _i; j = _j; x = _x;
    }
} ops[MAXN * 3]; int cnt;

int n, aa[MAXN];

int main() {
    int T = read(); 
    while (T --> 0) {
        int n = read(), sum = 0;
        for (int i = 1; i <= n; ++i) {
            aa[i] = read(); sum += aa[i];
        } if (sum % n) {
            puts("-1"); continue;
        }
        for (int i = 2; i <= n; ++i) {
            // 把所有 i | a[i] 转移到 a[1] 里面
            if (aa[i] % i == 0) {
                ops[++cnt] = Operation(i, 1, (aa[i] / i));
                aa[1] += aa[i]; aa[i] = 0;
            }
        }
        for (int i = 2; i <= n; ++i) {
            if (aa[i]) {
                int need = i - aa[i] % i;
                ops[++cnt] = Operation(1, i, need);
                aa[i] += need; aa[1] -= need;
                ops[++cnt] = Operation(i, 1, (aa[i] / i));
                aa[1] += aa[i]; aa[i] = 0;
            }
        }
        int send = sum / n;
        for (int i = 2; i <= n; ++i) {
            aa[i] += send; aa[1] -= send;
            ops[++cnt] = Operation(1, i, send);
        }
        printf("%d\n", cnt);
        for (int i = 1; i <= cnt; ++i) {
            printf("%d %d %d\n", ops[i].i, ops[i].j, ops[i].x);
        }
        cnt = 0;
    }
    return 0;
}

E. XOR Inverse

题意简述

给定一个长为 n 的序列，现在让你把它们都异或上一个数 x，使得新的序列逆序对最少。输出最少的逆序对数和此种情况下最小的 x。

解题思路

序列异或的一个常用技巧就是建 01 Trie。

逆序对的本质就是二进制最高不同位使得数字产生了不同的大小，所以我们可以考虑枚举二进制位。

考虑对原序列从高二进制位向低二进制位建立 01 Trie，为了方便计算逆序对，我们在每个节点记录一下经过这个节点的数字的下标序列，因为数字是按下标顺序插入的，所以这个序列也是有序的。这样，我们可以快速计算每个二进制位产生逆序对的个数。

如果 x 当前位为 1，那么就意味着位反转，新的逆序对个数就是总对数减去原来的逆序对个数。

有了这些信息，我们就可以贪心选需不需要反转了，也就能确定最小的 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
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
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <string>
#include <vector>
#include <bitset>

#define DEBUG(x) std::cerr << #x << " = " << x << std::endl;
#define forall(G,u) for (int i_ = 0, __for_siz__ = (int) G[u].size(); i_ < __for_siz__; ++i_) 

using std::cin;
using std::cout;
using std::endl;

inline int read() {
    int s = 0, x = 1; char ch = getchar();
    while (!isdigit(ch)) { if (ch == '-') x = -x; ch = getchar(); }
    while (isdigit(ch)) { s = s * 10 + ch - '0'; ch = getchar(); }
    return s * x;
}

const int MAXN = 3e5 + 10;

struct Node {
    int next[2], dep;

    Node() {
        dep = -1; next[0] = next[1] = 0;
    }
} node[MAXN * 30]; int cnt = 1; // log2(1e9)
std::vector<int> downs[MAXN * 30];

int n, aa[MAXN];
long long int f[30 + 10][2];

void insert(int x, int ind) {
    int u = 1; 
    for (int i = 29; i >= 0; --i) {
        int now = ((x >> i) & 1);
        // printf("%d", now);
        int &next = node[u].next[now];
        if (next == 0) next = ++cnt;
        node[u].dep = i;
        downs[u].push_back(ind);
        u = next;
    }
    node[u].dep = -1;
    // puts("");
    downs[u].push_back(ind);
}

void dfs(int u = 1) {
    if (node[u].dep == -1) return;
    long long int allinvpairs = 0, allpairs = 1ll * downs[node[u].next[0]].size() * downs[node[u].next[1]].size();
    int siz = 0;
    for (auto v : downs[node[u].next[0]]) {
        while (siz < (int) downs[node[u].next[1]].size() && downs[node[u].next[1]][siz] < v) {
            ++siz;
        }
        allinvpairs += siz;
    }
    // printf("Node %d, dep %d, allpairs %d, allinvpairs %d.\n", u, node[u].dep, allpairs, allinvpairs);
    f[node[u].dep][0] += allinvpairs;
    f[node[u].dep][1] += allpairs - allinvpairs;
    dfs(node[u].next[0]); dfs(node[u].next[1]);
}

int main() {
    n = read(); long long int allinvs = 0, ans = 0;
    for (int i = 1; i <= n; ++i) {
        aa[i] = read(); insert(aa[i], i);
    } dfs(1);
    for (int i = 29; i >= 0; --i) {
        if (f[i][0] <= f[i][1]) {
            allinvs += f[i][0];
        } else {
            allinvs += f[i][1];
            ans |= (1ll << i);
        }
    }
    printf("%lld %lld\n", allinvs, ans);
    return 0;
}