小花生

study & life record.

Codeforces Round 956 (Div.2)

发表于 分类于 ，

7月7日 Codeforces 实战记录。（1434 -> 1461）

AC数3/7。
比赛跳转：Codeforces Round 956 (Div. 2)

题解

A. Array Divisibility

分析：a[i] = i 显然满足题设。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include<bits/stdc++.h>
#define int long long
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;
}

void solve(){
    int n = read();
    for(int i = 1; i <= n; i++){
        cout << i << ' ';
    }
    puts("");
}

signed main(){
    int t = read();
    while(t--) solve();
    return 0;
}

B. Corner Twist

分析：操作前后的不变量是：每一行每一列的和mod 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
56
#include<bits/stdc++.h>
#define int long long
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;
}

void solve(){
    int n = read(), m = read();
    vector<vector<int>> a(n, vector<int>(m)), b(n, vector<int>(m));
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            char ch; cin >> ch;
            a[i][j] = ch - '0';
        }
    }
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            char ch; cin >> ch;
            b[i][j] = ch - '0';
        }
    }
    int ok = 1;
    for(int i = 0; i < n; i++){
        int suma = 0, sumb = 0;
        for(int j = 0; j < m; j++){
            suma += a[i][j];
            sumb += b[i][j];
        }
        if(suma % 3 != sumb % 3){
            ok = 0; break;
        }
    }
    for(int j = 0; j < m; j++){
        int suma = 0, sumb = 0;
        for(int i = 0; i < n; i++){
            suma += a[i][j];
            sumb += b[i][j];
        }
        if(suma % 3 != sumb % 3){
            ok = 0; break;
        }
    }
    if(ok) cout << "Yes" << '\n';
    else cout << "No" << '\n';	
}

signed main(){
    int t = read();
    while(t--) solve();
    return 0;
}

C. Have Your Cake and Eat It Too

分析：只有6种排列情况。依次贪心尝试即可，每次尝试都是 O(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
56
57
58
59
60
61
#include<bits/stdc++.h>
#define int long long
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;
}

void solve() {
    int n = read();
    vector<vector<int>> v(3, vector<int>(n)); 
    for(int i = 0; i < 3; i++){
        for(int j = 0; j < n; j++){
            v[i][j] = read();
        }
    }
    
    int tot = 0;
    for(int i = 0; i < n; i++) tot += v[0][i];
    tot = (tot + 2) / 3;
    
    vector<int> perm = {0, 1, 2};
    vector<int> l(3), r(3);
    
    
    do{
        int ok = 0;
        int cur = 0;
        
        for(int i = 0; i < 3; i++){
            l[perm[i]] = cur + 1;
            int sum = 0;
            while(cur < n){
                sum += v[perm[i]][cur++];
                if(sum >= tot){
                    ok++;
                    r[perm[i]] = cur;
                    break;
                }
            }
        }
        
        if(ok == 3){
            for(int i = 0; i < 3; i++){
                cout << l[i] << " " << r[i] << " \n"[i == 2];
            }
            return;
        }

    }while(next_permutation(perm.begin(), perm.end()));
    cout << -1 << '\n';
}

signed main() {
    int t = read();
    while (t--) solve();
    return 0;
}

D. Swap Dilemma

分析：可以将每一次操作等效转化到同一个数组上，而这种操作前后、逆序对的数量改变偶数次（必要条件）且充分条件是可证明的。于是判断两序列逆序对的数量之差是否为偶数即可。

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
#include<bits/stdc++.h>
#define int long long
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;
}

const int N = 1e5 + 10;
int n; vector<int> tmp(N);

int merge_sort(vector<int> &a, int l, int r){
    if(l >= r) return 0;
    
    int mid = l + r >> 1;
    int ans = merge_sort(a, l, mid) + merge_sort(a, mid + 1, r);
    
    int k = 0, i = l, j = mid + 1;
    while(i <= mid && j <= r){
        if(a[i] <= a[j]) tmp[k++] = a[i++];
        else {
            tmp[k++] = a[j++];
            ans += mid - i + 1;
        }
    }
    while(i <= mid) tmp[k++] = a[i++];
    while(j <= r) tmp[k++] = a[j++];
    
    for(int i = l, j = 0; i <= r; i++, j++)
        a[i] = tmp[j];
        
    return ans;
}

void solve(){
    n = read(); 
    vector<int> a(n), b(n);
    for(int i = 0; i < n; i++){
        a[i] = read();
    }
    for(int i = 0; i < n; i++){
        b[i] = read();
    }

    bool flag = (merge_sort(a, 0, n - 1) + merge_sort(b, 0, n - 1)) % 2 == 0;
    sort(a.begin(), a.end());
    sort(b.begin(), b.end());
    if(a != b) flag = 0;
    
    if(flag) cout << "Yes" << '\n';
    else cout << "No" << '\n';
}

signed main(){
    int t = read();
    while(t--) solve();
    return 0;
}