题意：把编号为num的树表示出来。。
<code>
//1014 hdu1100 (pku1095) trees made to order
/*
p 0 1 2 3 4 5 6
treenum[p] 1 1 2 5 14 42 132
treenumsum[p] 1 1 3 8 22 64
1 <= n <= 500,000,000
*/
#include<stdio.h>
#include<string.h>
#define pr printf
int treenum[20],treenumsum[20],f[20],index[20],L[20],p[20],cen[20];
//i¸öµãµÄÊ÷ÓÐtreenum[i]¸ö ,i=f[j] jµÄ¸¸½áµãÊÇi
// cen[j] ²ã ´ú ; p[i] µÚi¸öµãΪ¸ùµÄÊ÷ÓÐ p[i]¸öµã
int left,right,I1,I2,e[4];
/*
fun() ¼ÆËãp¸öµãµÄµÚI¸öÊ÷ µÄ×ó×ÓÊ÷£¬ÓÒ×ÓÊ÷,¼ÆËã×ÓÊ÷µÄµãÊýleft£¬right£¬µÚ¼¸¸öÊ÷I1,I2
fun(4,12) j=12 treenum[0]*treenum[3]= 1*5=5
j=7 treenum[1]*treenum[2]= 1*2=2
j=5 treenum[2]*treenum[1]= 2*1=2
j=3 treenum[3]*treenum[0]= 5*1=5
left=3, I1=3; right=0
fun(3,3) j=3 treenum[0]*treenum[2]= 1*2=2
j=1 treenum[1]*treenum[1]= 1*1=1
*/
void fun(int p,int I)
{int q,i,j;
//p¸öµã µÚI¸öÊ÷ ×óÓÐiµã ÓÒÓÐp-1-iµã
q=p-1;j=I;
for(i=0;i<=q;i++)
{
if(j>treenum[i]*treenum[q-i])j-=treenum[i]*treenum[q-i];
else
{// jÊÇ treenum[right]½øÖÆÊý I1I2
left=i;right=q-i;
if(i<=1)I1=1; else {I1=j/treenum[right];if(j%treenum[right]!=0)I1++;}
I2=j%treenum[right];if(I2==0)I2=treenum[right];
break;
}
}//printf("left=%d right=%d I1=%d I2=%d/n",left,right,I1,I2);
}
int main()
{int i,j,k,m,n,I,num,z,p0;
char tree[20][300];
treenum[0]=treenumsum[0]=1;
treenum[1]=treenumsum[1]=1;
treenum[2]=2;treenumsum[2]=3;
for(i=3;i<=18;i++)//Ë㿨ÌØÀ¼Êý
{k=0;
for(j=0;j<i;j++)k+=treenum[j]*treenum[i-1-j];treenum[i]=k;
treenumsum[i]=treenumsum[i-1]+treenum[i];
}
treenumsum[0]=0;
//pr("%d %d/n",treenum[18],treenumsum[18]);
//treenum[18]=477638700 18¸öµãµÄÊ÷ÓÐtreenum[18]¸ö
//treenumsum[18]=656043856 ÀÛ¼Æ18¸öµãµÄÊ÷ÓÐtreenumsum[18]¸ö
while(1)
{
scanf("%d",&n); if(n==0)break;
//1 2 5 14 42 a
//1 3 8 22 64 b
for(i=1;i<=18;i++)if(n<=treenumsum[i]){num=i;break;}
n-=treenumsum[num-1];z=1;//ÕâÀïµÄz»¹Ã»¿´³öÀ´¸ÉʲôÓõÄ
//printf("%d¸öµã£¬µÚ%d¸öÊ÷/n",num,n);
//num¸öµã µÄµÚn¸öÊ÷
//[]ÀïµÄÊý×Ö¾ÍÊǸù
f[1]=0;//µÚ1µãÊǸù£¬Ã»Óи¸½Úµã
index[1]=n; //ÒÔµÚ1µãΪ¸ùµÄÊ÷ÊÇÓÐnumµãµÄµÚn¸öÊ÷
p[1]=num; //ÒÔµÚ1µãΪ¸ùµÄÊ÷ÓÐnumµã
L[1]=0; //µÚ1µãΪ¸ù,Ëû²»ÊÇÈκεãµÄ×ó×Ó»òÓÒ×Ó
//L[i]=-1 ×ó 1 ÓÒ
for(i=0;i<=num;i++)cen[i]=-1;//»¹²»ÖªµÀiÊǵڼ¸´úµÄµã
cen[1]=0; //µÚ1µã ÊǵÚ0´úµÄµã £¬¸ùÊÇ µÚ0´ú£¬¸ùµÄ×ÓÊǵÚ1´ú...×î¶à ÓÐ num´ú
//ÕÒ µÚi´úµÄµã
for(i=1;i<=num;i++)
{
for(j=1;j<=num;j++)
{
if(cen[j]!=i-1)continue; // µÚi´úµÄµãµÄ¸¸ÊÇi-1´ú
p0=p[j]; // µÚi´úµÄµãµÄ¸¸ÊÇ p0¸öµãµÄ µÚI¸öÊ÷
I=index[j];
//p0¸öµã µÚI¸öÊ÷
fun(p0,I); //¼ÆËãp0¸öµãµÄ µÚI¸öÊ÷µÄ ×óÓÒ ×ÓÊ÷
if(left!=0){z++;cen[z]=i;p[z]=left;index[z]=I1;f[z]=j;L[z]=-1;}
if(right!=0){z++;cen[z]=i;p[z]=right;index[z]=I2;f[z]=j;L[z]=1;}
}
if(z==num)break;
}// for i
//for(i=1;i<=num;i++)pr("%d p=%d I=%d L=%d f=%d c=%d/n",i,p[i],index[i],L[i],f[i],cen[i]);
//cen[0]=cen[num];
for(i=num;i>=1;i--)
{k=0; for(j=1;j<=num;j++)if(f[j]==i){k++;e[k]=j;}
if(k==0)// ÎÞ×ÓÊ÷
{ strcpy(tree[i],"X");continue;}
if(k==1&&L[e[1]]==-1)// Ö»ÓÐ×ó×ÓÊ÷
{
strcpy(tree[i],"(");
strcat(tree[i],tree[e[k]]);strcat(tree[i],")X");
continue;
}
if(k==1&&L[e[1]]==1){//Ö»ÓÐÓÒ×ÓÊ÷
strcpy(tree[i],"X(");strcat(tree[i],tree[e[k]]);
strcat(tree[i],")");
continue;
}
strcpy(tree[i],"(");//ÓÐ×óÓÒ×ÓÊ÷
strcat(tree[i],tree[e[1]]);strcat(tree[i],")X");
strcat(tree[i],"(");
strcat(tree[i],tree[e[2]]);
strcat(tree[i],")");
} // for i
pr("%s/n",tree[1]);
}
}