UVa 679 - Dropping Balls【二叉树】【思维题】

题目链接

题目大意:

小球从一棵所有叶子深度相同的二叉树的顶点开始向下落,树开始所有节点都为0。若小球落到节点为0的则往左落,否则向右落。并且小球会改变它经过的节点,0变1,1变0。给定树的深度D和球的个数I,问第I个小球会最终落到哪个叶子节点。

解题思路:

完全二叉树有一个重要的性质:对于任意一个节点k,其左节点、右节点的编号分别为2k和2k+1

对于根节点,很容易知道当球的编号为奇数时,球落入左子树,偶数时落在右子树。这样其实对于其它节点看成根节点时也是一样的。比如对于第7个球,为奇数,是第7个到达一号节点的球,也是第(7/2)+1=4个到达2号节点球,再往下也是第2个到达5号节点的球。。。。

所以可以直接通过找规律,模拟最后一个球的判断过程

这是我的AC代码

#include <cstdio>
typedef long long ll;
ll d, n; int main()
{
int cur;
while (scanf("%d", &cur) != EOF,cur!=-)
{
while (cur--)
{
scanf("%lld%lld", &d, &n);
int height = ;
ll num = ;
while (height < d) //从深度为1的根节点到达深度为d的叶子总共需要判断d-1次
{
if (n % == ) //当球的编号为偶数的时候
{
num = num * + ;
n = n / ;
height++;
}
else //当球的编号为奇数的时候
{
num = num * ;
n = (n + ) / ;
height++;
}
}
printf("%lld\n", num);
}
}
return ;
}

以下更为精简的代码,和两种思路

数学思路

#include<stdio.h>

int main()
{
int D, I,cas;
while (scanf("%d", &cas) != EOF,cas!=-1)
{
while (cas--)
{
scanf("%d%d", &D, &I);
int k = ;
for (int i = ; i < D - ; i++)
{
if (I % ) //奇数
{
k = * k;
I = (I + ) / ;
}
else {
k = * k + ;
I = I / ;
}
}
printf("%d\n", k);
}
}
return ;
}

模拟下落过程

#include<stdio.h>
#include<string.h>
const int MAXD = ;
int s[<<MAXD]; //最大节点个数 2^MAXD - 1 int main()
{
int D, I,cas;
while (scanf("%d", &cas) != EOF,cas!=-1)
{
while (cas--)
{
scanf("%d%d", &D, &I);
memset(s, , sizeof(s)); //开关初始全0,表示关闭
int k, n = ( << D) - ; //k表示下落到的节点的开关下标
for (int i = ; i < I; i++) //共下落I个小球
{
k = ;
while ()
{
s[k] = !s[k];
k = s[k] ? * k : * k + ; //根据开关选择左右子树
if (k > n) break; //落到树外,出界
}
}
printf("%d\n", k / ); //出界前叶子节点编号
}
}
return ;
}

2018-03-31

上一篇:sql server版本、组件和管理工具


下一篇:Dropping Balls UVA - 679(二叉树的遍历)