文章

1

粉丝

219

获赞

0

访问

7.6k

头像
算术方法
P1264 北京大学机试题
发布于2021年3月6日 20:21
阅读数 7.6k

注意到题目中的树具有特点:结点上的数通过右移操作可以得到所有祖先结点上的数

例如: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
...

登录查看完整内容


登录后发布评论

暂无评论,来抢沙发