- 题目1543：无限完全二叉树的层次遍历
-
时间限制：1 秒
内存限制：128 兆
特殊判题：否
提交：389
解决：54
- 题目描述：
-
有一棵无限完全二叉树，他的根节点是1/1,且任意一个节点p/q的左儿子节点和右儿子节点分别是，p/(p+q)和(p+q)/q。如下图：
它的层次遍历结果如下：
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]范围内。
- 样例输入：
-
4 1 2 2 1 2 1 5 2 3 2
- 样例输出：
-
1 2 2 3 2 5
- 本来以为这道题是找规律的，还是自己对二叉树的概念不熟悉，这道题涉及到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; }