自动搬运

查看原文

来自洛谷，原作者为

	哈哈人生 Go Best.

搬运于2025-08-24 23:17:36，当前版本为作者最后更新于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;
}