(File IO): input:five.in output:five.out
时间限制: 1000 ms 空间限制: 262144 KB 具体限制
题目描述
有一棵满二叉树，最大深度为D，且所有叶子的深度都相同。所有结点从上到下从左到右编号为1，2，3，…，2^D-1。在结点1处放一个小球，它会往下落。每个内结点上都有一个开关，初始全部关闭，当每次有小球落到一个开关上时，它的状态都会改变。当小球到达一个内结点时，如果该结点上的开关关闭，则往左走，否者往右走，直到走到叶子结点。
一些小球从结点1处依次开始下落，最后一个小球将会落到哪里呢？
输入
输入文件five.in
只有一行共有二个正整数：d k （其中d为叶子深度，k为小球个数，1 <= k <= 2^(d-1) ）
输出
输出文件five.out
只有一行且只有一个正整数：第k个小球最后所在的叶子编号
样例输入
16 12345
样例输出
36358
数据范围限制
50% 的数据: 1 <= d <= 40
80% 的数据: 1 <= d <= 60
100% 的数据: 1 <= d <= 100
思路： 这道题其实也不算难，只是高精度乘除分。
首先，我们了解一下上面那个链接，然后再推一下满二叉树的特性：
1）叶子只能出现在最下一层。出现在其它层就不可能达成平衡。
2）非叶子结点的度一定是2，即他们的下一层都有两个结点。
3）在同样深度的二叉树中，满二叉树的结点个数最多，叶子数最多。
4）对于除却根结点的任意结点，父亲结点都为i/2,左子树为2i，右子树为2i+1。（重点）
对于每一个球，我们都能推出他应该向左还是向右，所以利用4），我们就能得到其最后球最后在哪个结点。
代码：
#include<bits/stdc++.h>
using namespace std;
long long d,k[10005],a[10005],js=1;
char f;
int main(){
freopen("five.in","r",stdin);
freopen("five.out","w",stdout);
scanf("%d",&d);
cin>>f;
while(f>='0'&&f<='9'){
k[0]+=1;
k[k[0]]=f-'0';
f=getchar();
}
a[0]=1;
a[1]=1;
for(int i=1;i<d;i++){
for(int j=1;j<=a[0];j++){
a[j]*=2;
}
for(int j=1;j<=a[0]+1;j++){
a[j+1]+=a[j]/10;
a[j]=a[j]%10;
}
if(k[k[0]]%2==0){
a[1]++;
for(int j=1;j<=a[0];j++){
a[j+1]+=a[j]/10;
a[j]=a[j]%10;
}
}
if(a[a[0]+1]!=0){
a[0]++;
}
int bj=0;
if(k[k[0]]%2==1) k[k[0]]+=1;
for(int j=js;j<=k[0];j++){
k[j+1]+=k[j]%2*10;
if(k[j]/2!=0||bj==1){
k[j]=k[j]/2;
bj=1;
}
else if(bj==0) js++;;
}
}
for(int i=a[0];i>=1;i--){
printf("%d",a[i]);
}
fclose(stdin);
fclose(stdout);
return 0;
}
写博不易，请发现问题的大佬提出。
代码保证正确，请留赞再走。