codeforces-#674-D

codeforces-#674-D

九月 28, 2020

D. Non-zero Segments

题意

给出一个长度为n<1e5的数组a (0<|ai|<1e9且)

求至少要插入多少个数使得 不存在 子区间和为0

​

题解

贪心的想若有多个区间和为0

那么我们需要在尽量多的区间公共处插入大数那样操作的次数最少

对于找到区间和为0的区间 可以用set或map 存之前出现过的前缀和

若当前的前缀和 pre在容器中出现 则说明这两个前缀和之间的子区间和为0

那么如何插入能符合上述贪心过程能减少最多和为0的区间

当遇到一个前缀和在容器中已经出现 则向当前位置插入一个非常大的数

并清空容器 并将前缀置为当前数的值

为什么这样插入符合要求，观察上图

一种颜色表示一个和为0的区间的左右端点

我们最先遇到红色区间的右端点处要插入大数，插入后整个数组被这个数隔开

不会再存在区间跨越这个数且和为0

也就是说插入后 黄色 绿色区间和一定不为0 那就符合我们的贪心策略了

这种方法因为插入的是为0区间的最右侧

所以无论是否存在和为0的区间与当前区间有交集

它都能一次操作后减少最多个和为0的区间

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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define endl '\n'
#define Turnoff std::ios::sync_with_stdio(false)
const ll Max=3e5+5;
const ll Mod=998857459;

ll data[Max];
int main() {
    Turnoff;
    int n;cin>>n;ll sum=0,ans=0;
    for(int i=1;i<=n;i++)cin>>data[i];
    set<ll>pre;ll Psum=0;pre.insert(0);
    for(int i=1;i<=n;i++){
        Psum+=data[i];
        if(pre.count(Psum)){
            ans++;
            pre.clear();
            pre.insert(0);
            Psum=data[i];
        }
        pre.insert(Psum);
    }
    cout<<ans<<endl;
}