【每日一题】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个数之和可以表示为： $S_{j}-S_{i-1}$ 。

本题应用：

异或也满足前缀和的使用。所以储存下每个位置的前n项异或。

所以第i个数到第j个数的异或和可以表示为： $S_{j}\otimes S_{i-1}$

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;
}

每日一题文章被收录于专栏

憨憨的专栏