UVa-679 Dropping Balls 二叉树

题意：

有一棵二叉树，所有节点从上至下，从左到右依次编号为1、2...2^D-1，叶子深度都相同，有I个小球，从根节点依次下落，若通过某一节点时节点状态为关闭，则小球向左走，否则向右走，直到叶节点。刚开始所有节点都是关闭的，问最后一个小球会落在哪里（即所在叶节点编号）

分析：

① 首先想到模拟I个小球的下落过程，但结果肯定是TLE，因为I可高达2¹⁹，每一个小球最多下落19层，所以每组测试总下落次数可达2¹⁹*19次，测试数据又最多有1000组。

②然后找规律，发现可直接根据I计算出最后的位置：对于某一个小球，如果它是第X个到达某一节点的，若X为奇数，则此球会向左走，此时它是第(X+1) / 2个到达下一位置的小球，若X为偶数则向右走，此时它是第X / 2个到达下一位置的。所以这道题可直接对于第I个小球只进行一趟循环，通过上述规则不断确定要走的方向，最后求得落到的叶节点的编号。

代码如下

//Uva-679

#include <iostream>

#include <cstdio>

using namespace std;

int main(void) {

    int D, I;

    int n;

    scanf("%d", &n);

    while(n--) {

        scanf("%d%d", &D, &I);

        int k = ;

        for(int i = ; i < D-; i++) { //直接模拟最后一个小球的运动，一共需要下落D-1层

            if(I %  != ) {//判断这是第几个到达这一层此位置的小球，若为奇数，则向左走

                k = *k;

                I = (I+) / ;// 这是此位置第 (I+1) / 2个向左走的小球

            }

            else {//为偶数，则向右走

                k = *k + ;

                I = I / ;//这是第I/2个向右走的小球

            }

        }

        printf("%d\n", k);

    }

}

巴特西

UVa-679 Dropping Balls 二叉树

最新文章

热门文章