【贪心（计算贡献）+操作】CF833div2 C. Zero-Sum Prefixes

àì夳堔傛蜴生んèń 2024-03-22 06:06 40阅读 0赞

**这道题考虑贪心，计算贡献就好了**

[Problem - C - Codeforces][]

题意：

定义一个数列的值为前缀和为0的位置个数，每次操作可以把一个ai==0的数变成一个任意数，求进行若干次操作后数列的值最多

![8b318317ecc740d8a9fdee39a336466b.png][]

思路：

因为要求的是这个前缀和为0的点的最多个数，因此考虑贪心

具体怎么考虑，就得看操作的特殊性质了：

对于一次操作，把原本ai=0的点变成一个任意数，比如变成x

这样对该数后面的影响就是原本前缀和为-x的点的前缀和会变成0

这样的多次操作是有顺序的，我们考虑先去修改前面的再去修改后面的，这样就不会相互影响

因此对于一次操作对答案的贡献就是两个0之间出现次数最多的那个值，把第一个0变成这个值的相反数即可

Code：

#include <bits/stdc++.h>
    
    #define int long long
    
    using namespace std;
    
    const int mxn=2e5+10;
    
    vector<int> zero;
    
    int N;
    int a[mxn],pre[mxn];
    
    void solve(){
    	cin>>N;
    	zero.clear();
    	for(int i=1;i<=N;i++) pre[i]=0;
    	for(int i=1;i<=N;i++){
    		cin>>a[i];
    		if(!a[i]) zero.push_back(i);
    	}
    	zero.push_back(N+1);
    	for(int i=1;i<=N;i++) pre[i]=pre[i-1]+a[i];
    	int ans=0;
    	for(int i=1;i<zero.size();i++){
    		map<int,int> mp;
    		int mx=0;
    		for(int j=zero[i-1];j<=zero[i]-1;j++){
    			mp[pre[j]]++;
    			mx=max(mx,mp[pre[j]]);
    		}
    		ans+=mx;
    	}
    	for(int i=1;i<zero[0];i++){
    		if(pre[i]==0) ans++;
    	}
    	cout<<ans<<'\n';
    }
    signed main(){
    	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    	int __=1;cin>>__;
    	while(__--)solve();return 0;
    }

[Problem - C - Codeforces]: https://codeforces.com/contest/1748/problem/C
[8b318317ecc740d8a9fdee39a336466b.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/22/3bb99b0c9e4c471389310b1975f63b6c.png