D. Kousuke's Assignment 题解

Gusare / 2024-12-19 / 原文

前言

特别感谢 @jiejiejiang
这场div3给我打破防了，谢谢好兄弟对这么菜的我不离不弃 > <
本题也是他教我的，我在他思路的基础上做一点自己的补充
题目传送门：https://codeforces.com/contest/2033/problem/D
怎么感觉 TokaiZaopen 之前给我讲过类似的题（？）

题目大意

给一个序列，问和为0且不重叠的子区间的最大个数

思路

$[L,R]$区间和为0，即前缀和相同，$pre[r]-pre[l-1]=0$
从左往右遍历，用set储存之前的累加结果，set初始有个0，
对于每一位，用sum累加。
如果在set里有相同的结果，ans++，清空set，并插入0，sum置零。

sum置零？
1. 方便找直接为0的点
2. $pre[r]=pre[l-1]$ 那么左右两侧同时减去 $pre[k]$ 也成立，也就是指要从同一个点开始求前缀和就可以，不一定得是从0
set清空？要保证区间不重叠。

简单证明

对于两个和为0的区间A，B，共有三种关系：

包含（AB只能择一）
相交（AB只能择一）
相离（AB需要全选）

如果用上述的贪心策略：

对于A包含B，统计B，没有A，
相交（A前B后），统计A，没有B
A，B相离，A和B都会统计上

对于区间个数这个属性来说，都是不影响的，所以贪心策略可行。

代码

参考了 @jiejiejiang 的

#include<bits/stdc++.h>
#define ll long long
#define inf 0x3f3f3f3f3f3f3f3f
using namespace std;
set<ll> st;
void solve();

void solve(){
    ll n,x,sum=0,ans=0;
    cin>>n;
    st.clear();
    st.emplace(0);
    for(ll i=1;i<=n;i++){
        cin>>x;
        sum+=x;
        if(st.find(sum)==st.end()){
            st.emplace(sum);
        } else {
            ans++;
            st.clear();
            st.emplace(0);
            sum=0;
        }
    }
    cout<<ans<<'\n';
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    ll t=1;
    cin>>t;
    while(t--){
        solve();
    }
    return 0;
}