Codeforces Round #715 Almost Sorted DP+构造

题意

定义“几乎有序”排列为:对于任意的$i$,有$a_{i+1}\geq{a_i}-1$。

现在问你$1$到$n$的排列中,对于满足“几乎有序”的排列,按字典序排序后,从小到大第$k$个排列是什么。

题解

我是DP做的。虽然DP完了我发现应该是有什么数学性质。但不重要。

总而言之就是通过DP得到长度为$l$的排列,总共有多少“几乎有序”排列。把$n$和$k$不断拆分成子DP。

1、结论:从后往前改

以$n=6$为例。我们可以注意到,对于$k=1$是$(1,2,3,4,5,6)$。对于$k=2$是$(1,2,3,4,6,5)$。

根据这个显然的例子我们立刻得到一个显然的结论:一定是从后往前改。

2、结论:一定是若干个连续且不相交的区间直接倒置

首先,将部分区间直接倒置显然是可行的。现在问题就是为什么一定是区间倒过来。

当我们尝试把某个数字$x$直接排到后面时,比如放到位置$i$,于是$a_{i-1}$的选择只有两个:1. $a_{i-1}=x+1$,2. $a_{i-1}<x$。

对于$a_{i-1}=x+1$:问题转化成,将$x+1$直接放到$i-1$的位置上,$i-2$将面对同样的问题。这样递归下去,结果就是一段区间的倒置。

对于 $a_{i-1}<x$的情况:如果是这样,我们可以发现对于任意的$j<i$,都有$a_j<a_i$。因为假如存在$a_j>a_i$那么只有一种构造方法,就是$a_{i-1}=x+1$这样一直加过去。因此对于 $a_{i-1}<x$,说明$a_i$是一个区间倒置的开头。(倒置的长度可以为1,也就是什么也不做)。

最后,显然,两段不相交的区间可以随便倒置。比如$(3,2,1,4,6,5)$。$[1,3]$倒置了和$[5,6]$倒置无关。

以$n=6$为例。假如我们交换3和4。我们得到$(1,2,4,3,5,6)$。现在,假如我想让2也参与到倒置之中。那么只有一种可能就是$(1,4,3,2,5,6)$。

3、计算$n$排列的所有可能数

令$dp[i][0]$表示长度为$i$的排列,不管是不是从第一个数字开始倒置,总共有多少“几乎有序”排列。

令$dp[i][0]$表示长度为$i$的排列,第一个数字必须参与倒置的情况下,总共有多少“几乎有序”排列。

于是有$dp[i][1]=1+\sum_{j=1}^{i-2}dp[j][0]$,$dp[i][0]=dp[i][1]+dp[i-1][0]$。

意思是说,$dp[i][1]$等于从i开始,长度为$i-j$的区间倒置之后,剩下长度为$j$区间的所有可能(也即是$dp[j][0]$)的和。外加直接从$i$到$n$全部倒置的1种情况。

$dp[i][0]$自不待言。就是$i$参与倒置和$i$不参与倒置的和。

举个例子:

考虑$dp[5][1]$。大概分为$(2,1,?,?,?)$,$(3,2,1,?,?)$,$(4,3,2,1,?)$以及$(5,4,3,2,1)$这几种。所以这里$i=5$的时候,$j$最大是$i-2=3$,也就是3个?。而三个?的全部可能就是$dp[3][0]$。

所以$dp[5][1]=dp[3][0]+dp[2][0]+dp[1][0]+1$。

打表出来后发现规律:$dp[i][0]=2^{i-1}$,$dp[i][1]=2^{i-2}$。有兴趣的可以考虑证明一波。

4、每次找出当前$n$和$k$下,第一个倒置的位置

首先,因为倒置是连续区间倒置。所以我们希望第一位倒置的长度尽可能小。比如$(1,2,3,4,5,6)$能只倒置$[3,4]$就不倒置$[3,5]$。因为$(1,2,4,3,5,6)$比$(1,2,5,4,3,6)$小。

于是我们根据$dp[i][0]$找出对于当前的$n$和$k$的倒置位置,也就是最小的$i$使得$dp[i][0]\geq{k}$。这样$n-i+1$位就是第一个改动点。

然后我们枚举第一个最小的改动点的倒置长度$l$。使得$dp[i-1][0]+\sum_{j=i-l}^{1}dp[j][0]\geq{k}$。

这样问题就转换成了对于长度为$i-l$的排列,第$k-dp[i-1][0]-\sum_{j=i-l+1}^{1}dp[j][0]$大的满足要求的排列。(注意此处$l-1$是因为上面找$l$的时候是已经大于$k$了,所以-1之后小于k,留给子问题解决)。

代码

Submission #113258017 - Codeforces
Codeforces. Programming competitions and contests, programming community
展示评论