Present CodeForces - 1323D (思维+二分)

时间:2022-09-14 23:49:46

题目大意比较简单,就是求一堆(二元组)的异或和。

思路:按位考虑,如果说第k位为1的话,那么一定有奇数个(二元组)在该位为1。二元组内的数是相加的,相加是可以进位的。所以第k位是0还是1,至于k为后边的数有关,所以我们直接(1<<(k+1))取模。取模后每个数的取值范围就是[0,2^(k+1)-1],二元组的取值范围就是[0,2^(k+2)-2]。

先把二元组看成一个数x,x的第k位是1, 那么x的取值范围就是[2^k,2^(k+1)-1]和[2^k+2^(k+1),2^(k+2)-2]。

解释一下为什么。因为x的取值为[0,2^(k+2)-2]。如果说k的左边没有1,那么取值范围就是010000...~~011111...,如果说k的左边有1,这里做多只能由一个1,如果k的左边有两个1的话那范围直接就是2^(k+2)+...肯定不对的,所以只能有一个1,那么范围就成了11000...~~11111...

然后将对每一个arr[i],在[1,i)的范围内查找j的个数。arr[j]的范围就是x-arr[i]了。查找的时候用二分。upper_bound和lower_bound要搭配使用。寻找上边界的时候用upper_bound,寻找下边界用lower_bound,至于为啥,自己举个例子就行了....

code:

#include<bits/stdc++.h>
using namespace std;
const int N=4e5+;
int arr[N];
int main(){
int n;
cin>>n;
for(int i=;i<=n;i++) cin>>arr[i];
int ans=;
for(int i=;i>=;i--){
for(int j=;j<=n;j++) arr[j]=arr[j]%(<<(i+));
sort(arr+,arr++n);
for(int j=;j<=n;j++)
{
if((upper_bound(arr+,arr+j,(<<(i+))--arr[j])-lower_bound(arr+,arr+j,(<<i)-arr[j]))&)
ans^=<<i;
if((upper_bound(arr+,arr+j,(<<(i+))--arr[j])-lower_bound(arr+,arr+j,(<<(i+))+(<<i)-arr[j]))&)
ans^=<<i;
}
}
cout<<ans<<endl;
return ;
}