首页 > ACM题库 > HDU-杭电 > HDU 3924-Extend-Tree-组合数学-[解题报告]HOJ
2015
04-14

HDU 3924-Extend-Tree-组合数学-[解题报告]HOJ

Extend-Tree

问题描述 :

There are many questions about the tree, most of them are Binary tree. But now, I’m tired of it. In this problem, we will not talk about the binary tree again, we discuss the tree which has three sub-trees, we called it extend tree;

The extend tree is orderly, it means that every integer n(n>=0) correspond to one unique extend tree and each extend tree correspond to one unique number. The tree is numbered using the following scheme:

1. The empty tree is numbered 0;
2. The single-node tree is numbered 1;
3. All extend trees that has m nodes correspond to a smaller integer than the tree which has more than m nodes.
4. Any extend tree having m nodes with left, mid and right sub-trees L ,M and R is numbered n; such that all trees having m nodes numbered > n have either Left sub-trees numbered higher than L, or A left sub-tree = L and a mid sub-tree numbered higher than M, or a left sub-tree = L a mid sub-tree = M and a right sub-tree numbered higher than R.

The first 18 extend trees are show below:

Invoker

Invoker

Invoker

Your job for this problem is to output a extend tree when its order number is given.

输入:

The first line contains a single positive integer T( T <= 3000 ), indicating the number of datasets.
Each instance consist of a single integer n, where 1<= n <=10^14.

输出:

The first line contains a single positive integer T( T <= 3000 ), indicating the number of datasets.
Each instance consist of a single integer n, where 1<= n <=10^14.

样例输入:

10
1
2
3
4
5
6
7
8
9
10

样例输出:

Case #1: X
Case #2: (X)X
Case #3: (X)X
Case #4: (X)X
Case #5: ((X)X)X
Case #6: ((X)X)X
Case #7: ((X)X)X
Case #8: (X)(X)X
Case #9: ((X)X)X
Case #10: ((X)X)X

这道题是poj1095的加强版

#include<stdio.h>
#include<math.h>
typedef long long ll;
ll a[30],s[30];
void init(){
	int i,j,k;
	a[0]=a[1]=1;
	s[0]=0;
	for(i=2;i<=20;i++)
		for(j=0;j<i;j++)
			for(k=0;k<=i-1-j;k++)
				a[i]+=a[j]*a[k]*a[i-1-j-k];
	for(i=1;i<=20;i++)
		s[i]=s[i-1]+a[i];
}
void cal(ll n,ll &rank,ll &num){
	int i;
	for(i=1;i<=20;i++)
		if(s[i]>n)
			break;
	rank=n-s[i-1];
	num=i;
}
void solve(ll num,ll rank){
	ll i,j,k;
	ll ii,jj,kk;
	ll ss,tem;
	if(num==1){
		printf("X");
		return ;
	}
	for(i=0;i<num;i++){
		for(ss=0,j=0;j<num-i;j++)
			ss+=a[j]*a[num-i-j-1];
		if(ss*a[i]>rank){
			ii=rank/ss;
			rank%=ss;
			break;
		}
		else
			rank-=ss*a[i];
	}
	for(j=0;j<num-i;j++){
		if(a[j]*a[num-i-1-j]>rank){
			break;
		}
		else
			rank-=a[j]*a[num-1-i-j];
	}
	if(i!=0){
		printf("(");
		solve(i,ii);
		printf(")");
	}
	if(j!=0){
		printf("(");
		solve(j,rank/a[num-1-i-j]);
		printf(")");
	}
	if(num-i-j-1!=0){
		printf("(");
		solve(num-1-i-j,rank%a[num-1-i-j]);
		printf(")");
	}
	printf("X");
}
int main(){
	int t,T;
	ll n,rank,num;
	//freopen( "E.in", "r", stdin );
	//freopen( "a.txt", "w", stdout );
	init();
	scanf("%d",&T);
	for(t=1;t<=T;t++){
		printf("Case #%d: ",t);
		scanf("%I64d",&n);        //%I64d被HDU坑死、、、、
		cal(n-1,rank,num);
		solve(num,rank);
		printf("\n");
	}
}

 

版权声明:本文为博主原创文章,未经博主允许不得转载。

参考:http://blog.csdn.net/waitfor_/article/details/7714699


  1. 老实说,这种方法就是穷举,复杂度是2^n,之所以能够AC是应为题目的测试数据有问题,要么数据量很小,要么能够得到k == t,否则即使n = 30,也要很久才能得出结果,本人亲测

  2. 站长,你好!
    你创办的的网站非常好,为我们学习算法练习编程提供了一个很好的平台,我想给你提个小建议,就是要能把每道题目的难度标出来就好了,这样我们学习起来会有一个循序渐进的过程!