传送
时间限制：C/C++ 2秒，其他语言4秒 空间限制：C/C++ 32768K，其他语言65536K
64bit IO Format:%lld
题目描述
给定一个长度为n的整数数组，问有多少对互不重叠的非空区间，使得两个区间内的数的异或和为0。 输入描述: 第一行一个数n表示数组长度；
第二行n个整数表示数组； 1<=n<=1000,0<=数组元素<100000。
输出描述:
一行一个整数表示答案。
示例1
输入
3
0 0 0
输出
5
说明
([1,1],[2,2]),([1,1],[3,3]),([1,1],[2,3]),([1,2],[3,3]),([2,2],[3,3])
题解：
枚举？TLE√
暴力肯定过不了，我们可以先考虑只枚举一个区间[x,y]，这个区间可以通过前缀异或和得到。pre来存前缀
我们用[x,y]表示右边的区间，题目要求左右区间异或和为0，也就是问[x,y]左边有多少和它值一样的区间。
我们可以用a[i]来存，a[i]表示左边异或和为i区间个数，数组a反应的数量，i反映的是值。
先将区间[k,i]存进a中，再用a[ ]来查看左边有多少区间异或和值与右区间[i+1 , j]值相同。
因为a存的是数量，所以直接用ans+=a [ pre[i] ^ [j] ]
代码：
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e7+3;
int a[maxn];
int pre[maxn];
int x;
int n;
long long ans=0;
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>x;
pre[i]=pre[i-1]^x;
}
for(int i=1;i<=n;i++)
{
for(int k=0;k<i;k++) a[pre[i]^pre[k]]++;//
for(int j=i+1;j<=n;j++) ans += a[pre[i]^pre[j]];//
}
cout<<ans;
return 0;
}
扩展
关于异或的题我最近做了个
CF282E Sausage Maximization
牛客网题目链接
异或的题，解法挺新颖，不过不知道为什么牛客网这里不能 提交？
原题是cf的cf题目链接
我自己写的题解
京公网安备 11010502036488号