【二分】代码源每日一题div2 三段式

港控/mmm° 2024-03-16 18:20 66阅读 0赞

[三段式 - 题目 - Daimayuan Online Judge][- _ - Daimayuan Online Judge]

题意：

![e8269ad9f788474c8d19679915dbe380.png][]

思路：

可以发现很特殊的地方是，它只有三段，因此这个就是突破口

显然，每一段的和是确定的，且如果sum不是3的倍数，就无解，输出0

然后，问题就是，如何统计三段和为定值的方案数

本来想的是那个前缀和+map的套路，后来细想不是

其实就是统计前后指针个数

注意到，如果能分成三段，那么第一个指针的前缀和一定是sum/3，第三个指针的后缀和一定是sum/3

因此可以把这些指针放到两个数组里，然后因为第三个指针一定要大于第一个指针，因此需要二分

有个细节就是，第三个指针一定要比第一个指针大至少2，不然三段中间那段就不见了，这个可以用全是0的特殊情况来考虑

所以找出第一个>=L\[i\]+2的指针个数就行

Code：

#include <bits/stdc++.h>
    
    #define int long long
    
    using namespace std;
    
    const int mxn=1e5+10;
    
    int N,len1=0,len2=0;
    int a[mxn];
    int pre[mxn],suf[mxn];
    int L[mxn],R[mxn];
    
    signed main(){
    	cin>>N;
    	int sum=0;
    	for(int i=1;i<=N;i++){
    		cin>>a[i];
    		sum+=a[i];
    		pre[i]=pre[i-1]+a[i];
    	}
    	if(sum%3!=0||N<3){
    		cout<<0<<'\n';
    		return 0;
    	}
    	for(int i=N;i>=1;i--) suf[i]=suf[i+1]+a[i];
    	for(int i=1;i<=N;i++){
    		if(pre[i]==sum/3) L[++len1]=i;
    	}
    	for(int i=N;i>=1;i--){
    		if(suf[i]==sum/3) R[++len2]=i;
    	}
    	sort(R+1,R+1+len2);
    	int ans=0ll;
    	for(int i=1;i<=len1;i++){
    		int pos=lower_bound(R+1,R+1+len2,L[i]+2)-R;
    		if(pos>=1&&pos<=len2) ans+=(len2-pos+1);
    		//if(pos>=1&&pos<=len2&&max(L[i]+2,pos)>=1&&max(L[i]+2,pos)<=len2) ans+=(len2-(max(L[i]+2,pos))+1);
    	}
    	cout<<ans<<'\n';
    	return 0;;
    }

[- _ - Daimayuan Online Judge]: http://oj.daimayuan.top/problem/872
[e8269ad9f788474c8d19679915dbe380.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/8d8142f8635049a995ff956cfc0bbfb8.png