小花生

study & life record.

Codeforces Round 945 (Div.2)

发表于 分类于 ，

5月17日 Codeforces 实战记录。（656 -> 1156）

第二次打Codeforces，挑战div.2惨遭被虐，AC数2/6。
比赛跳转：Codeforces Round 945 (Div. 2)

题解

A. Chess For Three

题意：三人两两随机比赛，win 2分，lose 0分，draw 各1分。
给出三人最终得分，输出 draw 最大场数。

分析：不难发现最大场次为min(p1 + p2, p1 + p2 + p3 >> 1)
（draw 场次仅受 p1+p2 与总比赛数的约束）

完整代码：

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
#include<bits/stdc++.h>
using namespace std;

inline int read(){
    int x = 0, f = 1; char ch = getchar();
    while(ch < '0' || ch > '9') { if(ch == '-') f = -1; ch = getchar(); }
    while(ch >= '0' && ch <= '9') { x = x * 10 + ch - 48; ch = getchar(); }
    return x * f;
}

int main(){
    int t = read();
    while(t--){
        int p1 = read(), p2 = read(), p3 = read();
        int sum = p1 + p2 + p3;
        
        if(sum & 1){
            cout << -1 << '\n';
            continue;
        }
        
        cout << min(sum >> 1, p1 + p2) << '\n';
    } 

    return 0;
}

B. Cat, Fox and the Lonely Array

题意：定义 loneliness 为保证所有长度为 k 的连续子序列内所有元素按位或运算结果相等的最小 k 值。输出 loneliness 值。

分析：发现，如果 k 满足条件，则 k+1 一定也满足条件，即具有决策单调性，采用二分答案。对于一个尝试的 k 值，用 cnt 数组记录每一位上出现 1 的次数，遍历一遍序列，如果发现按位或结果出现变化（即 cnt 数组中某一位由1变0或由0变1），check 失败，否则 check 成功。该方案时间复杂度为 $O(n\ logn\ logA)$。

完整代码：

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
#include<bits/stdc++.h>
using namespace std;

inline int read() {
    int x = 0, f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
    while (ch >= '0' && ch <= '9') { x = x * 10 + ch - 48; ch = getchar(); }
    return x * f;
}

bool check(vector<int>& a, int mid, int n) {
    vector<int> cnt(25, 0);
    for (int i = 0; i < mid; i++) {
        int tmp = a[i];
        for (int k = 1; tmp; k++) {
            if (tmp & 1) cnt[k]++;
            tmp >>= 1;
        }
    }
    for (int i = mid; i < n; i++) {
        int tmp = a[i];
        for (int k = 1; tmp; k++) {
            if (tmp & 1) {
                if (cnt[k] == 0) return 0;
                cnt[k]++;
            }
            tmp >>= 1;
        }
        tmp = a[i - mid];
        for (int k = 1; tmp; k++) {
            if (tmp & 1 && --cnt[k] == 0) return 0;
            tmp >>= 1;
        }
    }
    return 1;
}

int main() {
    int t = read();
    while (t--) {
        int n = read();
        vector<int>a(n);
        for (int i = 0; i < n; i++) a[i] = read();

        int l = 1, r = n;
        while (l < r) {
            int mid = l + r >> 1;
            if (check(a, mid, n)) r = mid;
            else l = mid + 1;
        }
        cout << l << '\n';
    }
    return 0;
} // 265ms

补充解法

官方还给出了一个 $O(n\ logA)$ 的做法：

逐位计算 loneliness 后求其最大值，实现如下：

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;

const int N = 1e5 + 10;

inline int read() {
    int x = 0, f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
    while (ch >= '0' && ch <= '9') { x = x * 10 + ch - 48; ch = getchar(); }
    return x * f;
}

int main() {
    int t = read();
    while (t--) {
        int n = read();
        vector<vector<bool>> bit(n, vector<bool>(25, 0));
        for (int i = 0; i < n; i++) {
            int a = read();
            for (int k = 1; a; k++) {
                bit[i][k] = a & 1;
                a >>= 1;
            }
        }

        int lonely = 1;
        for (int k = 1; k <= 20; k++) {
            int mx = 1, zeros = 0;
            for (int i = 0; i < n; i++) {
                if (bit[i][k]) {
                    mx = max(mx, zeros + 1);
                    zeros = 0;
                }
                else zeros++;
            }
            if (zeros != n)
                mx = max(mx, zeros + 1);
            lonely = max(lonely, mx);
        }
        cout << lonely << '\n';
    }
    return 0;
} // 93ms

C. Cat, Fox and Double Maximum

题意：给定长度为偶数 n 的一个全排列 p，试找出一个全排列 q，使得新数列 a = p + q 中，局部最大值（严格大于左右两数）的个数最多。

分析：这样的数最多有 $\frac{n-2}{2}$ 个，于是尝试构造，使局部最大值个数等于 $\frac{n-2}{2}$ 。
构造如下：如果 n 在偶数位上，我们将$1, 2, \dots, \frac n2$ 放在 q 的奇数位上（对应 p 从大到小），将 $\frac n2,\frac n2 + 1,\dots,n$ 放在 q 的 偶数位上（对应 p 从大到小），这样，不难发现，所有奇数位上的数均 $\leq n$，所有偶数位上的数均 $\geq n +1$，如此便满足题设；而若 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
#include<bits/stdc++.h>
using namespace std;
typedef pair<int, int> PII;

const int N = 1e5 + 10;
int p[N], q[N];

inline int read(){
    int x = 0, f = 1; char ch = getchar();
    while(ch < '0' || ch > '9') { if(ch == '-') f = -1; ch = getchar(); }
    while(ch >= '0' && ch <= '9') { x = x * 10 + ch - 48; ch = getchar(); }
    return x * f;
}

int main(){
    int t = read();
    while(t--){
        int n = read();
        bool turn = false;
        for(int i = 1; i <= n; i++){
            p[i] = read();
            if(p[i] == n && i & 1) turn = true;
        }
        if(turn) 
            reverse(p + 1, p + 1 + n);
        
        priority_queue<PII> odd, even;
        for(int i = 1; i <= n; i += 2)
            odd.emplace(p[i], i);
        for(int i = 2; i <= n; i += 2)
            even.emplace(p[i], i);
            
        int give = 1;
        while(!odd.empty()){
            int u = odd.top().second;
            odd.pop();
            q[u] = give++;
        }
        while(!even.empty()){
            int u = even.top().second;
            even.pop();
            q[u] = give++;
        }	
        
        if(turn)
            reverse(q + 1, q + 1 + n);
        for(int i = 1; i <= n; i++)
            cout << q[i] << ' ';
        puts("");
    }
    return 0;
}