Problem Description
A sequence of length n is called a permutation if and only if it‘s composed of the first n positive integers and each number appears exactly once.
Here we define the "difference sequence" of a permutation p1,p2,…,pn as p2−p1,p3−p2,…,pn−pn−1. In other words, the length of the difference sequence is n−1 and the i-th term is pi+1−pi
Now, you are given two integers N,K. Please find the permutation with length N such that the difference sequence of which is the K-th lexicographically smallest among all difference sequences of all permutations of length N.
Input
The first line contains one integer T indicating that there are T tests.
Each test consists of two integers N,K in a single line.
* 1≤T≤40
* 2≤N≤20
* 1≤K≤min(104,N!)
Output
For each test, please output N integers in a single line. Those N integers represent a permutation of 1 to N, and its difference sequence is the K-th lexicographically smallest.
Sample Input
7
3 1
3 2
3 3
3 4
3 5
3 6
20 10000
Sample Output
3 1 2
3 2 1
2 1 3
2 3 1
1 2 3
1 3 2
20 1 2 3 4 5 6 7 8 9 10 11 13 19 18 14 16 15 17 12
Source
题意：给你n和k 求n的全排列 使得ai+1 - ai （1<=i<=n-1）的字典序是第k小
思路：因为k的范围最大是10000 （8！=40320） 7！=5040
所以当n=9时 第一位取9 后面几位全排列 即8！种排列方法（k最大10000次不会超时）
所以分开处理 情况1：n<=8的 这种的要全部算出来 然后sort
之后就是>=9的 这种就直接第一位时n 之后的n-1位全排列
代码：
#include<bits/stdc++.h>
#define ll long long
using namespace std;
struct ydw{
int d[22],dd[22];
}xy[50005];
int n;
bool cmp(ydw u,ydw v)
{
for(int i=1;i<n;i++)
{
if(u.dd[i]!=v.dd[i])return u.dd[i]<v.dd[i];
}
}
int main()
{
int i,j,m,k;
int t;scanf("%d",&t);
int a[25];
while(t--)
{
scanf("%d%d",&n,&k);
for(i=1;i<=n;i++)a[i]=i;
if(n<=8)
{
int k2=1;
for(i=1;i<=n;i++)
{
xy[k2].d[i]=a[i];
}
for(i=2;i<=n;i++)
{
xy[k2].dd[i-1]=a[i]-a[i-1];
}
k2++;
while(next_permutation(a+1,a+1+n))
{
for(i=1;i<=n;i++)
xy[k2].d[i]=a[i];
for(i=2;i<=n;i++)
xy[k2].dd[i-1]=a[i]-a[i-1];
k2++;
}
sort(xy+1,xy+k2,cmp);
for(i=1;i<n;i++)
{
cout<<xy[k].d[i]<<" ";
}
cout<<xy[k].d[n]<<endl;
continue;
}
int s=1;
for(i=1;i<n;i++)//第二种情况
{
s=s*i;
if(s>10000)
{
s=10000;
break;
}
}
int t=0;
while(k>s)
{
k-=s;
t++;
}
int f=n-t,k1=0;
int b[30];
for(i=1;i<=n;i++)if(i!=f)b[k1++]=i;
cout<<a[f]<<" ";//第一位
if(k==1)
{
for(i=0;i<k1-1;i++)cout<<b[i]<<" ";
cout<<b[k1-1]<<endl;
continue;
}
int ans=1;
while(next_permutation(b,b+k1))
{
ans++;
if(ans==k)
{
for(i=0;i<k1-1;i++)cout<<b[i]<<" ";
cout<<b[k1-1]<<endl;
break;
}
}
}
return 0;
}
View Code
permutation 1 多校第五场
原文：https://www.cnblogs.com/ydw--/p/11326897.html
