4577093_re.cpp

部分PKU上的源码

#include<iostream>
#include<algorithm>
using namespace std;
struct biao
{
	long long big;
	long long small;
};
bool small=true;
bool big=false;
biao x[21][21];
bool used[21];
int test_number;
int n;
long long c;
int outnumber;
void tianbiao()
{
	int m,n;
	x[1][1].big=1;
	x[1][1].small=1;
	x[2][1].big=0;
	x[2][1].small=1;
	x[2][2].big=1;
	x[2][2].small=0;
	for(m=3;m<=21;m++)
	{
		for(n=1;n<=m;n++)
		{
			x[m][n].big=0;
			for(int i=1;i<=n-1;i++)
			{
				x[m][n].big+=x[m-1][i].small;
			}
			x[m][n].small=0;
			for(int j=n;j<=m-1;j++)
			{
				x[m][n].small+=x[m-1][j].big;
			}
			//printf("%I64d %I64d%",x[m][n].big,x[m][n].small);
		}
		//cout<<endl;
	}
}
void out(int number)
{
	int temp=0;
	outnumber++;
	for(int count=1;count<=n;count++)
	{
		if(used[count]==false) temp++;
		if(temp==number)
		{
			cout<<count;
			if(outnumber!=n) cout<<" ";
			used[count]=true;
			return;
		}
	}
}
void gets(int n,long long c,int now,bool type)
{
	long long temp=0;
	if(n==1) {out(1);return;}
	if(type==small)
	{
		for(int i=1;i<=now-1;i++)
		{
			temp+=x[n][i].small;
			if(temp>=c) {out(i);gets(n-1,c-temp,i,big);return;}
		}
	}
	else
	{
		for(int j=now;j<=n;j++)
		{
			temp+=x[n][j].big;
			if(temp>=c) {out(j);gets(n-1,c-temp,j,small);return;}
		}

	}
}
void get(int n,long long c)
{
	long long temp=0;
	if(n==1) {out(1);return;}
	for(int count=1;count<=n;count++)
	{
		temp+=x[n][count].big;
		if(temp>=c) {out(count);gets(n-1,c-temp+x[n][count].big,count,small);return;}
		temp+=x[n][count].small;
		if(temp>=c) {out(count);gets(n-1,c-temp+x[n][count].small,count,big);return;}
	}
	cout<<"get worng";
}
int main()
{
	cin>>test_number;
	tianbiao();
	for(int count=0;count<test_number;count++)
	{
		if(count!=0) cout<<endl;
		scanf("%d %i64d",&n,&c);
		memset(used,false,sizeof(used));
		outnumber=0;
		get(n,c);
	}
	return 0;
}