Dropping Balls UVA - 679(二叉树的遍历)

题目链接:https://vjudge.net/problem/UVA-679

Dropping Balls UVA - 679(二叉树的遍历)

Dropping Balls UVA - 679(二叉树的遍历)

题目大意:t组样例,每组包括D M   层数是D   问第M个小球落在哪个叶子节点?    每个节点有开关  刚开始全都是关闭的,小球走到节点  节点开关变为与当前相反   每个小球从根节点释放

思路:这题是第一道二叉树遍历的题目,二叉树暴力模拟的确可以求出答案 ,但是很不幸,会超时

然后另一种方法,只需要求第M次小球就行了!  怎么求呢?   试想一下,如果M为奇数 那么从根节点开始看,肯定是往左走(M+1)/2次  往右走M/2次  但是最后一次肯定是往左走的

同理,如果M是偶数  显然 往左走M/2次  往右走 M/2次   显然最后一次是往右走的    这就是做这题的思想了  然后往复此过程 !

看代码:

#include<iostream>
using namespace std;
int main()
{
int t;
int n,m;
while(cin>>t)
{
if(t==-) break;
while(t--)
{
int ans=;
cin>>n>>m;
for(int i=;i<n;i++)//
{
if(m%==) //最后一次肯定往左子树走 且走的次数为(m+1)/2
{
m=(m+)/;
ans=ans<<;
}
else//往右子树走
{
m=m/;
ans=ans<<|;
}
}
cout<<ans<<endl;
} }
return ;
}
上一篇:UVa 679 - Dropping Balls【二叉树】【思维题】


下一篇:UVA.699 The Falling Leaves (二叉树 思维题)