CF1438E

· · 题解

题解思路：

我们会发现一个性质：满足条件的区间不会很多。

因为满足条件的数很少，所以我们就可以用暴力。

我们先假设，这个区间是以 a_l 为主导的，就是 a_l 是 a_l 和 a_r 里二进制最高的一位。

对于这样的情况下，那么我们就暴力求满足条件的区间就可以了。

先对于 l 枚举 r。

终止条件是什么呢？

我们假设最高位是第 k 位，那么 \sum^{n}_{i = 1}a_i 一定要 \le 2^{k + 1}，首先我们最大值在第 k 位上，而异或又是不进位加法，所以这个区间的和就是一定要 \le 2^{k + 1} 的。

所以我们就暴力枚举 r，当遇到不符合这个条件的 r 时，就终止就可以了。

然后再倒着，对于 r 枚举 l，就可以了。

证明时间复杂度：

假设这是以第 k 位二进制，那么最多有 \log n 位二进制。对于每个二进制的情况下呢，我们去讨论。

我们假设二进制最高位为 k，的下标有： p_1 , p_2 ... ... p_n，假设 l = p_1，那么当 r = p_3 时一定会终止，因为要是 l = p_1 , r = p_3 时，累加和就是：p_2 + p_3 而这个数一定会超过 2^{k + 1}。

那么对于每个下标累加和是多少：

\sum^{x}_{i = 3} p_i - p_{i - 2}

那么这些数的累加和算下来他就是 p_x + p_{x - 1} - p_1 - p_2 \le 2n，就是一个 O(n) 级别的。

有 \log n 次操作，，每次 O(n) 总时间复杂度为 O(n \log n)

AC CODE:

#include <iostream> 
#include <algorithm>
#include <vector>
#include <cstring>
#include <cstdio>
#include <set>
using namespace std;
typedef long long ll;
const int N = 200010;
int n;
int a[N];
set <pair <int , int>> s;//用set去重
int log2 (int x) {//求log2 
    int cnt = 0;
    while (x) {
        ++ cnt;
        x >>= 1;
    }
    return cnt;
}
void solve (bool op) {//0代表正着，1代表倒着 
    vector <int> pre (n + 10);
    for (int i = 1; i <= n; ++ i)
        pre[i] = pre[i - 1] + a[i];//求前缀和 
    for (int i = 1; i <= n - 2; ++ i) {
        ll sum = a[i + 1];
        int x = log2 (a[i]) + 1;
        for (int j = i + 2; j <= n; ++ j) {
            if ((a[i] ^ a[j]) == pre[j - 1] - pre[i]) {//看看这个区间是否满足这个性质 
                if (!op) s.insert ({i , j});//正着直接插入 
                else s.insert ({n - j + 1 , n - i + 1});//倒着 
            }
            if ((sum + a[i]) > (1ll << x)) break;//超过了范围，break 
            sum += a[j];
        }
    }
}
int main() {
    scanf ("%d" , &n);
    for (int i = 1; i <= n; ++ i)
        scanf ("%d" , &a[i]);
    solve (0);//正着来
    reverse (a + 1, a + 1 + n);
    solve (1);//倒着来
    printf ("%d\n" , (int)s.size());//输出答案
    return 0;
}

码字不易，求赞！