「题解」Codeforces Round 1045 (Div. 2)

每天一场 Div. 2 是不是太少了。

比赛链接

A - Painting With Two Colors

给定三个正整数 $n, a, b$，要求先涂 $a$ 个连续红色，然后再涂 $b$ 个连续蓝色。问最后的的图形是否对称。

显然分奇偶考虑，如果 $n$ 是偶数则 $b$ 必须是偶数，否则 $b$ 必须是奇数。若 $a \le b$，则我们可以不用考虑 $a$，否则 $a$ 的奇偶性必须和 $b$ 一致。

void solve() {
    int n, a, b;
    cin >> n >> a >> b;
    if (n % 2 == 0) {
        if (b % 2 != 0) {
            cout << "NO\n";
        } else if (a <= b) {
            cout << "YES\n";
        } else if ((a - b) % 2 == 0) {
            cout << "YES\n";
        } else {
            cout << "NO\n";
        }
    } else {
        if (b % 2 == 0) {
            cout << "NO\n";
        } else if (a <= b) {
            cout << "YES\n";
        } else if ((a - b) % 2 == 0) {
            cout << "YES\n";
        } else {
            cout << "NO\n";
        }
    }
}

B - Add 0 or K

给定一个有 $n$ 个元素的数组 $a$ 和一个正整数 $k$，对于每一个元素 $a_i$ 可以选择加上 $m \times k$，$m$ 是非负整数。问若干次操作后使得 $\gcd(a_1,a_2,\dots,a_n) \gt 1$ 时，$a$ 数组的值。

我们不难想到，在模 $k+1$ 意义下，$x+k \equiv x-1 \pmod{k+1}$，所以我们只要对每一个元素操作 $a_i \bmod (k + 1)$ 次就行。

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

#define int long long
void solve() {
    int n, k;
    cin >> n >> k;
    vector<int> a(n);
    for (int i = 0; i < n; i++)
        cin >> a[i];
    if (n == 1) {
        cout << k + a[0] << "\n";
        return;
    }
    if (k % 2 == 1) {
        for (int i = 0; i < n; i++) {
            if (a[i] % 2 == 1)
                a[i] += k;
            cout << a[i] << " \n"[i == n - 1];
        }
        return;
    }
    for (int i = 0; i < n; i++) {
        a[i] += k * (a[i] % (k + 1));
    }
    for (int i = 0; i < n; i++) {
        cout << a[i] << " \n"[i == n - 1];
    }
}

signed main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    int T = 1;
    cin >> T;
    while (T--)
        solve();
    return 0;
}

C - Even Larger

#include <bits/stdc++.h>

using namespace std;

#define int long long
void solve() {
    int n;
    cin >> n;
    vector<int> a(n + 10);
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    int ans = 0;
    for (int i = 2; i <= n; i += 2) {
        if (a[i] < a[i - 1]) {
            ans += a[i - 1] - a[i];
            a[i - 1] = a[i];
        }
        if (a[i] < a[i + 1]) {
            ans += a[i + 1] - a[i];
            a[i + 1] = a[i];
        }
        if (a[i] < a[i + 1] + a[i - 1]) {
            ans += a[i + 1] + a[i - 1] - a[i];
            a[i + 1] -= a[i + 1] + a[i - 1] - a[i];
        }
    }
    cout << ans << "\n";
}

signed main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    int T = 1;
    cin >> T;
    while (T--)
        solve();
    return 0;
}

D - Sliding Tree

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

void solve() {
    int n;
    cin >> n;
    vector adj(n + 1, vector<int>{});
    for (int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;
        adj[u].emplace_back(v);
        adj[v].emplace_back(u);
    }
    vector<int> d, p;
    auto bfs = [&](int s) -> int {
        d.assign(n + 1, -1);
        p.assign(n + 1, -1);
        queue<int> q;
        q.push(s);
        d[s] = 0;

        while (not q.empty()) {
            int u = q.front();
            q.pop();
            for (auto v : adj[u]) {
                if (d[v] == -1) {
                    d[v] = d[u] + 1;
                    p[v] = u;
                    q.push(v);
                }
            }
        }
        return max_element(d.begin(), d.end()) - d.begin();
    };
    int s = bfs(1);
    int t = bfs(s);

    if (d[t] == n - 1) {
        cout << "-1\n";
        return;
    }

    int u = t;
    int fa = -1;
    while (adj[u].size() <= 2) {
        fa = u;
        u = p[u];
    }

    for (auto v : adj[u]) {
        if (v != fa and v != p[u]) {
            cout << p[u] << " " << u << " " << v << "\n";
            return;
        }
    }
}

signed main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    int T = 1;
    cin >> T;
    while (T--)
        solve();
    return 0;
}