Codeforces Round #615 (Div. 3)

第一次 CF 賽中破台，排名 +178，總算 1700 了。 pD 稍微想了一下子，pE 實作上卡了很久，有些邊界問題沒考慮清楚。pF 想了一下子才發現很好寫，但忘了考慮一直鏈的情況，所以 WA 了一次。

A. Collecting Coins

 1#include<bits/stdc++.h>
 2using namespace std;
 3typedef long long LL;
 4int main() {
 5    ios::sync_with_stdio(0), cin.tie(0);
 6    int t; cin >> t;
 7    while (t--) {
 8        LL a, b, c, n;
 9        cin >> a >> b >> c >> n;
10        LL sum = n + a + b + c;
11        if (sum % 3) {
12            cout << "NO\n";
13            continue;
14        }
15        sum /= 3;
16        if (sum < a || sum < b || sum < c) {
17            cout << "NO\n";
18            continue;
19        }
20        cout << "YES\n";
21    }   
22    return 0;
23}

B. Collecting Coins

 1#include<bits/stdc++.h>
 2using namespace std;
 3typedef pair<int, int> pii;
 4#define x first
 5#define y second
 6int main() {
 7    ios::sync_with_stdio(0), cin.tie(0);
 8    int t; cin >> t;
 9    while (t--) {
10        int n; cin >> n;
11        vector<pii> p(n);
12        for (int i = 0; i < n; i++) cin >> p[i].x >> p[i].y;
13        sort(p.begin(),p.end());
14        bool success = true;
15        for (int i = 1; i < n; i++)
16            if(p[i].x < p[i-1].x || p[i].y < p[i-1].y)
17                success = false;
18        if(!success) {
19            cout << "NO\n";
20            continue;
21        }
22        cout << "YES\n";
23        int xx = 0, yy = 0;
24        for(int i = 0; i < n; i++) {
25            while (xx != p[i].x) cout << "R", xx++;
26            while (yy != p[i].y) cout << "U", yy++;
27        }
28        cout << "\n";
29    }
30    return 0;
31}

C. Product of Three Numbers

 1#include<bits/stdc++.h>
 2using namespace std;
 3int main() {
 4    ios::sync_with_stdio(0), cin.tie(0);
 5    int t; cin >> t;
 6    while (t--) {
 7        int n; cin >> n;
 8        vector<int> ans;
 9        for (int i = 2; i * i <= n && ans.size() < 2; i++) {
10            if (n % i) continue;
11            ans.push_back(i);
12            n /= i;
13        }
14        if (ans.size() != 2 || n <= ans.back()) {
15            cout << "NO\n";
16            continue;
17        }
18        cout << "YES\n";
19        ans.push_back(n);
20        for (int i = 0; i < 3; i++)
21            cout << ans[i] << " \n"[i==2];
22    }
23    return 0;
24}

D. MEX maximizing

每次新增一個數字到序列裡，可對序列每個數字任意加減x的整數倍，問操作完後，序列中所缺的最小正整數最大是多少？

一開始可以確定答案不可能超過當前 query 的次數，且答案會單調遞增。可以知道 y[i] 可以加減 x 的整數倍，故可以直接 y[i] 紀錄 mod x 出現幾次，然後將答案往後爬。複雜度 O(q)。

 1#include<bits/stdc++.h>
 2using namespace std;
 3#define MAX 800005
 4int main() {
 5    ios::sync_with_stdio(0), cin.tie(0);
 6    int q, x; cin >> q >> x;
 7    int ans = 0;
 8    int cnt[MAX] = {};
 9    for (int i = 0; i < q; i++) {
10        int a; cin >> a;
11        cnt[a % x]++;
12        while (cnt[ans % x]){
13            cnt[ans % x]--;
14            ans++;
15        }
16        cout << ans << "\n";
17    }
18    return 0;
19}

E. Obtain a Permutation

只需要將每個 column 單獨計算，再將所有結果相加即可。

