UVa679 Dropping Balls (满二叉树+开关灯思想)

题目链接

1. 刚开始模拟了一下两个深度分别为3和4的样例，然后就发现在第i层中，首先落下的2^i-2次都是偶数且这2^i-2中按奇偶数来分正好是把左一半右一半的偶数叶子节点逐一遍历，同理接下来的2^i-2次都是奇数。然后直接写了一个规律的模拟，过了样例，交——WA。又读了一遍题，发现小球数目是任意的，而我刚开始按最多2^i-1次个小球来考虑了。
2. 读了几遍标答，手动模拟，搞懂了。以前做过开关灯的问题，和这个确实有思想上的类似的，可以对比着想。
3. 想去看下大神们有没有什么更好的理解，确实有。某博客：类似哈夫曼编码，第i个球走的路径是i-1二进制数的逆序。0代表左子树，1代表右子树。并由右向左走D-1次即可。（现在还看不懂，等以后搞懂了再来补充）
4. 关于代码中的位运算，如果看不懂可先参考这个博客

标答：

#include <iostream>
using namespace std;
int main(){
    int T,d,I;
    while(scanf("%d",&T)!=EOF){
        if(T==-1) break;
        while(T--){
            scanf("%d%d",&d,&I);
            int ans=1;
            for(int i=0;i<d-1;i++){	///写位运算可大大节省时间
                if(I&1){
                    ans<<=1;
                    I=(I+1)>>1;
                }else{
                    ans=(ans<<1)+1;
                    I>>=1;
                }
            }
            printf("%d\n",ans);
        }
    }
    return 0;
}

哈夫曼思想：

#include <cstdio>
#include <iostream>
using namespace std;
int main(){
    int T,p,q;
    while(scanf("%d",&T)!=EOF){
        if(T==-1) break;
        while(T--){
            scanf("%d%d",&p,&q);
            int x=q-1;
            int ans=1;
            while(--p){
                if(x&1){    ///判断最后一位是否为1，也可当做奇数偶数的判断
                    ans=(ans<<1)+1;
                }else ans<<=1;
                x>>=1;
            }
            printf("%d\n",ans);
        }
    }
        return 0;
}