北大算法基础
美丽栅栏 _练习代码
#include<iostream>
#pragma warning(disable : 4996)//禁用scanf错误提示
using namespace std;
const int UP = 0;
const int DOWN = 1;
const int MAXN = 25;
long long c[MAXN][MAXN][2];
//c[i][k][DOWN] 是i根木棒以k木棒打头向下的合理方案数
//c[i][k][UP] 是i根木棒以k木棒打头向上的合理方案数
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++) {//枚举第一根木棒k
for (int M = k ; M < i; M++)//枚举第二根木棒M比k长
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];//枚举第二根木棒N比k短
}
}
void Print(int n, long long cc) {//n根木棒,第cc个序列
long long skipped = 0;
int seq[MAXN];//输出的序列
int used[MAXN];//木棒是否用了
memset(used, 0, sizeof(used));
for (int i = 1; i <= n; i++) {//依次确定每个i位置的木棒
int k = 0;
int No = 0;//k在剩余木棒中是第几短
for (k = 1; k <= n; k++) {
skipped = 0;
if (!used[k]) {//木棒没有被使用时执行
No++;//k是未使用木棒中的第几根
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 >= cc)
break;
else
cc -= skipped;
}
}
used[k] = true;
seq[i] = k;
}
for (int i = 1; i <= n; i++)
printf("%d ", seq[i]);
printf("\n");
}
int main() {
int T, n;
long long cc;
Init(20);
scanf("%d", &T);
while (T--){
scanf("%d %lld", &n, &cc);
Print(n, cc);
}
return 0;
}