單一個 column，對每一格去算到達正確位置需要幾次操作，用個陣列去計算，轉 k 次能讓多少個格子到達正確位置。總複雜度 O(mn)。

 1#include<bits/stdc++.h>
 2using namespace std;
 3#define MAX 200005
 4int cnt[MAX] = {};
 5int main() {
 6    ios::sync_with_stdio(0), cin.tie(0);
 7    int n, m; cin >> n >> m;
 8    vector<vector<int>> a(n, vector<int>(m));
 9    for (int i = 0; i < n; i++)
10        for (int j = 0; j < m; j++)
11            cin >> a[i][j];
12    int sum = 0;
13    for (int j = 0; j < m; j++) {
14        for (int i = 0; i < n; i++) {
15            if (a[i][j] <= n * m && (j+1) % m == a[i][j] % m) {
16                int ii = (a[i][j] - 1) / m;
17                cnt[(i + n - ii) % n]++;
18            }
19        }
20        int ans = MAX;
21        for (int i = 0; i < n; i++) {
22            ans = min(ans, n - cnt[i] + i);
23            cnt[i] = 0;
24        }
25        sum += ans;
26    }
27    cout << sum << "\n";
28    return 0;
29}

F. Three Paths on a Tree

找出相異三點，使得兩兩之間的路徑聯集起來邊數最多。

若樹為一直鏈（竹子），則答案為兩端點，和中間任一點。其餘的情況，可以確定答案必有一點落在直徑上，且三點皆為葉子。故先做兩次 BFS 找出直徑，再做樹 DP 得到答案。複雜度 O(n)。

 1#include<bits/stdc++.h>
 2using namespace std;
 3#define maxn 200005
 4vector<int> v[maxn];
 5bool visit[maxn] = {1,1};
 6typedef pair<int, int> pii;
 7int ans = 0;
 8int out[3];
 9pii dfs(int u, int dep, int scr) {
10    visit[u] = true;
11    int mx1 = 0, mx2 = 0, a1 = u, a2 = u;
12    for (int uu : v[u]) {
13        if(visit[uu]) continue;
14        pii d = dfs(uu, dep + 1, scr);
15        if (d.first >= mx1)
16            mx2 = mx1, a2 = a1, mx1 = d.first, a1 = d.second;
17        else if (d.first > mx2)
18            mx2 = d.first, a2 = d.second;
19    }
20    if (mx1 + mx2 + dep >= ans) {
21        ans = mx1 + mx2 + dep;
22        out[0] = scr, out[1] = a1, out[2] = a2;
23    }
24    return pii(mx1 + 1, a1);
25}
26int main() {
27    ios::sync_with_stdio(0), cin.tie(0);
28    int n; cin >> n;
29    for (int i = 1; i < n; i++) {
30        int a, b; cin >> a >> b;
31        v[a].push_back(b), v[b].push_back(a);
32    }
33    queue<int> q;
34    int a = 1;
35    q.push(1);
36    while (!q.empty()) {
37        int u = q.front(); q.pop();
38        a = u;
39        for(int uu : v[u])
40            if (!visit[uu])
41                visit[uu] = true, q.push(uu);
42    }
43    int b = a;
44    memset(visit, 0, sizeof(visit));
45    q.push(a);
46    while(!q.empty()) {
47        int u = q.front(); q.pop();
48        b = u;
49        for (int uu : v[u])
50            if (!visit[uu])
51                visit[uu] = true, q.push(uu);
52    }
53    memset(visit, 0, sizeof(visit));
54    dfs(a, 0, a);
55    memset(visit, 0, sizeof(visit));
56    dfs(b, 0, b);
57    cout << ans << "\n";
58    if (out[1] == out[2] || out[0] == out[2]) {
59        for (int i = 1; i <= n; i++)
60            if (i != out[0] && i != out[1]){
61                out[2] = i;
62                break;
63            }
64    }
65    for (int i = 0; i < 3; i++)
66        cout << out[i] << " \n"[i == 2];
67    return 0;
68}