Posted on 2012-03-14 08:48
C小加 阅读(384)
评论(0) 编辑 收藏 引用 所属分类:
解题报告
这道题纠结我了一天的时间，本以为用lowbit可以轻松搞定，可是中间出现了各种故障，WA了很多次才AC。
计算a和b之间的节点数，可以用1-a与1-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;
}