acwing3956. 截断数组

题目

题解

将1-n分成三段，只需要枚举两个位置即可。首先枚举第二个位置i，然后枚举第一个位置j，其中由于每段不能为空，所以j只能在2_{i-2这之间，如果s[2}i-2]==s[n]/3则说明第一刀成立,cnt++,那么还要使第二段的和为s[n]/3，只需要s[n]-s[i-1]==s[n]/3即可

#include<iostream>
#include<algorithm>
using namespace std;
const int N=1e5+10;
int n;
int s[N];
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>s[i];
        s[i]+=s[i-1];
    }
    if(s[n]%3){
        puts("0");
        return 0;
    }
    long long ans=0;
    for(int i=3,cnt=0;i<=n;i++){
        if(s[i-2]==s[n]/3)cnt++;
        if(s[n]-s[i-1]==s[n]/3)ans+=cnt;
    }
    cout<<ans<<endl;
    
    return 0;
}