hdu 1100 Trees Made to Order

http://acm.hdu.edu.cn/showproblem.php?pid=1100

　　今晚做了一下标记为组合数学的题。这题归类组合数学应该是因为这题用到二叉树计数的原理吧。这次是完全没有参考其他资料的了~

　　稍微解释一下题意，这题就是将二叉树标号，然后给出标号，让你画出二叉树来。标号的规则比较长，总的来说就是结点多的标号大，左结点标号大的大，如果左结点标号相同，右结点标号大的大。

　　刚开始的时候，我就光靠数字和图形间的关系来推测构图的方法，然后发现要解这题必须要找到根本，就是二叉树计数。然后我就打了个卡特兰数的表，用来关联题目的条件。这时可以找到一个方法来找出左右子树的模样。

　　我描述一下方法：因为二叉树计数的递推是依靠左右子树的组合数来产生的，如果按照那种递推方法，将标号不停的减少，最后可以找到左右子树分别有多少个结点。然后，剩余量就是指在该组中是第几种组合方式。接着就是要计算左右子树分别属于它的数量中的第几种组合方式。刚刚说了一下题意，可以发现要右子树变到没得变，左子树才会改变一次，这就是我的代码中取模的操作，得到lrest和rrest。之后的每一个子结点都按照这种方法来找到左右子树的模样，因此我就进行递归的操作。从而得到树的模样！

　　最后输出的时候就是一个中序遍历输出，整体基本完成了！

参考代码：

View Code

 1 #include <cstdio>
 2 #include <cstring>
 3 
 4 typedef __int64 ll;
 5 const int maxn = 20;
 6 const ll maxsum = 500000000;
 7 ll tri[maxn << 1][maxn << 1];
 8 ll sum[maxn], rec[maxn];
 9 int cur, l[maxn], r[maxn];
10 
11 void build(){
12     memset(tri, 0, sizeof(tri));
13     tri[0][0] = 1;
14     for (int i = 1; i < maxn << 1; i++){
15         tri[i][0] = 1;
16         for (int j = 1; j <= i; j++){
17             tri[i][j] = tri[i - 1][j - 1] + tri[i - 1][j];
18         }
19     }
20     sum[0] = rec[0] = 1;
21     for (int i = 1; i < maxn; i++){
22         rec[i] = tri[i << 1][i] / (i + 1);
23         sum[i] = sum[i - 1] + rec[i];
24 #ifndef ONLINE_JUDGE
25         printf("%2d : %12I64d %12I64d\n", i, sum[i], rec[i]);
26 #endif
27     }
28 }
29 
30 void con(int rt, int rest, int cnt){
31     if (rest == 1 && cnt == 1){
32         return ;
33     }
34     cnt--;
35     for (int i = 0; i <= cnt; i++){
36         int tmp = rec[i] * rec[cnt - i];
37 
38 
39         if (rest > tmp) rest -= tmp;
40         else{
41             int lrest = (rest - 1) / rec[cnt - i] + 1;
42             int rrest = (rest - 1) % rec[cnt - i] + 1;
43 
44             if (i){
45                 l[rt] = ++cur;
46                 con(cur, lrest, i);
47             }
48             if (cnt - i){
49                 r[rt] = ++cur;
50                 con(cur, rrest, cnt - i);
51             }
52 
53             break;
54         }
55     }
56 }
57 
58 void print(int rt){
59     if (~l[rt]){
60         putchar('(');
61         print(l[rt]);
62         putchar(')');
63     }
64     putchar('X');
65     if (~r[rt]){
66         putchar('(');
67         print(r[rt]);
68         putchar(')');
69     }
70 }
71 
72 void deal(int n){
73     int cnt = 0;
74 
75     while (n >= sum[cnt]) cnt++;
76 #ifndef ONLINE_JUDGE
77     printf("%d\n", cnt);
78 #endif
79     for (int i = 0; i < cnt; i++)
80         l[i] = r[i] = -1;
81     cur = 0;
82     n -= sum[cnt - 1] - 1;
83     con(0, n, cnt);
84     print(0);
85     puts("");
86 }
87 
88 int main(){
89     int n;
90 
91     build();
92     while (~scanf("%d", &n) && n)
93         deal(n);
94 
95     return 0;
96 }

　　还是要多做组合数学的题来加快推理的速度啊！

——written by Lyon