Uva 679 Dropping Ballls 二叉树的编号

这个程序常规处理起来数据量很大，I可以高达2^D-1

/*

…….

*/

里面的代码块据此避免了开太大的数组

做太多的循环

#include<cstdio>
#include<cstring>
const int maxd=20;
int s[1<<maxd];//最大结点数2^maxd-1
int main(){
int D,I;
/*
while(scanf("%d%d",&D,&I)==2){
int k=1;
for(int i=0;i<D-1;i++)
对I作判断，这里I是当前结点所遇到的第I个小球
if(I&1){
k=2*k;
I=(I+1)/2;//I奇数，第(I+1)/2个往左走
}
else{
k=k*2+1;
I/=2;//I偶数,第I个往右走
}
printf("%d",&k);//到达D-1层即叶子结点则输出K
}
    */
while(scanf("%d%d",&D,&I)==2){
memset(s,0,sizeof(s));
int k,/*当前小球所在结点编号*/n=(1<<D)-1;//最大结点编号
for(int i=0;i<I;i++){
k=1;//从第一个结点开始
for(;;){
s[k]=!s[k];
k=s[k]?2*k:2*k+1;//闭左开右
if(k>n) break;//出界
}
}
printf("%d",k/2);//到叶子结点中去找原来的父结点
}
return 0;
}