(CF1333C)Eugene and an array

发表于 分类于 ，

原题链接

思路:

首先，若 \([a_i,\cdots,a_j]\) 是好数组，则 \([a_i,\cdots,a_{j-1}]\) 也是好数组；若 \([a_i,\cdots,a_j]\) 不是好数组，则 \([a_i,\cdots,a_{j+1}]\) 也不是好数组.

则对于每个 \(i\), 可以找到一个最大值 \(r_i\), 使得 \([a_i,\cdots,a_{r_i}]\) 是好数组，以 \(a_i\) 为起点的好数组便有 \(r_i-i+1\) 个.

同时由如上性质，\(r_i\) 是个连续不下降序列. 则可由尺取法求 \(r_i\).

令 \(sum_i = \sum\limits_{j=1}^{i} a_i\), 即前缀和 , 若 \(sum_{i-1}=sum_j\), 则数组 \([a_i,\cdots,a_j]\) 和为 0. 反之，若 \([a_i,\cdots,a_j]\) 为好数组，则 \([sum_{i-1},\cdots,sum_{j}]\) 互不相同. 利用此性质可求 \(r_i\).

用 set 实现时间复杂度为 \(O(nlogn)\)

代码:

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
#include <cstdio>
#include <set>
using std::set;
const int Mn(200500);
long long sum[Mn];

int main()
{
    int n;
    scanf("%d",&n);
    for(int i(1);i<=n;++i)
    {
        int a;
        scanf("%d",&a);
        sum[i] = sum[i-1]+a;
    }
    long long ans(0);
    int pl(1),pr(1);
    set<long long> S;    //用set判断是否有相等的sum
    S.insert(0);
    for(;pl<=n;++pl)    //尺取
    {
        for(;pr<=n;++pr)
        {
            if(S.count(sum[pr]))    //若存在相等的sum
                break;
            else
                S.insert(sum[pr]);
        }
        ans += pr-pl;    //ri=pr-1
        S.erase(sum[pl-1]);
    }
    printf("%I64d",ans);
    return 0;
}