【每日一题】Xorto
Xorto
https://ac.nowcoder.com/acm/problem/14247
题目
题目描述：
给定一个长度为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;
} 每日一题 文章被收录于专栏
憨憨的专栏
