Posted on 2012-03-14 08:48
C小加 閱讀(471)
評論(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;
}