本文共 5882 字，大约阅读时间需要 19 分钟。

Description

Richard just finished building his new house. Now the only thing the house misses is a cute little wooden fence. He had no idea how to make a wooden fence, so he decided to order one. Somehow he got his hands on the ACME Fence Catalogue 2002, the ultimate resource on cute little wooden fences. After reading its preface he already knew, what makes a little wooden fence cute.

A wooden fence consists of N wooden planks, placed vertically in a row next to each other. A fence looks cute if and only if the following conditions are met:

�The planks have different lengths, namely 1, 2, . . . , N plank length units.

�Each plank with two neighbors is either larger than each of its neighbors or smaller than each of them. (Note that this makes the top of the fence alternately rise and fall.)

It follows, that we may uniquely describe each cute fence with N planks as a permutation a1, . . . , aN of the numbers 1, . . . ,N such that (any i; 1 < i < N) (ai − ai−1)*(ai − ai+1) > 0 and vice versa, each such permutation describes a cute fence.

It is obvious, that there are many dierent cute wooden fences made of N planks. To bring some order into their catalogue, the sales manager of ACME decided to order them in the following way: Fence A (represented by the permutation a1, . . . , aN) is in the catalogue before fence B (represented by b1, . . . , bN) if and only if there exists such i, that (any j < i) aj = bj and (ai < bi). (Also to decide, which of the two fences is earlier in the catalogue, take their corresponding permutations, find the first place on which they differ and compare the values on this place.) All the cute fences with N planks are numbered (starting from 1) in the order they appear in the catalogue. This number is called their catalogue number.

After carefully examining all the cute little wooden fences, Richard decided to order some of them. For each of them he noted the number of its planks and its catalogue number. Later, as he met his friends, he wanted to show them the fences he ordered, but he lost the catalogue somewhere. The only thing he has got are his notes. Please help him find out, how will his fences look like.

Input

The first line of the input file contains the number K (1 <= K <= 100) of input data sets. K lines follow, each of them describes one input data set.

Each of the following K lines contains two integers N and C (1 <= N <= 20), separated by a space. N is the number of planks in the fence, C is the catalogue number of the fence.

You may assume, that the total number of cute little wooden fences with 20 planks fits into a 64-bit signed integer variable (long long in C/C++, int64 in FreePascal). You may also assume that the input is correct, in particular that C is at least 1 and it doesn抰 exceed the number of cute fences with N planks.

Output

For each input data set output one line, describing the C-th fence with N planks in the catalogue. More precisely, if the fence is described by the permutation a1, . . . , aN, then the corresponding line of the output file should contain the numbers ai (in the correct order), separated by single spaces.

Sample Input

2

2 1

3 3

Sample Output

1 2

2 3 1

分析

这里我就引用了别人的解题思路，先放在这里，等题量到了我再返回来看，Orz

动归解题思路

 1) 设 A[i] 为i根木棒所组成的合法方案数目。看看能否找出A[i]和A[i-1]

或A[i-j]之间的递推关系(所有木棒总数是i)。称i根木棒的合法方案集合 为S(i)

 2) 在选定了某根木棒x作为第一根木棒的情况下,剩下i-1根木棒的合法

方案数是A[i-1]。但是，这A[i-1]种方案，并不是每种都能和x形成新的 合法方案。将第一根比第二根长的方案称为DOWN方案，第一根比第 二根短的称为UP方案，则，S(i-1)中，第一根木棒比x长的DOWN方 案，以及第一根木棒比x短的UP方案，才能和x构成S(i)中的方案。 动归解题思路

 3) 置A[i] = 0。先枚举x。然后针对每个x，枚举x后面的那根木棒y。如果 y >

x(x<y的情况类推），则: A[i] += 以y打头的DOWN方案数 但以y打头的DOWN方案数，又和y的长短有关。 于是难以直接从 A[i-1]或 A[i-j]推出 A[i]

 4) 考虑将A[i]这种粗略的状态描述方式细化，即加上限制条件后分类。设

