poj 1095 Trees Made to Order

http://poj.org/problem?id=1095

先求出n个节点数的二叉树的形态有多少种。卡特兰数f[n]=f[n-1]*(4*n-2)/(n+1);再递归求。

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <algorithm>
 4 #define ll long long
 5 #define maxn 200
 6 using namespace std;
 7 
 8 ll f[maxn];
 9 int n,m;
10 
11 void inti()
12 {
13     f[0]=1;
14     for(int i=1; i<23; i++)
15     {
16         f[i]=f[i-1]*(4*i-2)/(i+1);
17     }
18 }
19 
20 void deal(int n,int k)
21 {
22     int i,sum=0;
23     if(n==1) {printf("X"); return ;}
24     for(i=0; sum+f[i]*f[n-1-i]<k; i++)
25     {
26         sum+=(f[i]*f[n-1-i]);
27     }
28     k-=sum;
29     if(i)
30     {
31         printf("(");
32         deal(i,(k-1)/f[n-1-i]+1);
33         printf(")");
34     }
35     printf("X");
36     if(i!=n-1)
37     {
38         printf("(");
39         deal(n-1-i,(k-1)%f[n-1-i]+1);
40         printf(")");
41     }
42 
43 }
44 
45 int main()
46 {
47     inti();
48     while(scanf("%d",&n)!=EOF)
49     {
50         if(n==0) break;
51         for(int i=1; ; i++)
52         {
53             if(n>f[i])
54             {
55                 n-=f[i];
56             }
57             else{
58                 m=i;
59                 break;
60             }
61         }
62         deal(m,n);
63         printf("
");
64     }
65     return 0;
66 }

View Code