3047213_ac_0ms_156k.cpp

北大大牛代码 1240道题的原代码 超级权威

#include <stdio.h>
#include <string.h>

__int64 g[21][21][2], c;
int a[21];

void go_up(int n,__int64 c,int lmt);
void go_down(int n,__int64 c,int lmt)
{
	int i, j;

	if(n==1) 
	{
		printf(" %d",a[n]);
		return;
	}
	for(i = lmt; i <= n; i++)
	{
		c -= g[n][i][1];
		if(c < 1)
		{
			printf(" %d",a[i]);
			for(j = i; j <= n; j++)
			{
				a[j] = a[j+1];
			}
			go_up(n-1,c+g[n][i][1],i-1);
			break;
		}
	}
}

void go_up(int n,__int64 c,int lmt)
{
	int i, j;

	if(n==1) 
	{
		printf(" %d",a[n]);
		return;
	}
	for(i = 1; i <= lmt; i++)
	{
		c -= g[n][i][0];
		if(c < 1)
		{
			printf(" %d",a[i]);
			for(j = i; j <= n; j++) 
			{
				a[j] = a[j+1];
			}
			go_down(n-1,c+g[n][i][0],i);
			break;
		}
	}
}

void solve(int n, __int64 C)
{
	int i, j;

	if(n==1) 
	{
		printf("%d",a[n]);
	}
	for(i = 2; i <= n; i++)
	{
		c -= g[n][i-1][0];
		if(c<1)
		{ 
			printf("%d",a[i-1]);
			for(j = i - 1; j < n; j++)
			{
				a[j] = a[j+1];
			}
			go_down(n-1,c+g[n][i-1][0],i-1);
			break;
		}
		c -= g[n][i][1];
		if(c < 1)
		{
			printf("%d",a[i]);
			for(j = i; j < n; j++)
			{
				a[j] = a[j+1];
			}
			go_up(n-1,c+g[n][i][1],i);
			break;
		}
	}
}

int main()
{
	int i, j, k;
	int cas, n;
	
	memset(g,0,sizeof(g));
	g[1][1][0] = g[1][1][1] = 1;
	for(i = 2; i < 21; i++)
	{
		for(j = 1; j < 21; j++)
		{
			for(k = 1; k < j; k++)
			{
				g[i][j][1] += g[i-1][k][0];
			}
			for(k = j; k < i; k++)
			{
				g[i][j][0] += g[i-1][k][1];
			}
		}
	}
	scanf("%d",&cas);
	while(cas--)
	{
		scanf("%d%I64d",&n,&c);
		for(i = 1; i <= n; i++)
		{
			a[i] = i;
		}
		solve(n,c);
		printf("\n");
	}
	return 0;
}