0%

[CF1426D] Non-zero Segments

题目

题目链接

题目大意:给定一个长度为 $n$ 的序列,求最少插入多少数才能将这个序列的任意子段和不为 $0$。$2 \le n \le 200000, -10^9 \le a_i \le 10^9, a_i \neq 0$。

思路

先思考 $O(n^2)$ 的算法,先求前缀和,然后找到 $f_j - f_i = 0$ 的 $i, j$,然后更新。

如果现在 $i < j$,那么在更新的时候对于任何满足 $r < i$ 的子段 $[l, r]$ 都是没有影响的。

我们可以对这个算法进行优化,当 $f_j = f_i$ 时意味着出现了一个子段和为 $0$ 的子段,这时候我们贪心的一个无限大的元素放在这个子段的末尾,这样一定是最优的。

使用 std::map 可以很好地实现这个算法。

另外要特判一下第一个子段和就为 $0$ 的情况,比如 1 -1 ...,所以要初始化 mp[0] = 1

每当更新了一次答案之后就要初始化,原因已经提过了,这时候右端点前面的部分已经没有用了。

代码

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
38
39
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <map>

template <class T>
inline void read(T &x) {
x = 0;
int f = 0;
char ch = getchar();
while (!isdigit(ch)) { f |= ch == '-'; ch = getchar(); }
while (isdigit(ch)) { x = (x << 1) + (x << 3) + (ch ^ 48); ch = getchar(); }
x = f ? -x : x;
return ;
}

typedef long long LL;

std::map<LL, int> mp;
LL n, a, s, ans;

int main() {
read(n);
mp[0] = 1;
for (int i = 1; i <= n; ++i) {
read(a);
s += a;
if (mp[s]) {
++ans;
mp.clear();
mp[0] = 1;
s = a;
}
++mp[s];
}
printf("%lld\n", ans);
return 0;
}