2043646 2006-08-26 14:29:40 Accepted 1062 C++ 00:00.00 432K St.Crux 给出一个N，求中序树形。 Sample Input 120311175320 Sample Output X((X)X(X))X(X(X(((X(X))X(X))X(X))))X(((X((X)X((X)X)))X)X) 这个题的思想是不断逼近。要构造一颗树，（最好）要知道他的左子树序列号和右子树序列号。这个一下子求不出来，但是我们可以先看一下能求出的东西。 N个节点数这儿有几棵树。An= C(2n, n) / (n + 1)，这个可以求，打一个表就可。且可求得N<20。 N这整棵树是几个节点。这个就好求了。用An一个一个的依次减，马上就求出来。减出来的数还得存着，待会儿还得减。 左子树几个节点。这个有点技巧了。这要明白一规律，当左子树有l个节点，右子树r个节点时，这样的树有几棵。答案是Al * Ar。这是全题的关键。而且这树是按左子树的节点树依次排下来的。这就好办了，和上面一样，一个一个挨个减下来。算出来以后右子树也出来了。这就是左子树的节点数和右子树的结点数。 最后就是这个序列号了。就拿这4,5,6,7,8来说吧。减到现在，就成了0,1,0,0,1。这有什么规律呢？没错，0,1分别是2号和3号在他们那一组（2棵树的）里的序列号。现在要用数学公式来说的话，就是： 设Sl为左边的序列号（在他们那一组里的，以下同）Sr为右边的，Al是左边节点数树的总个数，Ar同，t是N减到现在还剩的那个数。则可得：Sl = t / Ar, Sr = t  % Ar。因为每棵树是从右开始排，填满了Ar * Al种排法就结束，换到下一种Ar －1的排法里去了，也不归这个排法的管了。左边呢？就Al种排法，一个一个来，比作齿轮的话，就先得让右边的Ar轮一遍，才轮到他动一格。于是这个题就变成简单的排列组合了。 具体的算法边界处还得考虑，这个也是挺麻烦的一个地方。 #include <cstdio> int a[20] = { 1, 1, 2, 5, 14, 42, 132,  429, 1430, 4862, 16796, 58786, 208012,  742900, 2674440, 9694845, 35357670,  129644790, 477638700 }, b[20], n; void dfs(int x){ int s, l, r, i, t = x, xl, xr; for(i = 0; i < 20; i ++) {  if(t < a[i])   break;  t -= a[i]; } s = i - 1; for(i = 0; i <= s; i ++) {  if(t < a[i] * a[s - i])   break;  t -= a[i] * a[s - i]; } l = i, r = s - i; xl = t / a[r] + b[l], xr = t % a[r] + b[r]; if(xl) {  printf("(");  dfs(xl);  printf(")"); } printf("X"); if(xr) {  printf("(");  dfs(xr);  printf(")"); }}  void init(){ int i, t = 0; b[0] = 0; for(i = 0; i < 19; i ++) {  t += a[i];  b[i + 1] = t; }} int main(){ //freopen("in.txt", "r", stdin); init(); while(scanf("%d", &n) && n) {  dfs(n);  printf("\n"); } return 0;}    

评论