本文最后更新于 666 天前,其中的信息可能已经有所发展或是发生改变。
思想:
- 前缀和。
- 特殊情况:
- 当数组元素小于三个时,无解。
- 当该数组所有数之和不为 $3$ 的整数倍时,无解。
- 设数组均分的值为
res
,循环遍历前缀和数组a
。 - 设
i
为分割点,若a[i] == res
,说明将i
作为分割点有可能成立,记录分割点数量为cnt ++
。 - 设
n - i + 1
为第二个分割点,若a[n] - a[n - i + 1] == res
,则说明该分割点可以与i
之前的所有分割点进行分割数组,记录分割方案为ans += cnt
。
代码:
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 3;
typedef long long LL;
LL a[N];
void solve(){
int n; cin >> n;
for(int i = 1; i <= n; i ++){
cin >> a[i]; a[i] += a[i - 1];
}
if(n < 3 || a[n] % 3 != 0){ //特殊情况
cout << 0 << endl;
return ;
}
else{
LL res = a[n] / 3;
LL cnt = 0, ans = 0;
for(int i = 1; i + 2 <= n; i ++){
if(a[i] == res) cnt ++;
if(a[n] - a[i + 1] == res) ans += cnt;
}
cout << ans << endl;
}
}
int main(){
solve();
return 0;
}