构造完全二叉划分树

你现在有2ⁿ个数，分别为1,2,3,4,……，2ⁿ。Hang 想用这些数递归构造这样的一棵2ⁿ⁺¹个结点完全二叉划分树

这颗树的定义如下：

①一开始根节点有{1,2,3,4,……，2ⁿ_{} 全部这些数}。

②根据一定的规则R，对当前结点的数集做对半划分，拆成两个集合（集合内的数不要求相邻）。一个集合给左孩子，另一个集合给右孩子

③对左右孩子按照②的方式递归划分，直至集合中只剩一个数无法划分为止

④ Hang这个人太坏了，他定义的规则R是如下：

    我们定义max(A) 为集合A中的最大元素。 sum(A)为集合A中的所有元素之和。|A|为集合中的元素个数

    划分时，若A被拆分成两个集合B,C。其中B分给左子树，C分给右子树。则B,C应满足：|B|=|C|  and B∪C=A  and  B∩C=∅

    此外Hang还要求划分方法在满足max(A)∈C 的前提下，最大化sum(B)-sum(C)

这题是傻逼签到题，只要你能看得懂题目，并会找规律

这里给出一个n=3 时的划分案例

{1   2   3   4   5   6   7   8}

               /      \

{4   5   6   7}{ 1   2   3   8}

     /       \          /       \

{5   6} {4   7}{ 2   3}{ 1   8}

  /  \     /   \     /  \    /  \

{5} {6}{4} {7} {2} {3}{1} {8}

包含多组数据

每组输入占一行，只包含一个整数n

1<=n<=21

每组数据输出占一行，代表这颗完全二叉树叶子那层从左到右出现依次数字。

但是因为数字过多，输出有点慢，所以使用16进输出（字母必须大写）

并推荐使用快速输出模板：

char chset[]= "0123456789ABCDEF";

inline void Out(int a)    //输出一个整型

{

    if(a>15)

        Out(a>>4);

    putchar(chset[a&15]);

}

这题并不卡常，请尽量设计一个O(2ⁿ)的算法,而不是O(n*2ⁿ)的。因此请努力找规律，或者构造。

1
2
3
4
5

1 2
2 3 1 4
5 6 4 7 2 3 1 8
C D B E 9 A 8 F 5 6 4 7 2 3 1 10
1B 1C 1A 1D 18 19 17 1E 14 15 13 16 11 12 10 1F C D B E 9 A 8 F 5 6 4 7 2 3 1 20