首页 > 代码库 > wenbao与二叉树
wenbao与二叉树
二叉树
结点k的左右结点分别为 2k 和 2k+1
小球下落
将小球放在第一个节点上下落，每个点都有一个开关（小球落在该点时状态就会改变），当该点关闭往左走，否则往右走，求第 I 个小球落在那个节点上
直接按照题意模拟
1 #include <cstdio> 2 #include <cstring> 3 using namespace std; 4 const int maxn = 20; 5 int s[1<<maxn]; 6 int main(){ 7 int D,I; 8 while(scanf("%d%d", &D, &I) == 2){ 9 memset(s,0,sizeof(s));10 int k, n = (1<<D)-1;11 for(int i = 0; i < I; i++){12 k = 1;13 for(; ; ){14 s[k] = !s[k];15 k = s[k] ? k*2 : k*2+1;16 if(k > n) break;17 }18 }19 printf("%d\n", k/2);20 }21 return 0;22 }
如果继续观察的话就会发现其中的规律，每个奇偶性不同的球落的左右也不一样
只要知道该小球是第几个落在节点上就可以知道该点开关的闭合，即小球的左右
这样就可以节省许多的时间和不必要的数组
1 #include <cstdio> 2 #include <cstring> 3 using namespace std; 4 int main(){ 5 int D,I; 6 while(scanf("%d%d", &D, &I) == 2){ 7 int k = 1; 8 for(int i = 0; i < D-1; i++){ 9 if(I&1){10 k = k*2 ; I = (I+1)/2;11 }12 else{13 k = k*2+1; I/=2;14 }15 }16 printf("%d\n", k);17 }18 return 0;19 }
wenbao与二叉树
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。