题目
题目描述:
给定一个长度为n的整数数组,问有多少对互不重叠的非空区间,使得两个区间内的数的异或和为0。
输入描述:
第一行一个数n表示数组长度;第二行n个整数表示数组;1<=n<=1000,0<=数组元素<100000。
输出描述:
一行一个整数表示答案。
解析
题目表意很清楚,就是两个不重合子集的异或和为0
这里显然不可能暴力搜索,所以要用到前缀和(详情见前缀和专栏)
- 依旧是存好数组
- 做一个两层循环:(第一层)用来遍历数组。(第二层)用于求以第一层遍历的位置为基点的左右两边的子集(左右子集必须包含这个基点)的异或和的数量。
- 用散列表(map)存储某一个异或和在基点以前的数量。map[n]=m:意为异或和为n的子集有m个。
- 关于异或和数量:第二层有两个循环:第一个用于累加左边的散列表存储,第二个用于累加计算当前右子集的所有成功匹配的数量。
for (ll i = 2; i <= n; i++) { for (ll j = 1; j < i; j++) map[sum[j - 1] ^ sum[i - 1]]++; for (ll j = i; j <= n; j++) cnt += map[sum[i - 1] ^ sum[j]]; }
图解
解释:当i指到某个位置时,从i前面断开,循环累加计算的左右子集一定包含下划线的数据。
前缀和
ps:其实写这道题之前,我都不咋知道前缀和这个东西,tcl
前缀和:
将具有一定关系的数组的所有前缀,按这种关系计算后,保存下来。
前缀应用举例1:
求一个数组的第i个数到第j个数之和(默认i<j):我们平常可能就会从第i个遍历到第j个进行累加。
前缀和方法:输入时储存第i个位置的前i项和。以得到所有前缀。所以第i个数到第j个数之和可以表示为:。
本题应用:
异或也满足前缀和的使用。所以储存下每个位置的前n项异或。
所以第i个数到第j个数的异或和可以表示为:
AC代码
#include <iostream> #include <vector> using namespace std; typedef long long ll; #define js ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); const int MAX = 1e6 + 7; int main() { js; vector<ll> e, sum; ll map[MAX]; ll n; cin >> n; e.push_back(0); sum.push_back(0); for (ll i = 1; i <= n; i++) { ll t; cin >> t; e.push_back(t); sum.push_back(sum[i - 1] ^ t);//前缀和初始化 } memset(map, 0, sizeof(map)); ll cnt = 0; for (ll i = 2; i <= n; i++) { for (ll j = 1; j < i; j++) map[sum[j - 1] ^ sum[i - 1]]++; for (ll j = i; j <= n; j++) cnt += map[sum[i - 1] ^ sum[j]]; } cout << cnt << endl; return 0; }