简单递归,一个小错误浪费一下午、、、、
左子树的权值比右子树大!看清题、、、、
#include<stdio.h> #include<math.h> typedef long long ll; ll cat[50]; ll sum[50]; void solve(int num,int rank){ int i,tem=rank; if(num==1){ printf("X"); return ; } for(i=0;i<=num-1;i++) if(cat[i] * cat[num-1-i]<=tem) tem-=cat[i] * cat[num-1-i]; else break; if(i!=0){ printf("("); solve(i,tem/cat[num-1-i]); printf(")"); } printf("X"); if(i!=num-1){ printf("("); solve(num-1-i,tem%cat[num-1-i]); printf(")"); } } void cal(int n,int &rank,int &num){ int i; for(i=1;i<=20;i++) if(sum[i]>n){ rank=n-sum[i-1]; num=i; return ; } } void init(){ cat[0]=1; sum[1]=0; cat[1]=1; sum[1]=1; for(int i=1;i<=21;i++){ cat[i+1]=cat[i]*(4*i+2)/(i+2); //catalan递推关系 sum[i+1]=sum[i]+cat[i+1]; } } int main(){ int n,rank,num; init(); while(scanf("%d",&n) && n!=0){ cal(n-1,rank,num); solve(num,rank); //rank是从0开始的 printf("\n"); } }