链接：https://codeforces.com/contest/2134

A. Painting With Two Colors

算法：

    找规律。

思路：

    不难发现必须满足以下条件之一：

• \(b = n\): 蓝色直接把格子涂满。
• \(n, a, b\) 同奇偶。
• \(n, b\) 同奇偶且 \(a \leq b\)，蓝色直接覆盖红色。

关键代码：

void solve()
{
    ll n, a, b;
    cin >> n >> a >> b;

    if (b == n || ((n & 1) == (b & 1) && (a <= b || (n & 1) == (a & 1))))
        cout << "YES" << endl;
    else
        cout << "NO" << endl;
}

B. Add 0 or K

算法：

    数论。

思路：

    考虑将所有的元素都变成 \(k + 1\) 的倍数。

    通过恒等式：

\(k – (-1) = k + 1 \;\Rightarrow\; k – (-1) \equiv 0 \pmod{k+1} \;\Rightarrow\; k \equiv -1 \pmod{k+1}\)

    可发现每次对 \(x\) 加 \(k\) 相当于 \(-1\)，既：

\(x + k \equiv x – 1 \pmod{k+1}\)

    只需对每个 \(a_i\) 加上 \(a_i \text{ % } (k + 1)\) 个 \(k\) 即可。

关键代码：

void solve()
{
    ll n, k;
    cin >> n >> k;
    vector<ll> a(n);
    for (int i = 0; i < n; i++)
        cin >> a[i];

    ll t = k + 1;
    for (int i = 0; i < n; i++)
    {
        ll w = a[i] % t;
        a[i] += w * k;

        cout << a[i] << ' ';
    }

    cout << endl;
}

C. Even Larger

算法：

    贪心。

思路：

    很典的一个贪心不过多赘述。

关键代码：

void solve()
{
    int n;
    cin >> n;
    vector<ll> a(n + 10, 0);
    for (int i = 1; i <= n; ++i)
        cin >> a[i];

    ll ans = 0;
    for (int i = 2; i <= n; i += 2)
    {
        if (a[i] < a[i - 1] + a[i + 1])
        {
            ans += a[i - 1] + a[i + 1] - a[i];

            ll t = a[i - 1] + a[i + 1] - a[i];
            ll w = max(0ll, a[i + 1] - t);
            a[i + 1] = w;
            t -= w;

            if (t)
                a[i - 1] -= t;
        }
    }

    cout << ans << endl;
}

D. Sliding Tree

算法：

    构造，树的直径。

思路：

    滑动操作就是将一个节点 \(a\), 选择两个邻居 \(b、c\), 将除 \(b\) 以外的邻居都给 \(c\)。

    结论: 每次滑动操作至多让树的直径加一。

    设 \(l\) 为树的直径，要将树变化为路径图（直径为 \(n – 1\)），显然最少需要 \((n – 1) – l\) 次。

    由于只需输出第一对 \((a, b, c)\)，所以只需做一下操作即可：

    先求出树的直径以及直径中每个点的父节点，再将直径中的点都标记上，最后答案就为 \(a b c\)

• \(b\): 直径上的一点
• \(a\): \(b\) 的父节点且在直径上
• \(c\): 直径外的一点且与 \(b\) 相连

关键代码：

void solve()
{
    int n;
    cin >> n;
    vector<vector<int>> g(n + 1);
    for (int i = 0; i < n - 1; ++i)
    {
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }

    vector<int> dist(n + 1, 0);
    vector<int> p(n + 1, 0);
    auto dfs = [&](auto &&self, int u, int f) -> void
    {
        p[u] = f;
        for (auto v : g[u])
        {
            if (v != f)
            {
                dist[v] = dist[u] + 1;
                self(self, v, u);
            }
        }
    };

    int x = 1;
    dfs(dfs, x, 0);

    x = max_element(dist.begin() + 1, dist.end()) - dist.begin();

    ranges::fill(dist, 0);
    dfs(dfs, x, 0);

    x = max_element(dist.begin() + 1, dist.end()) - dist.begin();

    if (dist[x] == n - 1)
    {
        cout << -1 << endl;
        return;
    }

    vector<int> st(n + 1, 0);
    int now = x;
    while (now)
    {
        st[now] = 1;
        now = p[now];
    }

    int a = 0, b = 0, c = 0;
    for (int u = 1; u <= n; ++u)
    {
        for (auto v : g[u])
        {
            if (st[u] && !st[v])
            {
                a = p[u], b = u, c = v;
                break;
            }
        }

        if (a)
            break;
    }

    cout << a << ' ' << b << ' ' << c << endl;
}

E. Power Boxes

    交互题先不补了。