A[i] = ∑ B[i][k] k = 1….i B[i][k] 是S(i)中以第k短的木棒打头的方案数。尝试对 B 进行动归。第k短 ，指的是i根木棒中第k短。 动归解题思路

5) B[i][k] = ∑ B[i-1]+ ∑ B[i-1]

M = k … i-1 , N = 1… k-1 还是没法直接推。于是把B再分类细化： B[i][k] = C[i][k][DOWN] + C[i][k][UP] C[i][k][DOWN] 是S(i)中以第k短的木棒打头的DOWN方案数。然后试图对C进行动 归 C[i][k][UP] = ∑ C[i-1][M][DOWN] M = k … i -1 C[i][k][DOWN] = ∑ C[i-1][N][UP] N = 1… k-1 初始条件：C[1][1][UP]=C[1][1][DOWN] = 1

动归解题思路

 经验：当选取的状态，难以进行递推时（分解出的子问题和原 问题形式不一样，或不具有无后效性），考虑将状态增加限制 条件后分类细化，即增加维度，然后在新的状态上尝试递推 排序计数  如1，2，3，4的全排列，共有4！种，求第10个的排列是（从1计 起）？  先试首位是1，后234有3！=6种<10,说明首位1偏小，问题转换成 求2开头的第（10-6=4）个排列，而3！=6 >= 4，说明首位恰是2。  第二位先试1（1没用过），后面2！=2个<4,1偏小，换成3（2用过 了）为第二位，待求序号也再减去2！，剩下2了。而此时2!>=2， 说明第二位恰好是3。  第三位先试1，但后面1！<2，因此改用4。末位则是1了。  这样得出，第10个排列是2-3-4-1。 排序计数 本题待求方案的序号为C 本题就是先假设第1短的木棒作为第一根，看此时的方案数 P(1)是否>=C,如果否，则应该用第二短的作为第一根，C 减去P(1) ，再看此时方案数P(2)和C比如何。如果还 < C ，则应以第三短的 作为第一根,C再减去P(2) …. 若发现 第 i短的作为第一根时，方案数已经不小于C，则确定 应该以第i短的作为第一根， C减去第 i短的作为第一根的所有方案 数，然后再去确定第二根…. 微调：以第i短的木棒作第k根时，有UP和DOWN两类方案， 先用DOWN的方案数和C比较

AC

#include 
   
    #include 
    
     #define UP 1#define DOWN 0#define maxn 25long long C[maxn][maxn][2];void Init(int n){
   	memset(C, 0, sizeof(C));	C[1][1][UP] = C[1][1][DOWN] = 1;	int i, k, M, N;	for(i = 2; i <= n; ++i){
   		for(k = 1; k <= i; ++k){
   			 C[i][k][UP] = C[i][k-1][UP]+C[i-1][k-1][DOWN];		}		for(k = 1; k <= i; ++k){
               C[i][k][DOWN] = C[i][i-k+1][UP];		}	}}void Print(int n, long long cc){
   	long long skipped = 0, oldVal;	int seq[maxn];	int used[maxn];	memset(used, 0, sizeof(used));	for(int i = 1, k; i <= n; ++i){
   		int No = 0;		for(k = 1; k <= n; ++k){
   			oldVal = skipped;			if(!used[k]){
   				++No;				if(i == 1) skipped += C[n][No][UP] + C[n][No][DOWN];				else if(k > seq[i-1] && (i == 2 || seq[i-2] > seq[i-1]))					skipped += C[n-i+1][No][UP];				else if(k < seq[i-1] && (i == 2 || seq[i-2] < seq[i-1]))					skipped += C[n-i+1][No][DOWN];				if(skipped >= cc) break;			}		}		used[k] = 1;		seq[i] = k;		skipped = oldVal;	}	for(int i = 1; i <= n; ++i)		if(i < n) printf("%d ", seq[i]);		else printf("%d\n", seq[i]);}int main(){
   	int T, n; long long c;	Init(20);	scanf("%d", &T);	while(T--){
   		scanf("%d%lld", &n, &c);		Print(n, c);	}	return 0;}
    
   

学如逆水行舟，不进则退

转载地址：https://chocolate.blog.csdn.net/article/details/97618907 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！