【蓝桥杯】专题练习

前缀和

3956. 截断数组 - AcWing题库

一看到题目很容易想到的思路是对数组求前缀和，然后枚举两个分段点就好，时间复杂度是On^2，n是1e5会t，需要优化。

朴素的代码，会超时：

#include <bits/stdc++.h>
using ll=long long;
const int N=2e5+10;
int a[N],s[N];
void solve()
{int n;std::cin>>n;for(int i=1;i<=n;i++){std::cin>>a[i];s[i]=s[i-1]+a[i];} int target=s[n]/3;int cnt=0;for(int i=1;i<=n;i++){if(s[i]!=target) continue;for(int j=i+1;j<n;j++){if(s[n]-s[j]!=target) continue;cnt++;				}}std::cout<<cnt<<'\n';
}
signed main() 
{int t;t=1;//std::cin>>t;while(t--){solve();} return 0;
}

思考一下，上面的代码是枚举所有可能的（i,j)符合条件就++。试想一下如果我们手算这个题会怎么做呢？是不是确定第一段之后去数有第二段有多少种情况？比如：

4

1 2 3 3

i走到2时发现满足条件，我们去后面找有几个满足条件的，发现只有一个，加上1，没有再满足条件的i了，因此答案就是1。

反过来是不是也一样呢？数一数前面有多少种情况，一旦后面有满足条件的j就加上前面的和。

因为后段至少有两个数，因此i属于[1,n-2],判断s[1]是否等于target。前段至少有两个数，故而j属于[3,n],判断s[n]-s[j-1]是否等于target。

i从1-n-2顺着走，判断是否满足条件，满足则cnt++，说明目前前段有cnt种情况，只需要有一个j>i且满足条件就可以确定以j为第二段的一共有cnt种情况，答案加上cnt即可。

AC代码：

#include <bits/stdc++.h>
using ll=long long;
const int N=2e5+10;
int a[N],s[N];
void solve()
{int n;std::cin>>n;for(int i=1;i<=n;i++){std::cin>>a[i];s[i]=s[i-1]+a[i];} if(s[n]%3||n<3){std::cout<<0<<'\n';return ;}int target=s[n]/3;ll cnt=0,res=0; for(int i=1;i<=n-2;i++){if(s[i]==target) cnt++;int j=i+2;if(s[n]-s[j-1]==target) res+=cnt;}std::cout<<res<<'\n';
}
signed main() 
{int t;t=1;//std::cin>>t;while(t--){solve();} return 0;
}