又是挺悲剧的一道题目……上题目先……
Language:Default
A decorative fence
| **Time Limit:** 1000MS
|
|
**Memory Limit:** 10000K
|
| **Total Submissions:** 3869
|
|
**Accepted:** 1287
|
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 di erent 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
|
这道题目意思还是比较容易看懂的，不过做起来比较麻烦……但是我还是自己想到了算法~不过挺悲剧就是……
题目如果只是问总共有多少种方法情况的话能简单不少，直接DP就好了。a[i][j][k]表示总共i个数字第一位是j，k＝0表示双数位是大，k＝1表示单数位是大的情况个数，然后就能得到DP方程，分K=0，k=1两种情况。具体方程待会儿看源码吧……
然后要打印结果就用递归。一个个减下来。先确定第一位是多少，再递归第二位，再递归第三位。写一个函数getAns(int n, long long c, int j, int k, int ans[])，取总共有n个数，第c种情况，j表示前一位的数值，k表明双数位跟单数位哪个是大，然后结果放在ans里面……最后再处理一下ans就打印了……
呃……突然发现我的算法好复杂……应该有更好的算法……
然后写好程序就提交，发现WA了……悲剧，然后调试，发现一个错误，问题原因是在判断找到确切位置的时候判断条件有问题，数组超下界了……但是没报错……C的悲剧啊……
然后改了，还是WA……话说要上课了……然后就跑去上课了……上课的时候突然想到可能是编译器选了C++的关系，因为用到了long long，于是下课来电阅……换G++，继续WA……大悲剧……然后居然在记事本里面发现了错误……然后错误原因是getAns里面的c不小心用了int……哎……用VIM的大悲剧啊……如果用了IDE的话应该能够发现吧……
话说最后居然在记事本里面就看出了错误所在……说明放下代码一段时间再看代码DEBUG效率高很多啊……比赛的时候善用这点……
贴上代码：
Source Code
| **Problem:** [1037](http://acm.pku.edu.cn/JudgeOnline/problem?id=1037)
|
|
**User:** [dashashi](http://acm.pku.edu.cn/JudgeOnline/userstatus?user_id=dashashi)
|
| **Memory:** 396K
|
|
**Time:** 32MS
|
| **Language:** G++
|
|
**Result:** Accepted
|
-
Source Code
#include </span>
#include </span>
int n, t;
long long c, a[22][22][2];
void Init()
{
n = 20;
int i, j, t;
memset(a, 0, sizeof(a));
a[1][1][1] = 1;
a[2][2][1] = 1;
a[2][1][0] = 1;
for(i=3; j<=n; i++)
for(j=1; j<=i; j++){
for(t = 1; t<=j-1; t++)
a[i][j][1] += a[i-1][t][0];
for(t = j; t<=i; t++)
a[i][j][0] += a[i-1][t][1];
}
}
void getAns(int n, long long c, int j, int k, int ans[])
{
if(n == 0)
return;
if(n == 1){
ans[1] = 1;
return ;
}
int t;
if(k == 1){
for(t=1; t<=j-1; t++){
if(a[n][t][0] >= c)
break;
c -= a[n][t][0];
}
ans[1] = t;
getAns(n-1, c, t, 1-k, ans+1);
}else if(k == 0){
for(t=j; t<=n; t++){
if(a[n][t][1] >= c)
break;
c -= a[n][t][1];
}
ans[1] = t;
getAns(n-1, c, t, 1-k, ans+1) ;
}
}
void print(int n, long long c)
{
int ans[30], i, j, k;
memset(ans, 0, sizeof(ans));
for(j=1; j<=n; j++){
for(k=1; k>=0; k–){
if(a[n][j][k] >= c)
break;
c -= a[n][j][k];
}
if(k != -1)
break;
}
ans[1] = j;
getAns(n-1, c, j, k, ans + 1);
for(i = n; i>=1; i–){
for(j=i+1; j<=n; j++)
if(ans[j] >= ans[i])
ans[j]++;
}
for(j=1; j<=n; j++){
printf(“%d”, ans[j]);
printf(j == n?”\n”:” “);
}
}
int main()
{
Init();
scanf(“%d”, &t);
for(int i=1; i<=t; i++){
scanf(“%d%lld”, &n, &c);
print(n, c);
}
return 0;
}