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，留给子问题解决）。