Acwing 第 64 场周赛 C 4507. 子数组异或和(异或+前缀和)


https://www.acwing.com/problem/content/4510/

给定一个长度为 n 的整数数组 a1,a2,…,an。

请你统计一共有多少个数组 a 的非空连续子数组能够同时满足以下所有条件:

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

输出
一个整数,表示满足条件的连续子数组的数量。
输入样例1:
5
1 2 3 4 5
输出样例1:
1

输入样例2:
6
3 2 2 3 7 6
输出样例2:
3

输入样例3:
3
42 4 2
输出样例3:
0
  • s[r]^s[mid] = s[mid] ^ s[l-1]

  • s[r]=s[l-1]

  • 所以就是看对每个r有多少个l,然后区间长度为偶数,所以l-1和r奇偶性要相同

  • 直接map统计一下

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=400200,M=2002;
LL a[N],s[N];
int main()
{
    cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);
    LL n;
    cin>>n;
    for(LL i=1;i<=n;i++)
    {
        cin>>a[i];
        if(i==1) s[i]=a[i];
        else s[i]=s[i-1]^a[i];
        //cout<<s[i]<<" "; 
    }
    //cout<<endl;
    LL sum=0;
    map<LL,LL> odd,even;
    even[0]=1;//默认可以异或为0的时候就有一个了
    for(LL r=1;r<=n;r++)
    {
        if(r%2==1) sum+=odd[s[r]],odd[s[r]]++;//奇数
        else sum+=even[s[r]],even[s[r]]++;
        //cout<<sum<<" ";
    }
    //cout<<endl;
    cout<<sum<<endl;
    return 0;
}

原创文章,作者:ItWorker,如若转载,请注明出处:https://blog.ytso.com/280433.html

(0)
上一篇 2022年8月14日
下一篇 2022年8月14日

相关推荐

发表回复

登录后才能评论