AcWing-4507. 子数组异或和

本文主要是介绍AcWing-4507. 子数组异或和，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

异或的一个性质：如果对一个数异或了两次就相当于不异或。

所以我们可以用前缀和预处理 \(a[i]\oplus =a[i-1]\)

\(i\) 至 \(j\) 的异或和为 \(a[j]\oplus a[i-1]\)

该连续子数组的前一半元素的异或和等于其后一半元素的异或和。

即该连续子数组的异或和为 \(0\) 。

暴力的解法：

#include<bits/stdc++.h>
using namespace std;
int n,tot,b;
int a[300001];
int f[300001];
int main()
{
  cin>>n;
  for(int i=1; i<=n; i++)
  {
    cin>>b;
    a[i]=a[i-1]^b;
    for(int j=i-1; j>=1; j-=2)
    {
      if(a[i]==a[j-1])
      {
        tot+=f[j-1];
        tot++;
        f[i]=f[j-1]+1;
        break;
      }
    }
  }
  cout<<tot<<endl;
}

优化：

观察数据范围， \(1<<20\) ,可以接受。

于是我们开一个数组 \(mp[2][(1<<20)+1]\) ，第一维是长度为奇数（1）或偶数（0），第二维是前缀和为 \(x\) 的个数。

开第一维的原因是满足该连续子数组的长度为偶数（奇奇为偶）。

所以每对一个前缀和就判断和它相同值的个数，并计入答案。

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,tot,b;
int a[300001];
int mp[2][(1<<20)+1];
signed main()
{
  cin>>n;
  mp[0][0]=1;
  for(int i=1; i<=n; i++)
  {
    cin>>b;
    a[i]=a[i-1]^b;
    tot+=mp[i&1][a[i]];
    mp[i&1][a[i]]++;
  }
  cout<<tot<<endl;
}

这篇关于AcWing-4507. 子数组异或和的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！