文章
1
粉丝
219
获赞
0
访问
8.0k
注意到题目中的树具有特点:结点上的数通过右移操作可以得到所有祖先结点上的数
例如:14>>1=7; 7>>1=3; 3>>1=1
反过来通过左移操作可以得到完全二叉树的叶子结点的范围。通过子树高度计算完全树结点个数,然后比较n与叶子结点的范围,可直接计算出结果
代码:
#include <stdio.h>
int main(){
int n, m, th, sh, left, right, x, result;
while(scanf("%d%d", &m, &n) != EOF){
for(th = 0, x = n; x; th++)
x >>= 1;
for(sh = 0, x = m; x; sh++)
x >>= 1;
left = m << (th - sh);
right = ((m + 1) << (th - sh)) - 1;
if(left > n)
result = (1 << (th - sh)) - 1;
else if(right < n)
result = (1 << (th - sh + 1)) - 1;
else
...
登录后发布评论
暂无评论,来抢沙发