Posted on 2012-03-14 08:48
C小加 閱讀(462)
評論(0) 編輯 收藏 引用 所屬分類:
解題報(bào)告
這道題糾結(jié)我了一天的時(shí)間，本以為用lowbit可以輕松搞定，可是中間出現(xiàn)了各種故障，WA了很多次才AC。
計(jì)算a和b之間的節(jié)點(diǎn)數(shù)，可以用1-a與1-b的節(jié)點(diǎn)數(shù)之差來求。在右子樹的點(diǎn)可以轉(zhuǎn)化為相應(yīng)的左子樹的點(diǎn)，經(jīng)過多步驟的轉(zhuǎn)化，可以把點(diǎn)的位置固定在樹的最左邊的那條線上。所以只需要計(jì)算每層最左邊的節(jié)點(diǎn)數(shù)就OK了。經(jīng)過遞推會(huì)得出一個(gè)公式，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經(jīng)過的點(diǎn)
ll d[33]={0};//樹每層最左邊的序號(hào)
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);
}
//得到數(shù)的二進(jìn)制位數(shù)
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];//得到位數(shù)對應(yīng)的二進(jìn)制數(shù)
}
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;
}