题目描述
http://codeforces.com/problemset/problem/1438/E
简要题意：给定一个长度为 $n$ 的序列 $a_i$，求有多少子区间是合法的，定义一个子区间 $[l,r]$ 合法，当且仅当 $a_l\oplus a_r=\sum_{i=l}^ra_i$，其中 $\oplus$ 表示异或
$n\le 2\times 10^5,a_i <2^{30}$
Solution
注意到答案可能很少
我们考虑一种计数方式，将答案分成两类
第一种是 $a[l]$ 和 $a[r]$ 的最高位不相等
第二种是 $a[l]$ 和 $a[r]$ 的最高位相等
首先考虑第一种，我们枚举 $l$，然后向右枚举 $r$，直到 $\sum_{i=l+1}^{r-1}a[i]\ge 2^{k+1}$，其中 $k$ 为 $a[l]$ 的二进制最高位
能够证明这样的时间复杂度为 $O(n\log a_i)$，我们倒着再次枚举一遍，注意到这样的话第一类答案只会算一次，第二类答案则会算两次，所以我们再多判一下最高位即可
时间复杂度证明：
对于每个 $k$，最多枚举 $O(n)$，我们可以将每个含有 $2^k$ 的数当成一个隔板
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
| #include <iostream>
#include <cstdio>
#include <algorithm>
#define maxn 200010
using namespace std;
int n, m, a[maxn], bit[maxn], ans;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr); cout.tie(nullptr);
cin >> n;
for (int i = 1; i <= n; ++i) {
cin >> a[i];
for (int o = 0; o < 30; ++o)
if (a[i] >> o & 1) bit[i] = o;
}
for (int i = 1; i <= n; ++i) {
int sum = 0;
for (int j = i + 1; j < n; ++j) {
if (sum + a[j] >= (1 << bit[i] + 1)) break;
sum += a[j];
if (sum == (a[i] ^ a[j + 1]) && bit[i] >= bit[j + 1]) ++ans;
}
} reverse(a + 1, a + n + 1); reverse(bit + 1, bit + n + 1);
for (int i = 1; i <= n; ++i) {
int sum = 0;
for (int j = i + 1; j < n; ++j) {
if (sum + a[j] >= (1 << bit[i] + 1)) break;
sum += a[j];
if (sum == (a[i] ^ a[j + 1]) && bit[i] > bit[j + 1]) ++ans;
}
} cout << ans << "\n";
return 0;
}
|