Dropping Balls UVA - 679（二叉树的遍历）

题目链接：https://vjudge.net/problem/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 ;

}

巴特西

Dropping Balls UVA - 679（二叉树的遍历）

最新文章

热门文章