BUPT2017 wintertraining(15) #6C
题意
给长度n的数列，1,2,..,n，按依次递增递减排序，求字典序第k小的排列。
题解
dp。
up[i][j]表示长度为j,以第i小开头前两个递增的排列有几种。
down[i][j]表示长度为j,以第i小开头前两个递减的排列有几种。
那么有\(down[i][j]=\sum_{k=1}^{k=j-1}up[k][j-1]\)
并且有\(down[1][1]=1\),\(up[i][j]=down[j-i+1][j]\)。
然后就可以递推了。
求第k小的排列，令s[i]=i(i=1,2,…n)，再令i为n到1,从小到大枚举未用过的i个数中第v小的，如果down[v][i]不比k小，说明后面是以第v小开头的长为i的开头递减排列，之后就要找这些排列中第k-down小的了。或判断up，根据标记的fup(表示之前是上升否)。输出s[v]，并移除s[v]。
代码
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#define N 21
#define ll long long
using namespace std;
int t,n;
ll k;
ll up[N][N],down[N][N];
int s[N];
void get(){
int fup,v=0;
for(int i=1;i<=n;i++)s[i]=i;
for(int i=n;i;i--){//剩下i个位置要放
if(i==n){
for(int j=1;j<=n;j++){//放第1小到第n小
if(k<=down[j][i]){//先考虑下降，因为下降则这个方案更小
v=j;fup=0;break;//s[j]开头的够算，且是之后一个是上升
}
k-=down[j][i];//不够算，则找后面的第k-down大的方案。
if(k<=up[j][i]){
v=j;fup=1;break;
}
k-=up[j][i];
}
}else{
if(fup){
for(int j=v;j<=i;j++){
if(k<=down[j][i]){
v=j;break;
}
k-=down[j][i];
}
}else{
for(int j=1;j<v;j++){
if(k<=up[j][i]){
v=j;break;
}
k-=up[j][i];
}
}
fup^=1;
}
printf("%d ",s[v]);
for(int j=v;j<i;j++)s[j]=s[j+1];
}
puts("");
}
int main() {
down[1][1]=1;
for(int i=1;i<N;i++){
for(int j=2;j<=i;j++)
down[j][i]=down[j-1][i]+up[j-1][i-1];
//以第j小开头长度i的下降=sum_{k=1}^{k=j-1}{up[k][i-1]}
//那么down[j][i]-down[j-1][i]=up[j-1][i-1]
for(int j=1;j<=i;j++)
up[j][i]=down[i-j+1][i];
//第j小开头的上升=第i-j+1大开头的下降
}
scanf("%d",&t);
while(t--){
scanf("%d%lld",&n,&k);
get();
}
return 0;
}