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;
}