poj-1095-Trees Made to Order

调试了一晚上，终于对了。。

整个晚上竟然都没有发现取数之前没有+1，太气人了。。

用dos（i,j,k)

代表：子树的根节点为i，一共有j个节点的第k大的树。

#include
  
   
#include
   
     #include
    
      #include
     
       #include
      
        #include
       
         #define LL long long #define MAXN 550000000 using namespace std; LL dp[201]; LL ans[201]; struct list { LL l,r; }node[51]; void init() { LL i,j; memset(dp,0,sizeof(dp)); dp[0]=1; dp[1]=1; for(i=2;;i++) { for(j=0;j<=i-1;j++) { dp[i]=dp[i]+dp[j]*dp[i-j-1]; } if(dp[i]>MAXN)break; } for(j=1;j<=i;j++)ans[j]=ans[j-1]+dp[j]; } void dos(LL x,LL n,LL shu) { if(shu==0)return; if(n==0)return; node[x].l=0; node[x].r=0; LL ff; ff=0; LL i; for(i=0;i<=n-1;i++) { ff+=dp[i]*dp[n-1-i]; if(ff>=shu) { ff=shu-(ff-dp[i]*dp[n-1-i]); LL ks; ff--; ks=ff/(dp[n-1-i]); ff++; ks++; dos(x+1,i,ks); if(i)node[x].l=x+1; ks=ff%(dp[n-1-i]); if(ks==0)ks=dp[n-1-i]; dos(x+1+i,n-1-i,ks); if(n-1-i)node[x].r=x+1+i; return; } } } string lian(int x) { string ss; if(node[x].l)ss=ss+"("+lian(node[x].l)+")"; ss=ss+"X"; if(node[x].r)ss=ss+"("+lian(node[x].r)+")"; return ss; } int main() { LL n,i; init(); while(~scanf("%I64d",&n)&&n) { for(i=1;;i++) { if(ans[i]>=n)break; } dos(0,i,n-ans[i-1]); string str; str=lian(0); cout<