蓝桥杯刷题 前缀和与差分-[3507]异或和之和（C++）

题目描述

给定一个数组 Ai，分别求其每个子段的异或和，并求出它们的和。

或者说，对于每组满足 1≤L≤R≤n 的 L，R求出数组中第 L 至第 R 个元素的异或和。

然后输出每组 L，R 得到的结果加起来的值。

输入格式

输入的第一行包含一个整数 n。

第二行包含 n 个整数 Ai，相邻整数之间使用一个空格分隔。

输出格式

输出一行包含一个整数表示答案。

样例输入

5
1 2 3 4 5

样例输出

39

知识点：前缀和与差分

代码

通过90%测试样例代码

//0和任意数x异或都是x
//x和x异或得到0
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=100010;
ll a[N],b[N],sum;
int main()
{ll n;cin>>n;for(int i=1;i<=n;i++){cin>>a[i];b[i]=b[i-1]^a[i];}for(int i=1;i<=n;i++){for(int j=i;j<=n;j++){sum+=b[i-1]^b[j];//前半部分异或抵消}}cout<<sum<<endl;return 0;
}

 通过100%测试样例代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=100010;
ll a[N],b[N],c[N],cnt;
int main() {ll n;cin>>n;for(int i=1;i<=n;i++) {cin>>a[i];}for(int i=0;i<=20;i++) {int one=0,zero=0,sum=0;for(int j=1;j<=n;j++){b[j]=(a[j]>>i)&0x1;c[j]=c[j-1]^b[j];//前缀异或数组（按位） if(c[j]==1){one++;}}zero=n-one;//one*zero的值为前缀异或数组中1的数量乘0的数量 //one为前缀异或数组中1的数量 sum+=one*zero+one;cnt+=(pow(2,i)*sum);	}cout<<cnt<<endl;return 0;
}