题意：要使得一个非零数组的任意一部分的和都不是0，问最少需要插入多少个数。 解法：最开始这个问题被我转换成了一个很复杂的问题…想太多了，如下面的样例，下面的数组是上面的前缀和： 很容易发现，在前缀和中相等的数字中，任两个之间的区间之和都是0，那么只需要考虑最近的，问题就转换成要破坏这些区间最少需要多少数字。这时候我想到一个做法，就是把所有区间都记录下来，按左端点排序以后贪心判断，这样的话，要记录的区间根本存不下。破坏这些区间所需要的数字是很难得到的。其实这题做法很简单，用map记录前缀和，亮点就在于map的清空，只要插入了一个数字，就把map清空一次，这样就可以表明前面已经被更改过，后面的数字和前面的无关，重新开始计量。
代码：
#include <algorithm> #include <iostream> #include <cstring> #include <vector> #include <cstdio> #include <queue> #include <cmath> #include <set> #include <map> #include<bitset> #define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); #define _for(n,m,i) for (register int i = (n); i < (m); ++i) #define _rep(n,m,i) for (register int i = (n); i <= (m); ++i) #define lson rt<<1, l, mid #define rson rt<<1|1, mid+1, r #define PI acos(-1) #define eps 1e-9 #define rint register int #define F(x) ((x)/3+((x)%3==1?0:tb)) #define G(x) ((x)<tb?(x)*3+1:((x)-tb)*3+2) using namespace std; typedef long long LL; typedef pair<LL, int> pli; typedef pair<int, int> pii; typedef pair<double, int> pdi; typedef pair<LL, LL> pll; typedef pair<double, double> pdd; typedef map<int, int> mii; typedef map<LL, int> mli; typedef map<char, int> mci; typedef map<string, int> msi; template<class T> void read(T &res) { int f = 1; res = 0; char c = getchar(); while(c < '0' || c > '9') { if(c == '-') f = -1; c = getchar(); } while(c >= '0' && c <= '9') { res = res * 10 + c - '0'; c = getchar(); } res *= f; } const int ne[8][2] = {1, 0, -1, 0, 0, 1, 0, -1, -1, -1, -1, 1, 1, -1, 1, 1}; const int INF = 0x3f3f3f3f; const int N = 2e5+10; const LL Mod = 1e9+7; const int M = 3e5+10; int n; LL a, sum; mli mp; int main() { scanf("%d", &n); mp[0] = 1; int ans = 0; _rep(1, n, i) { scanf("%lld", &a); sum += a; if(mp[sum]) { ++ans; sum = a; mp.clear(); mp[0] = 1; } mp[sum] = 1; } printf("%d\n", ans); return 0; }