「题解」写点 Codeforces 之 12 道构造题

Problem - 2059B - Codeforces

*1200

把一个有 $n$ 个数的数列分割成 $k$ 个子数组，最小化具有偶数索引的子数组串联后形成的新数组的「代价」。（数组 $b$ 的「代价」定义为使 $b_i \neq i$ 成立的最小索引 $i$。

赛时对着这题坐牢，疑似是注意力有点欠缺了。

首先可以明显注意到当 $n = k$ 当时候，我们只需要模拟找到 $b_i \ne i$ 即可。

那么当 $n < k$ 的时候呢？我们可以把后 $k - 2$ 个元素切分成后 $k - 2$ 个子数组，这样我们就只需要考虑最开始的几个元素即可：

• 首先，对于第一个元素，无论是什么都不影响，因为我们要串联的是偶数段。

• 其次，考虑第二个元素到第 $n - k + 2$ 个元素，如果这段中有某个元素不是 $1$，我们就可以把该元素之前的部分设为第一个子数组，这样我们的第二个子数组就是不是以 $1$ 开头的了，答案是 $1$。

• 最后，如果该部分全部都是 $1$ 的话，显然答案是 $2$。

按照如上思路编写代码即可。

Problem - 2059C - Codeforces

*1500

给定 $n$ 个队列，每个队列有 $n$ 个元素，代表在第 $i$ 个时刻第 $k$ 个队列的人数的增加值。在第 $i$ 个时刻可以任意选择一个队列清空该队列的人数。最大化第 $n$ 个时刻由所有队列人数组成的数组的 $\text{MEX}$。

如果没在上题坠机就好了。

为了最大化 $\text{MEX}$，我们期望队列是由 $0,1,2,\ldots,n-1$，组成的。考虑到在第 $n$ 个时刻我们可以清空某一个队列，因此 $0$ 是一定存在的。然后我们考虑上一个时刻因为上一个时刻一定存在一个队列为 $0$，那么只要这一个时候该队列的元素为 $1$，即可。同理我们可以得到：最佳情况下，队列最后剩余的人数就是队列后缀连续出现 $1$ 的个数。根据此计算队列人数 $a$ 并求出 $\text{MEX}(a)$ 即可。

Problem - 2063B - Codeforces

*1100

给定一个长度为 $n$ 的序列 $a$ 和一个区间 $[l, r]$。最小化反转 $a$ 的某一个子序列 $b$ 后的区间和 $\sum_{i=l}^{r} a_i$。

考虑到反转的特性， 对于 $\forall i \in [1, l), j \in [l, r]$ 可以构造一个子序列使得反转后 $a_i, a_j = a_j, a_i$。并且多个这样的子序列叠加不影响其性质，对于 $(r,n]$ 也是一样。

因此，对区间 $[l, r]$，$[0, l)$ 和 $(r, n]$ 内的元素分别排序。计算将 $[l, r]$ 内最大的几个元素和 $[0,l)$ 内最小的几个元素交换后的区间和 $S_1$，以及和 $(r, n]$ 最小的几个元素交换后的区间和 $S_2$，还有其本来的区间和 $S_0$（子序列可以为空）。答案即为 $\min(\{S_0, S_1, S_2\})$。

Problem - A - Codeforces

*800

题意略。

因为序列长度可以是 $1$，统计 1 的个数就行。

Problem - C - Codeforces

*1500

我从来没有觉得位运算开心过。

在 $[l, r]$ 中选 $a, b, c$，使得 $S=(a \oplus b) + (b \oplus c) + (a \oplus c)$（$\oplus$ 代表异或运算）最大。

$$\begin{aligned} \text{令：} a &= 2^n\times a_n + 2^{n-1} \times a_{n-1}+\ldots+2^{0}\times a_0 \\ b &=2^n\times b_n + 2^{n-1} \times b_{n-1}+\ldots+2^{0}\times b_0 \\ c &=2^n\times c_n + 2^{n-1} \times c_{n-1}+\ldots+2^{0}\times c_0 \\ &\text{我们就可以把 S 看作多个位运算的结合。} \end{aligned}$$

列个表考察每一位：

