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