POJ 1095 Trees Made to Order(卡特兰数列)

题目链接

中间计算的各种细节。有的细节没处理好，就wa了。。。主要思路就是根据卡特兰数列的：

h(n)= h(0)*h(n-1)+h(1)*h(n-2) + ... + h(n-1)h(0) (n>=2)

 #include <cstdio>

 #include <string>

 #include <cstring>

 #include <queue>

 #include <map>

 #include <iostream>

 #include <algorithm>

 using namespace std;

 #define LL __int64

 LL ctl[];

 LL sum[];

 struct node

 {

     int l,r;

 }tree[];

 int t;

 void build(LL n,int rt)

 {

     int i,pos;

     if(n == ||n == )

     {

         return ;

     }

     for(i = ;i <= ;i ++)

     {

         if(sum[i] >= n)

         break;

     }

     pos = i;

     n -= sum[pos-];

     for(i = ;i <= pos-;i ++)

     {

         if(n <= ctl[i]*ctl[pos--i])

         break;

         n -= ctl[i]*ctl[pos--i];

     }

     if(i != )

     {

         tree[rt].l = t ++;

         if(n%ctl[pos--i] != )

         build(sum[i-]+n/ctl[pos--i]+,t-);

         else

         build(sum[i-]+n/ctl[pos--i],t-);

     }

     if(i != pos-)

     {

         tree[rt].r = t ++;

         if(n%ctl[pos--i] == )

         build(sum[pos--i]+ctl[pos--i],t-);

         else

         build(sum[pos--i]+n%ctl[pos--i],t-);

     }

 }

 void show(int x)

 {

     if(x == -)

     return ;

     if(tree[x].l != -)

     printf("(");

     show(tree[x].l);

     if(tree[x].l != -)

     printf(")");

     printf("X");

     if(tree[x].r != -)

     printf("(");

     show(tree[x].r);

     if(tree[x].r != -)

     printf(")");

 }

 int main()

 {

     int i;

     LL n;

     ctl[] = ;

     ctl[] = ;

     sum[] = ;

     for(i = ;i <= ;i ++)

     {

         ctl[i] = ctl[i-]*(*i-)/(i+);

         sum[i] = sum[i-] + ctl[i];

     }

     while(cin>>n)

     {

         if(n == ) break;

         t = ;

         for(i = ;i <= ;i ++)

         tree[i].l = tree[i].r = -;

         build(n,);

         show();

         printf("\n");

     }

     return ;

 }