有一個長度為 n n n的序列，現(xiàn)在我們想把它切割成三段(每一段都是連續(xù)的），使得每一段的元素總和都相同，請問有多少種不同的切割方法
輸入描述
第一行給出一個數(shù) n n n，( 1 ≤ n ≤ 1 0 5 1≤n≤10^5 1≤n≤105)
第二行給出序列 a 1 a_1 a1?， a 2 a_2 a2?， a 3 a_3 a3?，…， a n a_n an?，( ∣ a i ∣ ≤ 1 0 5 |a_i|≤10^5 ∣ai?∣≤105)
輸出描述
輸出一個數(shù)表示有多少種不同的切割方法
樣例輸入
4
1 2 3 3
樣例輸出
1
樣例解釋
可以將它分成第一組 1 1 1， 2 2 2，第二組 3 3 3，第三組 3 3 3
解題思路
根據(jù)題意，很容易得到下面的公式：
s
u
m
1
+
s
u
m
2
+
s
u
m
3
=
s
u
m
s
u
m
1
=
s
u
m
2
=
s
u
m
3
s
u
m
1
=
s
u
m
2
=
s
u
m
3
=
1
3
s
u
m
sum_1+sum_2+sum_3=sum\\ sum_1=sum_2=sum_3\\ \\ sum_1=sum_2=sum_3=\frac{1}{3}sum
sum1?+sum2?+sum3?=sumsum1?=sum2?=sum3?sum1?=sum2?=sum3?=31?sum
要滿足題意有兩個前提條件（特殊判定）：
（1） s u m ? % ? 3 = = 0 sum\ \%\ 3==0 sum?%?3==0；
（2） n ≥ 3 n\ge3 n≥3。
if (n < 3 || sum % 3 != 0) {
cout << 0 << endl;
return 0;
}
然后我們來尋找可能的分割方式。
如果有多于 1 1 1種的分割方法，那么一定存在子段和為 0 0 0。
與其去找子段和為 0 0 0的部分，不如轉(zhuǎn)化思維，使用前綴和的概念（經(jīng)常用于連續(xù)區(qū)間和問題）。
這樣我們就只需要尋找前綴和同為 1 3 s u m \frac13sum 31?sum的部分了。
然后具體問題具體分析，因為題目中只要求分割為三段，所以我們直接找出前后兩段 1 3 s u m \frac13sum 31?sum即可。
注意，至少要為中間的 1 3 s u m \frac13sum 31?sum預(yù)留一個元素的位置。
long long ans = 0;
for (int i = 1; i <= n - 1; i++) {
if (pre[i] == subsum) {
ans += tail_counter[i + 2];
}
}
其中tail_counter中的元素意義為：
i
i
i位置及其之后有多少個后綴和為
1
3
s
u
m
\frac13sum
31?sum。文章來源：http://www.zghlxwxcb.cn/news/detail-452101.html
最后，AC代碼如下：文章來源地址http://www.zghlxwxcb.cn/news/detail-452101.html
#include <iostream>
using namespace std;
const int max_n = 1e5;
long long arr[max_n + 1], pre[max_n + 1], tail[max_n + 2];
long long tail_counter[max_n + 1];
int main() {
int n;
long long sum = 0;
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> arr[i];
sum += arr[i];
}
if (n < 3 || sum % 3 != 0) {
cout << 0 << endl;
return 0;
}
long long subsum = sum / 3;
for (int i = 1; i <= n; i++) {
pre[i] = arr[i] + pre[i - 1];
}
for (int i = n; i >= 1; i--) {
tail[i] = arr[i] + tail[i + 1];
tail_counter[i] = tail_counter[i + 1];
if (tail[i] == subsum) tail_counter[i]++;
}
long long ans = 0;
for (int i = 1; i <= n - 1; i++) {
if (pre[i] == subsum) {
ans += tail_counter[i + 2];
}
}
cout << ans << endl;
return 0;
}
到了這里，關(guān)于[Daimayuan] 三段式（C++，數(shù)組前綴和）的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
