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

Love_Ti_fjx · 2026-01-27 13:06:10 · 题解

蒟蒻的第一篇题解OvO,求过QWQ。

题意简述

• 给定一个长度为 n 的数列 A，将其划分为 4 段，每一段之和相等。

核心分析

• 首先，设每一段的总和为 t，则这一个数列的总和必定为 4 \times t，如果一个数无法被 4 整除即不满足被划分成四段的和相等，输出 0。

• 其次，直接枚举 4 段子段的时间复杂度为 O(n^3)，无法通过本题，从而要换一种简单的思路来写。

优化思路

• 我们可以运用前缀和以及计数累加来优化这道题。
• 将三个分割点分别设为 i，j，k，分别表示前一段的和，前两段的和，前三段的和（第四段就是剩下的）。
• 遍历数列时，先更新前缀和，再按 3t，2t，t 的顺序判断分割点，保证其严格递增。
• 当前缀和等于 3t 时，累加已统计的 i，j 到答案。
• 当前缀和等于 2t 时，累加已统计的 j 到 cnt2。
• 当前缀和等于 t 时，cnt1 计数加 1。

提示

• 一定要严格按照顺序来，不能打乱。

代码呈现

#include<bits/stdc++.h>  
using namespace std;
#define int long long   
int n,cnt,sum;//n:数列长度/cnt:数列总和/sum:当前前缀和
int cnt1,cnt2,ans;//cnt1:前缀和等于t的次数/cnt2:前缀和等于2t的累计组合数/ans:最终答案
signed main(){          
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    cin>>n;              
    vector<int> a(n);    
    for(int i=0;i<n;i++){
        cin>>a[i];      
    }
    for(int i:a){// 计算数列总和
        cnt+=i;
    }
    if(cnt%4!=0){//核心:总和无法被4整除，直接输出0
        cout<<"0";
        return 0;
    }
    int t=cnt/4;//每段需要满足的目标和         
    for(int i=0;i<n-1;i++){//遍历到n-1（保证第四段至少有一个数）
        sum+=a[i];// 累加当前元素，更新前缀和
        if(sum==3*t){// 找到第三个分割点：累加前两个分割点组合数
            ans+=cnt2;
        }
        if(sum==2*t){//找到第二个分割点：累加第一个分割点
            cnt2+=cnt1;
        }
        if(sum==t){//找到第一个分割点：计数+1
            cnt1++;
        }
    }
    cout<<ans;
    return 0;
}

总复杂度：O(n)。

作者太蒻了，就这还WA了2发才过。

完结撒花！求关OvO。