子段异或
子段异或
http://www.nowcoder.com/questionTerminal/c41f41cd9bdc4d3097b2e754f2f49856
子段异或
https://ac.nowcoder.com/acm/contest/3005/D
亦或运算中
连续一段的运算 a[0]^...a[i]^a[i+1]^...^a[i+k]^...^a[n] 中若出现相同的亦或前缀和，
如a[0]^...^a[i]的亦或前缀和 与 a[0]^...^a[i+k]的亦或前缀和相等，则a[i+1]^...^a[i+k]=0
如 1 2 4 7 2 1 中 有1^2=3 1^2^4^7^2^1=3 则1^2^4^7^2^1=0
另配合map食用更佳
#pragma warning (disable :4996)
#include <iostream>
#include <cstdio>
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e5 + 20;
map<ll, int> a;
ll A[N];
ll ans = 0, sum = 0;
int main() {
int n;
scanf("%d", &n);
for (int i = 0; i < n; i++)
scanf("%lld", &A[i]);
a[0] = 1;
for (int i = 0; i < n; i++) {
sum = sum ^ A[i];
ans += a[sum];
a[sum]++;
}
cout << ans << endl;
}
查看15道真题和解析