首页 > ACM题库 > HDU-杭电 > HDU 1100 Trees Made to Order-组合数学-[解题报告] C++
2013
11-27

HDU 1100 Trees Made to Order-组合数学-[解题报告] C++

Trees Made to Order

问题描述 :

We can number binary trees using the following scheme:
The empty tree is numbered 0.
The single-node tree is numbered 1.
All binary trees having m nodes have numbers less than all those having m+1 nodes.
Any binary tree having m nodes with left and right subtrees L and R is numbered n such that all trees having m nodes numbered > n have either
Left subtrees numbered higher than L, or
A left subtree = L and a right subtree numbered higher than R.The first 10 binary trees and tree number 20 in this sequence are shown below:
Your job for this problem is to output a binary tree when given its order number.

输入:

Input consists of multiple problem instances. Each instance consists of a single integer n, where 1 <= n <= 500,000,000. A value of n = 0 terminates input. (Note that this means you will never have to output the empty tree.)

输出:

For each problem instance, you should output one line containing the tree corresponding to the order number for that instance. To print out the tree, use the following scheme:A tree with no children should be output as X.
A tree with left and right subtrees L and R should be output as (L’)X(R’), where L’ and R’ are the representations of L and R.
If L is empty, just output X(R’).
If R is empty, just output (L’)X.

样例输入:

1
20
31117532
0

样例输出:

X
((X)X(X))X
(X(X(((X(X))X(X))X(X))))X(((X((X)X((X)X)))X)X)

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

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

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

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

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

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

 

参考代码:

#include <cstdio>
 #include <cstring>

 typedef __int64 ll;
 const int maxn = 20;
 const ll maxsum = 500000000;
 ll tri[maxn << 1][maxn << 1];
 ll sum[maxn], rec[maxn];
 int cur, l[maxn], r[maxn];

 void build(){
     memset(tri, 0, sizeof(tri));
     tri[0][0] = 1;
     for (int i = 1; i < maxn << 1; i++){
         tri[i][0] = 1;
         for (int j = 1; j <= i; j++){
             tri[i][j] = tri[i - 1][j - 1] + tri[i - 1][j];
         }
     }
     sum[0] = rec[0] = 1;
     for (int i = 1; i < maxn; i++){
         rec[i] = tri[i << 1][i] / (i + 1);
         sum[i] = sum[i - 1] + rec[i];
 #ifndef ONLINE_JUDGE
         printf("%2d : %12I64d %12I64d\n", i, sum[i], rec[i]);
 #endif
     }
 }

 void con(int rt, int rest, int cnt){
     if (rest == 1 && cnt == 1){
         return ;
     }
     cnt--;
     for (int i = 0; i <= cnt; i++){
         int tmp = rec[i] * rec[cnt - i];

         if (rest > tmp) rest -= tmp;
         else{
             int lrest = (rest - 1) / rec[cnt - i] + 1;
             int rrest = (rest - 1) % rec[cnt - i] + 1;

             if (i){
                 l[rt] = ++cur;
                 con(cur, lrest, i);
             }
             if (cnt - i){
                 r[rt] = ++cur;
                 con(cur, rrest, cnt - i);
             }

             break;
         }
     }
 }

 void print(int rt){
     if (~l[rt]){
         putchar('(');
         print(l[rt]);
         putchar(')');
     }
     putchar('X');
     if (~r[rt]){
         putchar('(');
         print(r[rt]);
         putchar(')');
     }
 }

 void deal(int n){
     int cnt = 0;

     while (n >= sum[cnt]) cnt++;
 #ifndef ONLINE_JUDGE
     printf("%d\n", cnt);
 #endif
     for (int i = 0; i < cnt; i++)
         l[i] = r[i] = -1;
     cur = 0;
     n -= sum[cnt - 1] - 1;
     con(0, n, cnt);
     print(0);
     puts("");
 }

 int main(){
     int n;

     build();
     while (~scanf("%d", &n) && n)
         deal(n);

     return 0;
 }

 

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

 

——written by Lyon


  1. a是根先忽略掉,递归子树。剩下前缀bejkcfghid和后缀jkebfghicd,分拆的原则的是每个子树前缀和后缀的节点个数是一样的,根节点出现在前缀的第一个,后缀的最后一个。根节点b出现后缀的第四个位置,则第一部分为四个节点,前缀bejk,后缀jkeb,剩下的c出现在后缀的倒数第2个,就划分为cfghi和 fghic,第3部分就为c、c

  2. 博主您好,这是一个内容十分优秀的博客,而且界面也非常漂亮。但是为什么博客的响应速度这么慢,虽然博客的主机在国外,但是我开启VPN还是经常响应很久,再者打开某些页面经常会出现数据库连接出错的提示