AT2382 A or...or B Problem

传送门

还是看题解的啦

先考虑一个显而易见的结论：A和B二进制下最高的几位相同是没用的（设去掉的那些位之和为sum）

然后我们设\(d\)为二进制下从高位到低位第一位不相同的，\(k\)为B从高位到低位第二个不为0的

然后我们分几段来统计答案

首先，\([A,2^d-1+sum]\)显然是可以凑出来的

然后，考虑\(k\)，发现\([2^d+sum,2^d+2^{k+1}+sum-1]\)也是可以凑出来的

最后，我们发现还有一种情况漏算了，确定\(d\)，所以区间就是\([A+2^d,sum+2^{d+1}]\)

求并就好啦

讲的好乱啊，应该只有我一个人会来看吧

代码：

#include<cstdio>

#include<iostream>

#include<cstring>

#include<algorithm>

using namespace std;

void read(long long &x){

	char ch;bool ok;

	for(ok=0,ch=getchar();!isdigit(ch);ch=getchar())if(ch=='-')ok=1;

	for(x=0;isdigit(ch);x=x*10+ch-'0',ch=getchar());if(ok)x=-x;

}

#define rg register

const int maxn=110;

long long a,b,x,y,l,r,ans,ll,rr;

int aa[maxn],bb[maxn],lena,lenb,len,k;

int main(){

	read(a),read(b);x=a,y=b;

    while(a)aa[++lena]=a&1,a>>=1;

	while(b)bb[++lenb]=b&1,b>>=1;

	for(rg int i=max(lena,lenb);i;i--){

		if(aa[i]!=bb[i]){len=i;break;}

		x-=1ll*aa[i]<<(i-1);

		y-=1ll*bb[i]<<(i-1);

	}

	for(rg int i=len-1;i;i--)if(bb[i]){k=i;break;}

    l=x,r=(1ll<<(len-1))+(1ll<<k)-1;

	ll=(1ll<<(len-1))+x,rr=(1ll<<len)-1;

	if(ll>r)ans=r-l+1+rr-ll+1;

	else ans=rr-l+1;

	printf("%lld\n",ans);

}

巴特西

AT2382 A or...or B Problem

传送门

最新文章

热门文章