首页 诗词 字典 板报 句子 名言 友答 励志 学校 网站地图
当前位置: 首页 > 教程频道 > 开发语言 > 编程 >

9度online judge 1543 二叉树

2013-10-07 
九度online judge 1543二叉树它的层次遍历结果如下:1/1, 1/2, 2/1, 1/3, 3/2, 2/3, 3/1,...有如下两类问题

九度online judge 1543 二叉树

它的层次遍历结果如下:
1/1, 1/2, 2/1, 1/3, 3/2, 2/3, 3/1,...
有如下两类问题:
1.找到层次遍历的第n个数字。如,n为2时,该数字为1/2;
2.给定一个数字p/q,输出它在层次遍历中的顺序,如p/q为1/2时,其顺序为2;

输入:

输入包含多组测试用例,输入的第一行为一个整数T,代表共有的测试用例数。
接下去T行每行代表一个测试用例,每个测试用例有如下两种类型
1.1 n。输出层次遍历中,第n个数字。
2.2 p q。输出p/q在层次遍历中的顺序。
1 ≤ n, p, q ≤ 2^64-1

输出:

对于每个测试用例,若其类型为1,输出两个整数p q,代表层次遍历中第n个数字为p/q。
若其类型为2,输出一个整数n,代表整数p/q在层次遍历的中的顺序n。
数据保证输出在[1,2^64-1]范围内。

样例输入:
41 22 1 21 52 3 2
样例输出:
1 223 25
本来以为这道题是找规律的,还是自己对二叉树的概念不熟悉,这道题涉及到usigned long long
#include<stdio.h>#include<iostream>#include<cstring>using namespace std;int visit[1000];int main(){int T,i,choice,num;unsigned long long sum,p,q,n;cin>>T;while(T--){num=0;sum=1;memset(visit,-1,sizeof(visit));cin>>choice;if(choice==1){   p=q=1;scanf("%llu",&n);while(n!=1){if(n%2==0){n=n/2;visit[num++]=0;}else{n=(n-1)/2;visit[num++]=1;}}for(i=num-1;i>=0;i--){if(visit[i]==0){q=p+q;p=p;}if(visit[i]==1){q=q;p=p+q;}}printf("%llu %llu\n",p,q); }if(choice==2){scanf("%llu%llu",&p,&q);while(p-q!=0){if(p>q){visit[num++]=1;p=p-q;q=q;}if(p<q){visit[num++]=0;p=p;q=q-p;}}for(i=num-1;i>=0;i--){if(visit[i]==0){sum=sum*2;}if(visit[i]==1){sum=sum*2+1;}}printf("%llu\n",sum);}}return 0;}


热点排行