小花生

study & life record.

Codeforces Round 947 (Div.1 + Div.2)

发表于 分类于 ，

5月25日 Codeforces 实战记录。（1378 -> 1468）

AC数3/9。
比赛跳转：Codeforces Round 947 (Div. 1 + Div. 2)

题解

A. Bazoka and Mocha’s Array

分析：题意即循环处理，存在单调不减序列，重复序列两次计数最长单调不减序列长度即可。

完整代码：

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
#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 n = read();
        vector<int> a(n);
        for(int i = 0; i < n; i++) a[i] = read();
        int cnt = 0, last = 0; bool flag = 0;
        for(int i = 0; i < 2 * n; i++){
            if(last <= a[i % n]){
                cnt ++ ;
                last = a[i % n];
                if(cnt == n){
                    flag = 1; break;
                }
            }
            else last = a[i % n], cnt = 1;
        }
        if(flag) cout << "Yes\n";
        else cout << "No\n";
    }
    return 0;
}

B. 378QAQ and Mocha’s Array

分析：找出序列中最小且互不整除的两数作为所有元素的除数，判断能否整除剩余所有元素即可。

完整代码：

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
#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 n = read();
        vector<int>a(n);
        for(int i = 0; i < n; i++) a[i] = read();
        sort(a.begin(), a.end());
        int x = a[0], y; bool flag = 0;
        int pos = 1;
        for(; pos < n; pos++){
            if(a[pos] % x) {
                y = a[pos];
                break;
            }
            if(pos == n - 1) flag = 1;
        }
        
        if(flag) {
            cout << "Yes\n";
            continue;
        }
        
        flag = 1;
        for(int i = pos + 1; i < n; i++){
            if(a[i] % x && a[i] % y) {
                flag = 0;
                break;
            } 
        }
        if(flag) {
            cout << "Yes\n";
            continue;
        }
        cout << "No\n";
        
    }
    return 0;
}

C. Chamo and Mocha’s Array

分析：选取长度为 2 的 array 只能取到较小值，不考虑；当选取长度大于 3 时，都可以直接选取长度为 3 的 array 实现，故寻找每个长度为 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
#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 n = read();
        vector<int>a(n);
        
        for(int i = 0; i < n; i++) a[i] = read();
        
        if(n == 2){
            cout << min(a[0], a[1]) << '\n';
            continue;
        }
        
        int mx = 0;
        for(int i = 0; i < n - 2; i++){
            int arr[] = {a[i], a[i + 1], a[i + 2]};
            sort(arr, arr + 3); 
            mx = max(mx, arr[1]);
        }
        cout << mx << '\n';
    }
    return 0;
}

D. Paint the Tree

分析：先让 A，B 走到同一点，利用 bfs 扫描，求出两点距离及中点坐标。该阶段步数为 $\frac{dist(A, B) + 1}{2}$ 。走到同一点后，要遍历全图所有点，即，除了最长边，每条边遍历两遍，该阶段步数为 $2\times(n-1) - maxlen$。

完整代码：

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

const int N = 2e5 + 10;
vector<int>g[N];
int mid; bool vis[N]; int path[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 bfs(int a, int b){
    memset(vis, 0, sizeof vis);
    memset(path, 0, sizeof path);
    queue<PII>q;
    q.emplace(a, 0);
    
    while(1){
        auto u = q.front();
        q.pop();
        vis[u.first] = 1;
        
        if(u.first == b){
            mid = b;
            for(int i = 0; i < u.second + 1 >> 1; i++)
                mid = path[mid];
            return u.second;
        }
        
        for(auto &v : g[u.first]){
            if(vis[v]) continue;
            path[v] = u.first;
            q.emplace(v, u.second + 1);
        }
    }
}

int bfss(int u){
    memset(vis, 0, sizeof vis);
    queue<PII>q;
    q.emplace(u, 0);
    int mx = 0;
    while(!q.empty()){
        auto u = q.front();
        q.pop();
        vis[u.first] = 1;
        mx = max(mx, u.second);
        
        for(auto &v : g[u.first]){
            if(vis[v]) continue;
            q.emplace(v, u.second + 1);
        }
    }
    return mx;
}

int main() {
    int t = read();
    while (t--) {
        int n = read();
        for(int i = 1; i <= n; i++) g[i].clear();
        int a = read(), b = read();
        for(int i = 1; i <= n - 1; i++){
            int x = read(), y = read();
            g[x].emplace_back(y), g[y].emplace_back(x);
        }
        
        int stp = bfs(a, b) + 1 >> 1;
        int len = bfss(mid);
        cout << stp + 2 * (n - 1) - len << '\n';
    }
    return 0;
}