a	b	c	ans
0	0	0	0
0	0	1	2
0	1	0	2
0	1	1	2
1	0	0	2
1	0	1	2
1	1	0	2
1	1	1	0

因此，当且仅当 $a, b, c$ 三者至少有一该位不同，该位即可对答案产生影响。因此我们可以任意指定 $a, b, c$ 其中的两个，比如令 $a=l, c=r$，我们构造出 $b$ 即可。

罕见地给出了代码：

void solve(){
    int l, r;
    cin >> l >> r;
    // 固定 a = l, c = r，构造 b
    int b = 0;  // 用来构造 b 的值
    int tp = -1;  // 第一个 l 与 r 不同的位（从高位开始找）
    // 假设数最多 32 位，从 31 到 0
    for(int i = 31; i >= 0; i--){
        if (((l >> i) & 1LL) != ((r >> i) & 1LL)) {
            tp = i;
            break;
        }
    }
    // 注意：题目保证 l < r ，因此 tp 一定不为 -1

    // 1. 对于高于 tp 的位，l 和 r 均相同，直接复制
    for (int i = tp+1; i < 32; i++){
        if((l >> i) & 1LL)
            b |= (1LL << i);
    }
    // 2. 对于从 tp 到 0 的位，先对那些 l 和 r 相同的位，令 b_i = l_i ⊕ 1
    for (int i = tp; i >= 0; i--){
        if (((l >> i) & 1LL) == ((r >> i) & 1LL)){
            // 令 b_i = (l_i XOR 1)
            if (((l >> i) & 1LL) == 0)
                b |= (1LL << i);  // 0^1 = 1
            // 如果 l_i 为 1，则 b_i 取 0；这里 b_i 默认已是 0，所以不用处理
        }
    }
    // 3. 对于从 tp 到 0 的位，处理那些 l 与 r 不同的位：
    for (int i = tp; i >= 0; i--){
        if (((l >> i) & 1LL) != ((r >> i) & 1LL)){
            // 尝试置 1
            b |= (1LL << i);
            // 如果设置后 b 超过或等于 r，则把这一位还原为 0
            if (b >= r)
                b &= ~(1LL << i);
        }
    }
    // 保证最终 l < b < r
    if(b <= l) b = l + 1;
    if(b >= r) b = r - 1;

    cout << l << " " << b << " " << r << "\n";
}

Problem - A - Codeforces

*800

题意略。

没有 $0$ 的行列全都是 $0$；而 $0$ 所在的行列中必有一个是 $1$，最大化不是 $1$ 那个行或列，因此答案是 $\max(n,\;m)+1$。

Problem - C - Codeforces

*1200

最大化序列 $a$ 的最长回文子序列的个数。

为了让个数最大，我们期望这个子序列的长度尽可能短，而数量尽可能多。

考虑最长回文子序列长度为 $1$ 的情况，此时 $a$ 为一个排列，答案是 $n$。考虑最长回文子序列为 $2$ 的情况，在这种情况下，只能是由相邻的连续重复数字组成，如：$\{1,1,2,2,3,3\}$。方案数为 $\frac{n}{2}$。

然后我们就可以构造长度为 $3$ 的情况，也就是 $\{1,2,3,\ldots,1\}$，对于单个这样的序列，其方案数为 $|a|-2$，我们可以通过向该子序列开头或结尾再添加一个 $1$ 的方式构造一个新的序列$\{1,1,2,\ldots,1\}$，这样方案数就变成了 $(|a|-2)\times(|a|-3)$。但是这样的操作只能实现一次。因为更多的操作会使得最长长度不为 $3$。

观察样例的最长长度和通过此种方式构造的最长长度一致，因此可以认为此为正解。至于为什么长度为 $4$ 的情况不会创造更多的方案数，供读者自证明（绝对不是因为我不会）。

Problem - A - Codeforces

*800

题意略。

显然在方格中周长会等于最靠近原点的顶点和最远离原点的顶点的坐标差的绝对值的和的两倍。

Problem - C - Codeforces

*1400

