SPOJ - MAXXOR

依然是异或运算,这次是限制L,R范围内挑2个数使其异或值最大

如果r最高为是pos,那最理想状态当然是(1ll<<pos+1)-1

只有2个数如果凑近最理想的状态?直接找紧挨着的一个就好,这样符合高位尽可能高

/*H E A D*/

int main(){

	ll l,r,pos,pos2;

	while(cin>>l>>r){

		if(l>r) swap(l,r);

		if(l==r){

			cout<<0<<endl;

			continue;

		}

		rrep(i,63,0){

			if((r>>i)&1){

				pos=i;

				break;

			}

		}

		cout<<((1ll<<pos)^((1ll<<pos)-1))<<endl;

	}

	return 0;

}

UPD.昨晚写的太匆忙没考虑L足够接近但不等于R时的情况,

如果R=2^i+j,L=2i+k,(2^{i>j>k>0),无论如何异或,2}i是无效的,这时的对比就相当于j到k的区间中寻找异或最大的两个数

所以这时需要进一步的递归或迭代(L,R减去2^i就好),这一定有解

这题可能数据太弱了所以我前面的代码轻松过了

UPDD.感性上想了想好像这并不影响正确结果,因为无论如何递归,两个数必然是紧挨着的,异或处理越界部分都是无效的

代码不改了~

巴特西

SPOJ - MAXXOR

最新文章

热门文章