poj 1037 A decorative fence
共 2355字，需浏览 5分钟
· 2021-11-30
A decorative fence
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
装饰栅栏
描述
理查德刚刚盖完他的新房子。现在房子唯一缺少的是一个可爱的小木栅栏。他不知道如何制作木栅栏，所以他决定订购一个。不知何故，他拿到了 ACME Fence Catalog 2002，这是关于可爱的小木栅栏的终极资源。读了它的序言，他就知道是什么让小木栅栏变得可爱了。
木栅栏由 N 块木板组成，垂直并排放置。当且仅当满足以下条件时，围栏看起来很可爱：
木板具有不同的长度，即 1, 2, . . . , N 木板长度单位。
每块有两个邻居的木板要么比它的邻居大，要么比他们小。（请注意，这会使围栏顶部交替上升和下降。）
因此，我们可以唯一地将每个带有 N 块木板的可爱栅栏描述为排列 a1,... . . , 数字 1 中的 N, . . . ,N 使得 (any i; 1 < i < N) (ai − ai−1)*(ai − ai+1) > 0 反之亦然，每个这样的排列都描述了一个可爱的围栏。
很明显，有许多不同的可爱木栅栏，由 N 块木板制成。为了将一些订单放入他们的目录中，ACME 的销售经理决定按以下方式订购它们：围栏 A（由排列 a1, . . , aN 表示）在围栏 B（由 b1, . 表示）之前在目录中。. . , bN) 当且仅当存在这样的 i，即 (any j < i) aj = bj 和 (ai < bi)。（还要决定，两个栅栏哪个在目录中较早，取它们对应的排列，找到它们不同的第一个位置并比较这个位置的值。）所有有N块木板的可爱栅栏都编号（从1) 按照它们在目录中出现的顺序。这个编号称为他们的目录编号。
仔细检查了所有可爱的小木栅栏后，理查德决定订购一些。他记下每块木板的数量和目录号。后来，当他遇到他的朋友时，他想向他们展示他订购的围栏，但他在某处丢失了目录。他唯一能得到的就是他的笔记。请帮他看看，他的围栏会是什么样子。
输入
输入文件的第一行包含输入数据集的数量 K (1 <= K <= 100)。后面有 K 行，每行描述一个输入数据集。
以下 K 行中的每一行都包含两个整数 N 和 C (1 <= N <= 20)，用空格分隔。N是围栏的木板数量，C是围栏的目录号。
您可能会假设，带有 20 块木板的可爱小木栅栏的总数适合一个 64 位有符号整数变量（C/C++ 中的 long long，FreePascal 中的 int64）。您也可以假设输入是正确的，特别是 C 至少为 1 并且它不超过带有 N 块木板的可爱围栏的数量。
输出
对于每个输入数据集输出一行，描述目录中带有 N 个木板的第 C 个栅栏。更准确地说，如果栅栏由置换 a1, . . . , aN，则输出文件的相应行应包含数字 ai（按正确顺序），以单个空格分隔。
样本输入
2
2 1
3 3
样本输出
1 2
2 3 1
这道题总算勉勉强强看懂了，DP和计数都很不好想
DP部分：
称i根木棒的合法方案集合为S(i)，第二根木棒比第一根长的方案称作UP方案，反之叫做DOWN方案
C[i][k][DOWN] 是S(i)中以第k短(而不是长度为k)的木棒打头的DOWN方案数。
假设S(i)中第一根木棒长为x，那么构成合法的方案数有两类：
S(i - 1)中第一根木棒比x长的DOWN方案
S(i - 1)中第一根木棒比x短的UP方案
有如下递推关系：
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
举个例子：
比如四根木棒，假设第一根木棒长度为2，在剩下的1 3 4中，比2长的3和4分别是S(3)中第2和第3短的。(要和C所定义的状态相对应)
所以上式的M和N的范围就是这样的
总的方案数就是：Sum{ C[n][k][DOWN] + C[n][k][UP] } k = 1.. n
计数部分：
扔掉这个题，考虑一下这个问题：
1 2 3 4全排列，求字典序的第10个
首先假设第一个数是1，那么后面有3! = 6 < 10种排列情况，所以打头的不是1。 继续假设是2，后面三个数也有6种排列情况， 6 + 6 ≥ 10，所以第一个数确定是2，此时跳过了第一个数为1的6种情况。
继续假设第二个数是1，后面有2! = 2种情况， 2 + 6 ＜ 10，所以假设第二个数是3(注意2已经在第一个数中用过了)，依旧是有2种情况， 8 + 2 ≥ 10，第二个数确定是3，跳过了10种情况。
后面因为10 ≥ 10，所以第三第四个数分别是1 4
所求的排列就是2 3 1 4
回到这个题上来：
前面已经求得了i个数中第k小打头的方案数，所以我们也完全可以模拟上面的思维过程来求解。
微调：以第i短的木棒作第k根时，有UP和DOWN两类方案，先用DOWN的方案数和C比较
代码：
#include
#include
#include
using namespace std;
const int maxn = 25;
const int UP = 0;
const int DOWN = 1;
long long C[maxn][maxn][2];
void Init(int n)
{
memset(C, 0, sizeof(C));
C[1][1][UP] = C[1][1][DOWN] = 1;
for(int i = 2; i <= n; ++i)
for(int k = 1; k <= i; ++k)
{
for(int M = k; M < i; ++M)
C[i][k][UP] += C[i - 1][M][DOWN];
for(int N = 1; N <= k - 1; ++N)
C[i][k][DOWN] += C[i - 1][N][UP];
}
}
void Print(int n, long long c)
{
long long skipped = 0;
int seq[maxn], used[maxn];
memset(used, 0, sizeof(used));
for(int i = 1; i <= n; ++i)
{
long long oldVal = skipped;
int k, 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][DOWN];
else if(k < seq[i - 1] && (i == 2 || seq[i - 2] < seq[i - 1]))
skipped += C[n - i + 1][No][UP];
}
if(skipped >= c)
break;
}
}
used[k] = 1;
seq[i] = k;
skipped = oldVal;
}
for(int i = 1; i < n; ++i) printf("%d ", seq[i]);
printf("%d\n", seq[n]);
}
int main(void)
{
#ifdef LOCAL
freopen("1037in.txt", "r", stdin);
#endif
int T, n;
long long c;
Init(20);
scanf("%d", &T);
while(T--)
{
scanf("%d %lld", &n, &c);
Print(n, c);
}
return 0;
}