请选择 进入手机版 | 继续访问电脑版
MSIPO技术圈 首页 IT技术 查看内容

北京大学考研机试题:二叉树

2023-07-13

【题目来源】
https://www.acwing.com/problem/content/description/3474/

【题目描述】

如上图所示,由正整数 1,2,3…… 组成了一颗特殊二叉树。
我们已知这个二叉树的最后一个结点是 n。
现在的问题是,结点 m 所在的子树中一共包括多少个结点。
比如,n=12,m=3 ,那么上图中的结点 13,14,15 以及后面的结点都是不存在的,结点 m 所在子树中包括的结点有 3,6,7,12,因此结点 m 的所在子树中共有 4 个结点。

【输入格式】
输入数据包括多行,每行给出一组测试数据,包括两个整数 m,n。
最后一行 0 0 表示输入结束。

【输出格式】
对于每一组测试数据,输出一行,该行包含一个整数,给出结点 m 所在子树中包括的结点的数目。

【数据范围】
1≤m≤n≤10^9,
最多包含 20 组数据。

【输入样例】
3 12
0 0

【输出样例】
4

【算法代码】

#include <bits/stdc++.h>
using namespace std;

int m,n;
int main(){
    while(cin>>m>>n) { //while(scanf("%d %d",&m,&n)!=EOF)
        if(m==0 && n==0) break;
        long long le=2*m;
        long long ri=2*m+1;
        int ans=1;
        int t=1;
        while(ri<=n){
            t*=2;
            ans+=t;
            le=le*2;
            ri=ri*2+1;
        }
        if(le<=n) ans=ans+n-le+1;
        cout<<ans<<endl;
    }
    return 0;
}

/*
in:
3 12
0 0

out:
4
*/





【参考文献】
https://www.acwing.com/solution/content/96273/
https://blog.csdn.net/hzyhfxt/article/details/83475168




 

相关阅读

手机版|MSIPO技术圈 皖ICP备19022944号-2

Copyright © 2024, msipo.com

返回顶部