每天一把CF : 20201021
题目
原题链接:https://codeforces.com/problemset/problem/1426/D
思路
题目大意：给定一个整数数组，有一操作，往任一位置插入任意一个数（可任意大或任意小），问要使这个数组没有和为0的子串，最小操作数是多少？
核心思路：做前缀和，记做数组s，若s[i]==s[j]则a[i+1]至a[j]和为0（因为数组中已经明确表示没有等于0的数）。只要往j处插入一个无限大的数即可。
插入这个数之后因为j的左边已经不可能产生0和子串，所以此时前缀和s数组需要清0，重新开始计算。
具体实现如下
代码实现
#include<iostream>
#include <set>
using namespace std
;
#define ll long long
const int MAX
= 2e5 + 5;
ll n
, sum
, ans
, tp
;
int a
[MAX
];
set
<ll
> s
;
int main() {
while (cin
>> n
) {
ans
= sum
= 0;
s
.clear();
s
.insert(0);
for (int i
= 1; i
<= n
; i
++)
cin
>> a
[i
];
for (int i
= 1; i
<= n
; i
++)
{
sum
+= a
[i
];
if (s
.find(sum
) != s
.end()) {
ans
++;
s
.clear();
s
.insert(0);
s
.insert(a
[i
]);
sum
= a
[i
];
}
else
s
.insert(sum
);
}
cout
<< ans
<< endl
;
}
}
