首页 > 其他分享 >Acwing 第 64 场周赛 C 4507. 子数组异或和(异或+前缀和)

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

时间:2022-08-14 10:57:41浏览次数:97  
标签:周赛 输出 int LL 样例 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;
}

标签:周赛,输出,int,LL,样例,4507,异或,数组
From: https://www.cnblogs.com/Vivian-0918/p/16584968.html

相关文章