这不是一道什么竞赛题目,就是刘汝佳老师在算法竞赛入门经典中给的关于二叉树的例子。自己写了一下,附到博客园上面来供自己回忆;
第一种解法是设了一个ok判断球是往左还是往右,但是要开一个2^20的数组,用来记录每个位置的0/1开关情况。这个代码很简单,在书的100页有详细的讲解。
View Code
1 #include<stdio.h> 2 #include<string.h> 3 #define max 20 4 int str[1<<max]; 5 int ok; 6 int main() 7 { 8 int a,b; 9 while(scanf("%d%d",&a,&b) == 2) 10 { 11 memset(str,0,sizeof(str)); 12 int k=0,n; 13 n=(1<<a)-1; 14 for(;k<b;k++) 15 { 16 ok=1; 17 for(;;) 18 { 19 str[ok] = !str[ok]; 20 ok=str[ok]?2*ok:2*ok+1; 21 if(ok>n) break; 22 } 23 } 24 printf("%d\n",ok/2); 25 } 26 return 0; 27 }
然后看刘老师讲了一种优化解法:利用那个数字的奇偶性来判断在第几个节点落在跟的左子树里。从而判断位置,不太好说,自己得好好想想。
View Code
1 #include<stdio.h> 2 #include<string.h> 3 int main() 4 { 5 int line,ball; 6 int ok,i,j; 7 while(scanf("%d%d",&line,&ball) == 2) 8 { 9 ok=1; 10 for(i=0;i<line-1;i++) 11 { 12 if(ball%2) 13 { 14 ok=2*ok; 15 ball=(ball+1)/2; 16 } 17 else 18 { 19 ok=2*ok+1; 20 ball/=2; 21 } 22 } 23 printf("%d",ok); 24 } 25 }