这个合集主要是近期的 CodeForces 比赛题。

1898. Codeforces Round 910 (Div. 2)

https://codeforces.com/contest/1898

A. Milica and String

很容易发现答案不超过 \(1\)，然后分类讨论当前 B 的个数然后选取一个前缀赋值即可。如果已经满足条件答案就是 \(0\)。反正随便做做，时间复杂度 \(O(n)\)，代码。

B. Milena and Admirer

考虑 倒着 贪心，我们肯定是要让当前在填的这个数尽可能大，给前面的数留出空间。二分这个数需要分几次才能 \(\leq x\)，具体一点，如果 \(v\) 要分 \(k\) 次，那么最优方案下这 \(k + 1\) 个数的最小值为 \(\left\lfloor\dfrac{v}{k + 1}\right\rfloor\)，最大值为 \(\left\lceil\dfrac{v}{k + 1}\right\rceil\)。贪心即可，时间复杂度 \(O(n \log a_n)\)，代码。

C. Colorful Grid

容易发现，我们可以先从 \((1, 1)\) 走到 \((n, m)\) 然后兜圈子。发现 \(k\) 的奇偶性与 \((n + m - 2)\) 相同，如果不同直接无解。如果 \(k < n + m - 2\) 那么根本无法走到，也无解。然后我们就考虑兜圈子，设要兜 \(k' = k - (n + m - 2)\) 步。如果 \(k' \bmod 4 = 0\)，那么直接按 \((n, m) \to (n, m - 1) \to (n - 1, m - 1) \to (n - 1, m) \to (n, m)\) 这样循环即可，按照路径染色即可。否则 \(k' \bmod 4 = 2\)，可以在一开始多向右走 \(1\) 步，在多向左走 \(1\) 步，如图：

容易发现在 \(n = m = 3\) 的情况下，该构造方案也是合法的，所以可以 AC，写完代码一定要查 corner case！时间复杂度 \(O(nm)\)，瓶颈在输入输出 & 初始化乐，代码。

D. Absolute Beauty

典。

感觉和 CF1093G 的套路类似。

设 \(C = \displaystyle \sum_{i = 1}^{n}|a_i - b_i|\)。

设交换了 \(b_i, b_j(1 \leq i < j \leq n)\)，那么贡献为 \(C - |a_i - b_i| - |a_j - b_j| + |a_i - b_j| + |a_j - b_i|\)，我们考虑枚举 \(i\)，然后把后两个绝对值拆开，发现 \(a_i\) 与 \(b_j\) 异号，\(a_j\) 与 \(b_i\) 也异号。然后就可以把 \(a_i, b_i\) 和 \(a_j, b_j\) 拆开算了。直接暴力枚举正负号即可，具体见代码，时间复杂度 \(O(n)\)，代码。

E. Sofia and Strings

Conclusion. 可以把操作 \(\symbfit{2}\) 看成交换 \(\symbfit{s_i, s_{i + 1}}\) 并且满足 \(\symbfit{1 \leq i < n}\) 且 \(\symbfit{s_i \geq s_{i + 1}}\)。

考虑贪心匹配 \(t\) 在 \(s\) 中的位置。

容易发现 \(t_i\) 在匹配的时候右边不能有字典序比 \(t_i\) 大的并且已经匹配完的（指 \(t_1, t_2, \dots, t_{i - 1}\)），如果这个条件满足了，那么可以 \(t_n, t_{n - 1}, \dots, t_1\) 倒着向右边移动，可以发现一定是可以移动的。

然后贪心匹配，维护 \(52\) 个 std :: set，前 \(26\) 个表示每一个字母 未匹配 的下标。后 \(26\) 个表示每一个字母 已匹配 的下标。贪心选取一个尽可能靠前的并且右边没有比 \(t_i\) 大的已匹配的字符即可。如果在匹配某个字母的时候没有满足条件的就是无解。

时间复杂度 \(O(n \log n)\)，代码。

F. Vova Escapes the Matrix

有点难写，但是没有那么难调。

首先如果没有出口我们就可以把所有 . 都填上。

如果只有 \(1\) 个出口，那么保留最短的从起点到某一个点的最短路，剩下的可以都填上。

关键就是处理 \(\geq 2\) 个出口。我们可以选两条最短的最短路，但是会有重复的。怎么办？首先我们发现两条路径相交的部分是一个前缀，那么就存在一个分叉。枚举这个分叉，然后求这个分叉到出口的最短路的最短的两条，这个可以使用多源 bfs 求解，在加上到起点的距离用 . 的数量减去就是对答案的贡献了。主要难在这一部分以及代码实现，注意细节，时间复杂度 \(O(nm)\)，代码。