AtCoder Regular Contest 092 D - Two Sequences

題意：

給出兩個長度為 n n n的序列，求出所有 a i + b j a_i+b_j ai​+bj​的異或值。

題解：

異或相關還是按位考慮吧

如果能求出最總每一位有多少個1就可以算答案了。

那麼枚舉 a i a_i ai​，統計它能對第 j j j位貢獻多少個1

設 t = 2 j t=2^j t=2j，容易發現，隻有對 2 t 2t 2t取模後的數才有用。

然後考慮什麼情況第 j j j是1（取模後）

t &lt; = a i + b j &lt; 2 t t&lt;=a_i+b_j&lt;2t t<=ai​+bj​<2t

3 t &lt; = a i + b j &lt; 4 t 3t&lt;=a_i+b_j&lt;4t 3t<=ai​+bj​<4t

那麼排序+二分即可。

code：

#include<cstdio>
#include<cstdlib>
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
int a[200010],b[200010],n,c[200010];
int num[30];
int get1(int k)
{
	int l=1,r=n,ans=n+1;
	while(l<=r)
	{
		int mid=(l+r)/2;
		if(c[mid]>=k) ans=mid,r=mid-1;
		else l=mid+1;
	}
	return ans;
}
int get2(int k)
{
	int l=1,r=n,ans=0;
	while(l<=r)
	{
		int mid=(l+r)/2;
		if(c[mid]<k) ans=mid,l=mid+1;
		else r=mid-1;
	}
	return ans;
}
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++) scanf("%d",&a[i]);
	for(int i=1;i<=n;i++) scanf("%d",&b[i]);
	int T=1;
	for(int I=0;I<29;I++)
	{
		int t=(1<<(I+1))-1;
		for(int i=1;i<=n;i++) c[i]=b[i]&t;
		sort(c+1,c+n+1);
		for(int i=1;i<=n;i++)
		{
			int x=a[i]&t;
			int l=get1(T-x),r=get2(2*T-x);
			if(l<=r) num[I]+=(r-l+1);
			l=get1(3*T-x);r=get2(4*T-x);
			if(l<=r) num[I]+=(r-l+1);
		}
		T<<=1;
	}
	int ans=0;
	for(int i=0;i<29;i++) if(num[i]&1) ans+=(1<<i);
	printf("%d",ans);
}