首页 > 代码库 > UVa679 Dropping Balls (二叉树)
UVa679 Dropping Balls (二叉树)
链接：http://acm.hust.edu.cn/vjudge/problem/19499
分析：二叉树的递归定义:二叉树要么为空，要么有根节点、左子树和右子树组成，而左右子树分别是一棵二叉树。本题来说，对于一个根节点，当奇数次小球到达时，小球往左走，k*=2,且当前到达左子树小球个数是到达根节点小球个数的（I+1）/2,当偶数次小球到达此根节点时，小球往右走，k=k*2+1,然后当前往右边走到达右子树根结点的小球总个数为I/=2，就这样递归进行直到到达叶子结点。
1 #include <cstdio> 2 3 int main() { 4 int T; 5 scanf("%d", &T); 6 while (T--) { 7 int D, I; 8 scanf("%d%d", &D, &I); 9 int k = 1;10 for (int i = 0; i < D - 1; i++) {11 if (I % 2) { k *= 2; I = (I + 1) / 2; }12 else { k = k * 2 + 1; I /= 2; }13 }14 printf("%d\n", k);15 }16 return 0;17 }
UVa679 Dropping Balls (二叉树)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。