Codeforces 1333C. Eugene and an array（思维） /详解

Cynthia ·

更新时间:2024-09-20

· 664 次阅读

Codeforces Round #632 (Div. 2) C. Eugene and an array

题意：
求出一个数列中子区间满足此区间的任意子区间之和不为0的区间个数。

思路:

考虑用dp[x]dp[x]dp[x]记录前缀和为xxx的区间右端点。那么这道题其实可以看成用map记录前缀和的路径，依次计算每个元素作为区间右端点并且满足条件时对答案的贡献，再进行累加即可。 iii是以a[i]a[i]a[i]为右端点的子区间个数，lastlastlast是距离 iii最近且[last,i][last,i][last,i]中包含和为0的子段的端点，那么即说明[last+1,i][last+1,i][last+1,i]不包含和为0的子区间，所以每次遍历对答案的贡献为i−lasti-lasti−last。那么怎么求lastlastlast? 当dp[x]dp[x]dp[x]在前面出现过的时候就说明区间[dp[x]+1,i][dp[x]+1,i][dp[x]+1,i]之间的子段和为0，那么很明显，此时last=max(last,dp[x]+1)last=max(last,dp[x]+1)last=max(last,dp[x]+1)。这里取maxmaxmax是防止dp[x]+1dp[x]+1dp[x]+1比lastlastlast小，而导致容纳了一些错误的区间。例如[dp[x]+1,i]和[last,i][dp[x]+1,i]和[last,i][dp[x]+1,i]和[last,i]中均包含了子段和为0的区间，但是如果lastlastlast取dp[x]+1dp[x]+1dp[x]+1的话就会把原先的[last,i][last,i][last,i]之间的错误区间算进答案中，所以上面才会提及lastlastlast是距离 iii 最近的一点。但是不仅仅是如此，还要注意初始化 : dp[0]=last=0dp[0]=last=0dp[0]=last=0，其他应该没什么问题和坑点了。如果觉得有帮助的话给个赞，谢谢！或者有什么讲的不清楚的欢迎留言私信交流~

代码:

#include
#define ll long long
#define ull unsigned long long
#define inf 0x3f3f3f3f
#define mod 1000000007
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define lowbit(x) (x&(-x))
using namespace std;
inline ll read(){ll s=0,w=1;char ch=getchar();
while(ch'9'){if(ch=='-')w=-1;ch=getchar();}
while(ch>='0'&&ch>= 1;}return ans%p;}
const ull base=2333; const ull pp=19260811; const ull ppp=999998639;
const int manx=1e5+5;
const int mo=998244353;
ll s[manx];
mapdp;
int main(){
    ll n=read();
    ll ans=0,s=0,last=0; dp[s]=0;
    for(int i=1;i<=n;i++){
        ll x=read();
        s+=x;
        if(dp.count(s)) last=max(last,dp[s]+1);
        dp[s]=i;
        ans+=i-last;
     //   cout<<ans<<" "<<last<<endl;
    }
    cout<<ans;
    return 0;
}

作者：我不会DP

CodeForces AND array

1024 个赞