3257685_ce.cpp

部分PKU上的源码

#include <iostream.h>
#include<string>
using namespace std;
int num[21][21][2],work[21][21][2],out[21];
int i,j,k,count,t;
int K,N,C;
void display(int number);
int get (int x,int y,int z);
void output(int x,int number);
void output2(int x,int number,int z,int chu);

	int main ()
{cin>>K;
memset(num,0,21*21*2);
 memset(work,0,21*21*2);
num[2][1][0]=0;num[2][1][1]=1;	num[2][2][0]=1;num[2][2][1]=0;
for(i=3;i<=20;i++)
  for(j=1;j<=i;j++)
  {get(i,j,1);get(i,j,0);}
for(i=0;i<K;i++)
{for(j=1;j<=20;j++) out[j]=j;
	cin>>N>>C; 
output(N,C);
cout<<endl;
}
	return 0;
}
	int get (int x,int y,int z)
{if(work[x][y][z]==1) return num[x][y][z];
else{if(z==0) {for(i=1;i<y;i++) num[x][y][z]+=get(x-1,i,1);}
	   else {for(i=y;i<=x-1;i++) num[x][y][z]+=get(x-1,i,0);}
	    work[x][y][z]=1;
		return num[x][y][z];}
}

void output(int x,int number)
{if(x==2){if(number==2) display(2),display(1);
           else display(1),display(1);
            }
	else{count=0;
	for(i=1;i<=x;i++)
	{count+=num[x][i][0]; if(count>=number) {count-=num[x][i][0];display(i);output2(x-1,number-count,1,i);return;}
	count+=num[x][i][1]; if(count>=number) {count-=num[x][i][1];display(i);output2(x-1,number-count,0,i);return;}
	}
}
}
void output2(int x,int number,int z,int chu)
{if(x==2){if(z==0) display(2),display(1);
           else display(1),display(1);
            }
else{count=0;
	if(z==1) {
	for(i=1;i<=x;i++) 
	{
		count+=num[x][i][1]; 
		if(count>=number) {count-=num[x][i][1];display(i);output2(x-1,number-count,0,i);return;}
	}
}
else {
	for(i=chu;i<=x;i++) 
	{
		count+=num[x][i][0]; 
		if(count>=number) {count-=num[x][i][0];display(i);output2(x-1,number-count,1,i);return;}
	}
}
}
}
	
	
	void display(int number)
{t=0;
	for(k=1;k<=20;k++) 
	{if(out[k]!=0) t++;
	 if(t==number) cout<<k<<" ",out[k]=0,k=20;
	}
}