给定一个 $n\times m$ 的网格 $a$ 和一段由向下和向右构成的从 $(1,1)$ 到 $(n,m)$ 的路径。改变在路径上点的值使得 $\sum_{j=1}^m a_{i, j} = x$ 对于 $1\le i\le n$， 且 $\sum_{i=1}^n a_{i, j} = x$ 对于 $1\le j\le m$.

题目指出解总是存在的。考虑到固定 $x=0$，因为路径只能向下或向右，我们可以把某步移动后面对的问题看作成总问题的子问题（因为 $x=0$）。所以我们在向下移动的时候把单元格的值设置为该行元素和的相反数并更新，向右移动时把单元格的值设置为该列元素和的相反数并更新即可。

Problem - B - Codeforces

*1000

给定两个长度为 $n$ 的数列 $a$ 和 $b$。在可以执行「以将 $a$ 除了 $i$ 以外的元素减一为代价把 $a_i$ 加一」操作任意次，问是否能让 $a$ 变成 $b$。

如果有两个 $i$ 满足 $a_i < b_i$ 的话那么无解，因为一个加一的同时另一个在减一。于是我们只需要判断 $b_i - a_i$ 的最大值是否小于等于 $a_i - b_i,i \in [1,n]$ 的最小值即可。

Problem - A - Codeforces

*800

唉唉，唉唉唉。（题意略）

我们假设 $a$ 和 $b$ 相邻：此时先手必负。若 $a$ 和 $b$ 间隔 $1$，则先手必胜（走一步即成为相邻的后手）。

依次类推，得到 $|a-b|\mod 2=0$ 时 $a$ 胜利，否则 $b$ 胜利的结论。

Problem - A - Codeforces

*1600

$n$ 辆赛车以 $1,2,\ldots,n$ 的顺序发车比赛，最后以 $c_1, c_2, \ldots, c_n\;(1 \le c_i \le n, c_i \ne c_j)$ 为顺序通过终点。编号为 $i$ 的车只允许超过编号为 $j$ 的车一次。求最大超车次数以及最大超车次数下的超车事件。

假设 $i < j$，且通过终点的时候 $i$ 先通过终点，那么可能发生两次超车事件：$j$ 超过了 $i$，之后 $i$ 超过了 $j$。

拓展到多辆车，如果通过终点的顺序依然是 $1,2,\ldots,n$ 的话，那么总共发生了 $2n$ 次超车，例如：

1 2 3 (发车)
-----
1 3 2 (3 2)
3 1 2 (3 1)
3 2 1 (2 1)
3 1 2 (1 2)
1 3 2 (1 3)
1 2 3 (2 3)

我们可以发现超车就是蛄蛹着向前再向后的过程。我们可以把这个过程分为两部分：首先是从完全顺序到完全逆序的过程，然后是由完全逆序恢复到终点顺序的过程。我们注意到无论通过终点的顺序怎样，至少第一个过程中的超车都能发生。因为如果 $i < j$ 且 $i$ 先通过终点线的话，那么只需要让 $i$ 从后面再超过来一次就行，如果 $j$ 先通过终点线的话，那么不需要调整。

这种蛄蛹的过程让人想起了冒泡排序，所以我们写一个和冒泡排序差不多的东西模拟一下超车即可。（笑点解析：把冒泡写成了选择排序然后调了半小时）。

在这里给出代码：

void solve() {
    int n;
    cin >> n;
    vector<int> a(n + 1);
    vector<int> b(n + 1);
    for (int i = 1; i <= n; i ++) {
        int x;
        cin >> x;
        b[x] = i;
    }

    vector<pair<int, int>> vec;

    for (int j = n; j >= 1; j --) {
        for (int k = j - 1; k >= 1; k --) {
            vec.push_back({j, k});
        }
        a[n - j + 1] = j;
    }
    bool ok = true;
    while (ok) {
        ok = false;
        for (int i = n; i > 1; i --) {
            if (b[a[i]] < b[a[i - 1]]) {
                ok = true;
                vec.push_back({a[i], a[i - 1]});
                swap(a[i], a[i - 1]);
            }
        }
    }

    cout << vec.size() << "\n";
    if (vec.size()) {
        for (auto &[l, r] : vec)
            cout << l << " " << r << "\n";
    }
}