250420 D1 模拟赛 T1 题解

题意

你有一个排列 \(a\)，你要对这个排列进行升序排序。

你每次可以进行如下操作：

选择一个 \(a\) 的子序列，从排列 \(a\) 中删去这个子序列，再将这个子序列插回到 \(a\) 的最前面。

你需要求出最少几次操作可以将 \(a\) 进行排序，并且构造一种方案。

注意到题目可以等价为：给每个数字赋一个二进制数 \(p_i\)，然后以这个二进制数为关键字进行稳定排序；每次操作就等价于向二进制数的高位再添加一个二进制位。

因此我们一定可以在不超过 \(\lceil\log n\rceil\) 次操作内把序列排好序。

然而这个朴素的策略不一定总是最优的。考虑序列 \(a\) 中一个值域上连续上升的子序列，我们可以给子序列中的每个元素都赋予相同的 \(p_i\)，因为它们无需改变相对顺序。显然，选取极长的子序列是一定更优的。

其他情况均不能给多个不同的数字赋予相同的 \(p_i\)。答案就是极长的值域上连续上升自序列数量的 \(\log\)。

构造方案是容易的。我们可以直接求出一组合法的 \(p\)，依次模拟，输出对应方案即可。