6 6_droping_balls_uva679 - nuaazdh/acm GitHub Wiki

##例题6-6 小球下落(Droping Balls UVa679) ###问题 一个完全二叉树（FBT），每个节点都有一个状态，初始都为 false，假设一个小球从根节点（编号为1）开始下落，经过任何一个结点，若为 false，则转向左子树，否则转向右子树，并改变当前节点的状态值。 给定二叉树的深度D和放入的小球的编号I，求小球最终落入的叶子节点的编号

###分析 FBT可以用数组来表示，那么最直接的想法就是模拟这个过程。

###code in C++

#include <iostream>

char btree[(1 << 20)];

int main() {
    int T;
    while (std::cin >> T && T != -1) {
        for (int i = 0; i < T; ++i) {
            int D, I;
            std::cin >> D >> I;
            memset(btree, 0, sizeof(btree));
            int last_pos = 1;
            for (int j = 1; j <= I; ++j) {
                last_pos = 1;
                while (last_pos < (1 << (D - 1))) {
                    if (btree[last_pos] & 0x01) {//true
                        btree[last_pos] &= 0;
                        last_pos <<= 1;
                        last_pos++;
                    } else {
                        btree[last_pos] |= 0x01;
                        last_pos <<= 1;
                    }
                }//while
            }//for j
            std::cout << last_pos << "\n";
        }//for i
    }
    return 0;
}

###点评 虽然已经用 char类型的数组（比int型节约内存）,但还是TEL超时。

###改进 分析小球运动规律，第一层，奇数向左，偶数向右。到第二层，位于奇数位置的奇数（如1，3）向左，偶数位置的奇数第二层向右（如5，7），同样的，奇数位置的偶数第二层向左…… ###code in C

#include <stdio.h>

int drop_ball(int D, int I) {
    int i, pos = 1;
    for (i = 0; i < D - 1; ++i) {
        pos <<= 1;
        if (I & 0x01) {
        } else {
            ++pos;
        }
        I = (I + 1) / 2;
    }
    return pos;
}

int main() {
    int T,D,I,i;
    while (scanf("%d",&T) == 1 && T != -1) {
        for (i = 0; i < T; ++i) {
            scanf("%d%d",&D,&I);
            printf("%d\n",drop_ball(D,I));
        }
    }
    return 0;
}
⚠️ **GitHub.com Fallback** ⚠️