Codeforces Round 842

C 题 FST 劲爆下分

Source

Codeforces Round 838

A - Greatest Convex

$x! + (x - 1)! = (x + 1)\times(x - 1)!$

令 $x = k - 1$ 即可，显然这也是最大的

Code

1768 A

B - Quick Sort

permutation forces

找出 $p$ 中是 $1, 2, \cdots, n$ 前缀的最长子序列。非该序列中的元素都要按照大小每 $k$ 个进行一次操作，不足 $k$ 个用已经排好的序列的后缀补上即可

Code

1768 B

C - Elemental Decompress

permutation forces

尝试模拟

先尽量填 $p$，若 $a_i$ 已经出现过就填入 $q_i$，若已经出现过两次则显然不合法

一遍过后，$p_i, q_i$ 有且仅有一个不为 0

接下来，考场上做法是依次填上最大的没被用掉的，但是容易退化到 $O(n^2)$，最后 FST 了

考虑改进第二步填空。把 $p$ 中不在 $n$ 排列的数记录下来，同时记录 $p_i$ 为 0 时的 $q_i$。在没填的位置上，选择与 $q_i$ 相对大小一致的没填的数即可

注意每个 case 记得清空 $p, q$

Code

1768 C

D - Lucky Permutation

permutation forces

考场上绕了半天，处理了一堆情况，总是差一点

这题想法很妙：对于排列 $p$，建边 $i\to p_i$，得到一张图

可以发现，这张图由形如 $i\to p_i\to p_{p_i}\to\cdots i$ 的环划分。将 $p$ 升序排序所需要的交换次数即为 $n - cycles$，其中 $cycles$ 表示图中环的个数

然后回到本题，易知最后要变成的排列有 $n - 1$ 种可能，其中第 $i$ 种为升序排列基础上交换 $(i, i + 1)$。讨论每种可能，找到最小的交换次数即可

设给出的 $p$ 中，$x\to i, y\to i + 1$。对于第 $i$ 种可能的排列，我们应该删去 $x\to i, y\to i + 1$，加上 $x\to i + 1, y\to i$。观察一下对 $cycles$ 的影响：

• 若 $x, y$ 在同一个环中，这样会使该环分裂成两个，即 cycles++
• 若 $x, y$ 不在同一个环中，这样会使两个环合并成一个，即 cycles--

这样，我们实际上无需真正删边，使用并查集维护即可

Code

1768 D

Warnings

• 边界情况有可能无需特判，特判前想想清楚
• 记得 memset()，能省下排查问题的时间