Codeforces Round 636 Div.3 题解

整点活

没啥需要分析的，具体的话官方题解吧。

1343A Candies

A.cpp

#include <bits/stdc++.h>
using namespace std;

int main() {
    int t;
    cin >> t;
    while (t--) {
        int n, c = 1;
        cin >> n;
        for (int i = 1; i < 31; ++i) {
            c |= 1 << i;
            if (n % c == 0) {
                cout << n / c << endl;
                break;
            }
        }
    }
    return 0;
}

1343B Balanced Array

B.cpp

#include <bits/stdc++.h>
using namespace std;

int main() {
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        if (n >> 1 & 1) {
            cout << "NO" << endl;
            continue;
        }
        cout << "YES" << endl;
        for (int i = 1; i <= n / 2; ++i) {
            cout << i * 2 << ' ';
        }
        for (int i = 0, t = 1; i < n / 2; ++i) {
            cout << t << ' ';
            t += 2;
            if (i + 1 == n / 4)
                t += 2;
        }
        cout << endl;
    }
    return 0;
}

1343C Alternating Subsequence

C.cpp

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int main() {
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        vector<ll> a(n);
        for (ll &i : a) cin >> i;
        ll sum = 0, la = a[0];
        for (int i = 1; i < n; ++i) {
            if (a[i] * la < 0) {
                sum += la;
                la = a[i];
            }
            la = max(la, a[i]);
        }
        sum += la;
        cout << sum << endl;
    }
    return 0;
}

1343D Constant Palindrome Sum

这道题主要是想到对于一对数$a,b,(a\leq b)$，若 $x\leq a$，需要两次操作，若$a\le x\le b+k$，需要1次操作，其中 $x = a + b$ 时不需要操作，若 $b+k\le x\le 2k$，也需要两次操作，因此差分后扫描线取最小值。

D.cpp

#include <bits/stdc++.h>
using namespace std;

int main() {
    int T;
    cin >> T;
    while (T--) {
        int n, k;
        cin >> n >> k;
        vector<int> a(n), b(2 * k);
        for (int &i : a) cin >> i, --i;
        for (int i = 0; i < n / 2; ++i) {
            int s = a[i] + a[n - i - 1];
            int l = min(a[i], a[n - i - 1]);
            int r = max(a[i], a[n - i - 1]) + k;
            b[0] += 2;
            --b[l], --b[s];
            ++b[s + 1], ++b[r];
        }
        int ans = b[0];
        for (int i = 1; i < 2 * k; ++i) {
            b[i] += b[i - 1];
            ans = min(ans, b[i]);
        }
        cout << ans << endl;
    }
    return 0;
}

1343E Weights Distributing

这道题是枚举一个点$t$，我们的路径为$a\to t,t\to b,b\to t,t\to b$，那么走两遍的边和走一遍的边就确定了数目，取最小值即为答案。

F.cpp

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
const ll INF64 = 0x3f3f3f3f3f3f3f3f;

int main() {
    int T;
    cin >> T;
    while (T--) {
        int n, m, a, b, c;
        cin >> n >> m >> a >> b >> c;
        vector<vi> g(n + 1);
        vector<vi> d(3, vi(n + 1, -1));
        vector<ll> p(m + 1);
        for (int i = 1; i <= m; ++i)
            cin >> p[i];
        sort(p.begin(), p.begin() + m + 1);
        for (int i = 1; i <= m; ++i)
            p[i] += p[i - 1];
        for (int i = 0, u, v; i < m; ++i) {
            cin >> u >> v;
            g[u].emplace_back(v);
            g[v].emplace_back(u);
        }
        auto bfs = [&](int s, int i) {
            queue<int> Q;
            Q.emplace(s);
            d[i][s] = 0;
            while (!Q.empty()) {
                int u = Q.front();
                Q.pop();
                for (int v : g[u]) {
                    if (d[i][v] == -1) {
                        d[i][v] = d[i][u] + 1;
                        Q.emplace(v);
                    }
                }
            }
        };
        bfs(a, 0);
        bfs(b, 1);
        bfs(c, 2);
        ll ans = INF64;
        for (int i = 1; i <= n; ++i) {
            if (d[2][i] + d[1][i] + d[0][i] > m) continue;
            ll tt = p[d[1][i]] + p[d[2][i] + d[1][i] + d[0][i]];
            ans = min(ans, tt);
        }
        cout << ans << endl;
    }
    return 0;
}

1343F Restore the Permutation by Sorted Segments

这个题主要是暴力$check$和模拟吧，思路见。

F.cpp

#include <bits/stdc++.h>
using namespace std;

int main() {
    auto cmp = [](set<int> &a, set<int> &b) { return a.size() < b.size(); };

    int T;
    cin >> T;
    while (T--) {
        int n;
        cin >> n;
        vector<int> ans(n), tp;
        vector<set<int>> s, ss(n + 1);
        for (int i = 1, k, t; i < n; ++i) {
            cin >> k;
            for (int j = 0; j < k; ++j) {
                cin >> t;
                ss[i].emplace(t);
                if (k == 2) tp.emplace_back(t);
            }
        }
        sort(ss.begin(), ss.begin() + n, cmp);
        while (1) {
            s = ss;
            ans[0] = tp.back();
            tp.pop_back();
            for (int i = 1; i < n; ++i) {
                if (s[i].count(ans[0]))
                    s[i].erase(ans[0]);
            }
            sort(s.begin(), s.begin() + n, cmp);
            for (int i = 1; i < n; ++i) {
                ans[i] = *s[i].begin();
                for (int j = 1; j < n; ++j) {
                    if (s[j].count(ans[i]))
                        s[j].erase(ans[i]);
                }
                sort(s.begin(), s.begin() + n, cmp);
            }
            int ff = 1;
            for (int i = 1; i < n; ++i) {
                set<int> tt;
                int f = 0;
                tt.emplace(ans[i]);
                for (int j = i - 1; j >= 0; --j) {
                    tt.emplace(ans[j]);
                    if (find(ss.begin(), ss.end(), tt) != ss.end()) {
                        f = 1;
                        break;
                    }
                }
                if (!f) {
                    ff = 0;
                    break;
                }
            }
            if (ff) break;
        }
        for (int i = 0; i < n; ++i)
            cout << ans[i] << ' ';
        cout << endl;
    }
    return 0;
}