C小加

厚德 博学 求真 至善 The bright moon and breeze
posts - 145, comments - 195, trackbacks - 0, articles - 0
  C++博客 :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理

这道题纠结我了一天的时间,本以为用lowbit可以轻松搞定,可是中间出现了各种故障,WA了很多次才AC

计算ab之间的节点数,可以用1-a1-b的节点数之差来求。在右子树的点可以转化为相应的左子树的点,经过多步骤的转化,可以把点的位置固定在树的最左边的那条线上。所以只需要计算每层最左边的节点数就OK了。经过递推会得出一个公式,z[i]=z[i-1]*2+i-1;i表示树的高度。

#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
typedef long long ll;
ll z[33]={0};//从1到n经过的点
ll d[33]={0};//树每层最左边的序号
void init()
{
    for(int i=2;i<=31;i++)
    {
        z[i]=z[i-1]*2+i-1;
    }
    d[1]=1;
    for(int i=2;i<=31;i++)
    {
        d[i]=d[i-1]<<1;
    }
}
ll lowbit(ll x)
{
    return x&(-x);
}

//得到数的二进制位数
ll getbit(ll x)
{
    ll cnt=0;
    while(x!=1)
    {
        x>>=1;
        cnt++;
    }
    return cnt;
}
void swap(int& a,int& b)
{
    int temp=a;
    a=b;
    b=temp;
}
ll fun(ll x)
{
    return d[getbit(x)+1];//得到位数对应的二进制数
}
ll solve(ll x)
{
   ll bx=x-lowbit(x);
    if(bx==0)
    {
        return z[getbit(x)];
    }
    else
    {

        int temp=fun(x);
        ll sum=solve(temp)+abs(solve(temp)-solve(temp-(x-temp)));

        return sum;
    }
}


int main()
{
init();
    int a,b;
    while(scanf("%d %d",&a,&b)!=EOF)
    {

        if(a>b) swap(a,b);
        ll ba=solve(a);
        ll bb=solve(b);
        printf("%lld\n",bb-ba);
    }
    return 0;
}


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理