蓝桥杯刷题-15-异或和之和-拆位+贡献法⭐⭐(⊙o⊙)

蓝桥杯2023年第十四届省赛真题-异或和之和

在这里插入图片描述
题目描述
给定一个数组 Ai，分别求其每个子段的异或和，并求出它们的和。或者说，对于每组满足 1 ≤ L ≤ R ≤ n 的 L, R ，求出数组中第 L 至第 R 个元素的异或和。然后输出每组 L, R 得到的结果加起来的值。

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

在这里插入图片描述

⭐⭐
处理位运算的常用方法:拆位法
常用的思想:贡献法思想

010101100101
011010101010
101010101101
110101010101
110010101011
对于二进制位中的第i位:
如果这一位中1的个数是奇数，那么最后的结果中，这一位就是1.如果是偶数，在结果中，这一位就是0.
在这里插入图片描述

bit=(a[j]>>i)&1
//这段代码是在C语言中常见的位操作语句，它主要用于提取一个整数数组a中第j个元素的第i位的值
a[j]: 这是数组a中的第j个元素。在这里，a是一个整数数组，j是数组的索引。

a[j] >> i: 这是将数组元素a[j]右移i位。这里的>>是右移位操作符，它将a[j]的二进制表示向右移动i位。例如，如果a[j]是1101，而i是2，那么结果将是0011。

(a[j] >> i) & 1: 这一步是将右移后的结果与1进行按位与操作。这里的&是按位与操作符，它将两个数的对应位进行与操作。因为1在二进制中是0001，所以此操作会保留右移后结果的最低位。这样就可以提取出a[j]右移i位后的最低位，即第i位的值。

bit: 这是一个变量，用于存储提取出的第i位的值。如果该位为1，则bit为1；如果该位为0，则bit为0。

因此，整个表达式(a[j]>>i)&1的目的是提取出数组a中第j个元素的第i位的值，并将其存储在变量bit中。

ans+=(1<<i)*n0;
//这段代码是在C语言中常见的位操作语句，它执行的是一个位运算操作
1 << i: 这是将数字1左移i位的操作。这里的<<是左移位操作符，它将1的二进制表示向左移动i位。例如，如果i是2，那么结果将是100。

(1 << i) * n0: 这是将左移后的结果乘以变量n0的值。这里的*是乘法操作符。因为左移后的结果实际上是2的i次幂，所以这一步相当于将2的i次幂乘以n0。

ans += (1 << i) * n0: 这是将上一步得到的结果加到变量ans上。这里的+=是加法赋值操作符，它将右侧表达式的结果加到左侧的变量上。

因此，整个表达式ans += (1 << i) * n0的目的是将2的i次幂（即1左移i位）乘以n0的值，并将结果加到变量ans上。

代码：

#include <iostream>
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+10;
int a[N];

void solve()
{
  int n;cin>>n;
  for(int i=0;i<n;i++){
    cin>>a[i];
  }
  int ans=0;
  for(int i=20;i>=0;i--)
  {
    int s=0;//前缀和
    int n0=1,n1=0;//偶数个数和奇数个数
    for(int j=0;j<n;j++)
    {
      int bit=(a[j]>>i)&1;//从高到底取
      s+=bit;
      //前缀和是奇数，合法区间个数=1+前面偶数的个数
      if(s%2){
        ans+=(1<<i)*n0;
        n1++;

      }else{
        ans+=(1<<i)*n1;
        n0++;
      }
    }
  }
  cout<<ans<<endl;
}
signed main(){
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  int t;
  t=1;
  //cin>>t;
  while(t--)
  solve();
}