Codeforces Round 926 (Div. 2) 题解

比赛链接：https://codeforces.com/contest/1929

官解链接：https://codeforces.com/blog/entry/125943

出的很差的一场。

推歌

CF1929A. Sasha and the Beautiful Array

题意

任意排列数组 \(a_{1..n}\)，求 \(\sum_{i=2}^n (a_i - a_{i-1})\) 的最大值。

题解

见过最显然的 A 题，奠定了本场题目简单的基调。

众所周知 \(\sum_{i=2}^n (a_i - a_{i-1}) = a_n - a_1\)，又因为可以任意排列，答案就是 \(\max(a) - \min(a)\)。

代码实现

void solve() {
    int n;
    cin >> n;
    vector<int> a(n);
    for (int &x: a) cin >> x;
    cout << ranges::max(a) - ranges::min(a) << '\n';
}

CF1929B. Sasha and the Drawing

题意

在一个 \(n \times n\) 的正方形网格上，最少要给多少个格子涂色，才能使至少有 \(k\) 条对角线上至少有一个格子被染色？

题解

垃圾场特有的猜猜题，但我一开始画图画错了，导致猜错了……

在一个最优方案中，涂色一个格子只会使染色对角线的数目增加 \(1\) 或 \(2\)。且我们永远可以将染色两条对角线的操作提前（因为他不会和任何之前的操作产生冲突！）。那么问题就是如何连续进行尽可能多的染色两条对角线的操作。

我们有一种染色方案，能使得共 \(2n\) 次操作中，只有最后两次操作只染色一条对角线，前 \(2n-2\) 次操作如下图：

要证明这是最优方案，只要说明不可能所有操作都能够染色两条对角线。很简单：左下角和右上角的两个小方格，它们所在的两条对角线均只能通过这一条小方格染色，也就是这两次涂色必然进行；但它们又在同一条反对角线上，因此两次涂色擦操作必定至少有一次只染色一条对角线。

若所有操作均染色两条对角线，需要的操作次数为 \(\lceil \dfrac k 2\rceil\)。当 \(\lceil \dfrac k 2\rceil \le 2n-2\) 时，即为答案；否则答案为 \(2n-2 + k - 2 * (2n-2) = k + 2 - 2n\)。

代码实现

void solve() {
    int n, k;
    cin >> n >> k;
    if (k <= 4 * n - 4) {
        cout << (k + 1) / 2 << '\n';
    } else {
        cout << k + 2 - 2 * n << '\n';
    }
}

CF1929C. Sasha and the Casino

题意

题解

这场比赛最有趣的一题。