CodeForces1323 D. Present(二分)

68 阅读 0 评论 45 点赞

我是靠谱客的博主谨慎心锁，最近开发中收集的这篇文章主要介绍CodeForces1323 D. Present(二分)，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

题意：

给一个长度为n的数组a
要求计算(a(1)+a(2))异或(a(1)+a(3))异或…(a(1)+a(n))异或(a(2)+a(3))异或…(a(2)+a(n))异或(a(3)+a(4))…(a(n-1)+a(n))。
即所有"有序对相加的和"的异或和。
数据范围：n<=4e5，1<=a(i)<=1e7

思路:

原题(可以不看)：AtCoder3943 Two Sequences

思路基本一致。

看到异或很容易想到按位计算贡献
但是有加法很麻烦，因为加法可能会产生进位，怎么处理加法进位不是很好想。
假设我们当前要计算第x位的贡献，那么显然高于x的位对第x位是否为1不会产生影响，只考虑二进制的1到x位。
设T=2^x，将a数组2T取模，则得到低x位的值。
要使得a(i)+a(j)的第x位为1，则需满足以下两个条件之一：
T<=a(i)+a(j)<2T，(第x位不发生进位，此条件为第x位为1，x位下面任意)
3T<=a(i)+a(j)<4T，(第x位发生进位，此条件位第x和第x+1位都为1，x位下面任意)
因此可以枚举a(i)，分别两次二分出满足这两种条件的两个区间端点，区间长度即为第x位为1的数对个数，

有几点需要注意：
1.因为计算出的区间长度的总和是无序对数量总和，而题目要求是有序对，所以总数量需要除以2
2.对于每个a(i)，需要减去自己匹配自己的情况(判断方法：一是判断i是否在区间内，二是自己和自己相加判断是否第x位为1)。

最后，如果数对总和如果是奇数则当前位对答案有贡献。

ps：
代码里面手写的二分，所以码量会大很多。
如果改成lower_bound码量变小，代码看起来会短很多。

code:

#include<bits/stdc++.h>
using namespace std;
const int maxm=4e5+5;
int a[maxm];
int b[maxm];
int n;
int ask(int left,int right,int idx){//计算b数组中left<=x<right的x的数量
int st=0,ed=0;
int l=1,r=n;
while(l<=r){//st尽量向左扩展
int mid=(l+r)/2;
if(b[mid]>=left){
st=mid;
r=mid-1;
}else{
l=mid+1;
}
}
l=1,r=n;
while(l<=r){//ed尽量向右扩展
int mid=(l+r)/2;
if(b[mid]<right){
ed=mid;
l=mid+1;
}else{
r=mid-1;
}
}
if(!st||!ed)return 0;//如果不能同时满足x>=left且x<right,则无解
int ans=ed-st+1;
if(st<=idx&&ed>=idx)ans--;//自己不能和自己匹配，如果自己在区间内就减1
return ans;
}
signed main(){
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
}
int ans=0;
for(int i=0;i<25;i++){
int t=(1<<i);
for(int j=1;j<=n;j++){
b[j]=a[j]%(t*2);
}
sort(b+1,b+1+n);
int cnt=0;
for(int j=1;j<=n;j++){
cnt+=ask(t-b[j],t*2-b[j],j);
cnt+=ask(t*3-b[j],t*4-b[j],j);
}
cnt/=2;//因为题目要求的数对是有序对，所以要除以2
if(cnt&1)ans+=(1<<i);
}
printf("%dn",ans);
return 0;
}