蓝桥杯刷题 前缀和与差分-[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;
}