Codeforces-1323D Present【思维】【异或】【二分】

65 阅读 0 评论 43 点赞

我是靠谱客的博主现代小海豚，最近开发中收集的这篇文章主要介绍Codeforces-1323D Present【思维】【异或】【二分】，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

题目

Codeforces-1323D

题意

给一个长度为n的数组，计算以下公式的答案

(a1+a2)⊕(a1+a3)⊕…⊕(a1+an)
⊕(a2+a3)⊕…⊕(a2+an)
…
⊕(an−1+an)

题解

以下第k位从0开始计起，如二进制01的1处于第0位；
考虑答案的每一位，假设答案第 k 位上为1，则有奇数个a[i]+a[j] (i>j)在第 k 位上为1；
在计算第k位上是否为1时，k+1位以上的值对结果是没有影响的，所以我们先把数组a的每个数（k+1）位以上值消除后存入数组b，即：b[i] = a[i]&((1<<(k+1))-1);
接下来就是求有多少对 (i, j) （i<j）使得 (b[i]+b[j]) 在第k位上的值为1;
因为我们消除了第k+1位以上的值，那么第k位为1的范围为**[(1<<k)，(1<<(k+1))-1]** ，例如k=1时，范围为二进制10到11；
另外由于是两个数相加，那么两数和最大范围到（1<<(k+2)-2），例如二进制11+11=110；所以还存在一个范围 [(1<<(k+1))+(1<<k)，(1<<(k+2))-2] ，例如k=1时，范围为110到111；
求存在多少对的和在这两个区间的方法:
排序数组b，遍历数组b，固定一个值b[i]，二分查询，计算对数即可

代码

/*
* @author: arc
* @date: 2020-09-16 11:53:16
*/
#include<cstdio>
#include<algorithm>
#include<iostream>
using namespace std;
int a[444444];
int b[444444];
int main(){
int n;
cin >> n;
for(int i = 1; i <= n; i++) { cin >> a[i]; }
int ans = 0;
for (int k = 0; k <= 26; k++) {
for(int i = 1; i <= n; i++) {
b[i] = a[i] & ((1 << (k + 1)) - 1);
}
sort(b + 1, b + 1 + n);
int num = 0;
for(int i = 1; i <= n; i++) {
num +=
upper_bound(b + 1, b + 1 + n, ((1 << (k + 1)) - 1) - b[i]) -
lower_bound(b + 1, b + 1 + n, (1 << k) - b[i]);
num +=
upper_bound(b + 1, b + 1 + n, ((1 << (k + 2)) - 2) - b[i]) -
lower_bound(b + 1, b + 1 + n,
(1 << (k + 1)) + (1 << k) - b[i]);
if (b[i] + b[i] & (1 << k)) {
num--;
}
}
if ((num / 2) & 1) {
ans += (1 << k);
}
}
cout << ans << endl;
return 0;
}