题解：P12708 [KOI 2021 Round 1] 分割

哈哈人生 · 2025-06-11 19:16:07 · 题解

题意

求出把一个序列划分为四段非空且相等的连续段的方案数。

思路

我们将形式化题意中的 i,j,k 拿过来，方便讲述。拿人话说就分别是三个断点。

既然要四段都相等，那么一段的总和应该为序列总和的四分之一。而且第一、二段的总和应该和第三、四段的总和相等，且为序列总和的一半。我们记录序列前缀和和后缀和，找到前缀和等于序列总和的四分之一的位置当 i，找到前缀和等于序列总和的一半的位置当 j，找到后缀和等于序列总和的四分之一的位置当 k。

预处理 pre_x 表示 x 之前可以当 i 的位置的个数，和 suf_x 表示 x 之后可以当 k 的位置的个数。而我们枚举可行的中间位置 j，用 ans 累加 pre_j\times suf_{j+1} 即可。

代码

思路不难，预处理有些细节需要注意，别忘了特判即可。

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,a[100005],sum=0,pre[100005],suf[100005],ans=0;
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i],sum+=a[i];
    if(sum%4)return cout<<0,0;
    int tmp=0;
    for(int i=2;i<=n;i++){
        tmp+=a[i-1];
        if(tmp==sum/4)pre[i]=pre[i-1]+1;
        else pre[i]=pre[i-1];
    }
    tmp=0;
    for(int i=n-1;i>=1;i--){
        tmp+=a[i+1];
        if(tmp==sum/4)suf[i]=suf[i+1]+1;
        else suf[i]=suf[i+1];
    }
    tmp=0;
    for(int i=1;i<=n-1;i++){
        tmp+=a[i];
        if(tmp==sum/2)ans+=pre[i]*suf[i+1];
    }
    cout<<ans;
    return 0;
}