题目链接：http://codeforces.com/problemset/problem/466/C

 

题目大意： 给你一个长度为n的序列，让你将其分为三个区间，每个区间的和相等，求分的方法有几种？

 

正好最近学了前缀和，这道题目恰巧是一个前缀和的题

首先我们进行判断该序列的总和是否可以整除3： 如果不可以那么输出0

随后我们先求后缀和，如果后缀和 sum/3 相等，那么我们就用标记数组标记。最后在对标记数组求后缀和(cnt[i] 代表i->n 之间可以为第三个区间左边界的个数)

我们再求前缀和，如果前缀和和 sum/3 相等，那么个数 res += cnt[i+2]  

为什么是i+2？

因为我们要确保有三个区间，如果是i+1的话不能够确保有第三个区间

 

AC代码：

 1 #include <cstdio>
 2 #include <string>
 3 #include <iostream>
 4 #include <algorithm>
 5 #include <cstdbool>
 6 #include <string.h>
 7 #include <math.h>
 8 
 9 using namespace std;
10 
11 typedef long long LL;
12 const int maxn = 500005;
13 int a[maxn],cnt[maxn];
14 
15 int main()
16 {
17     int n;
18     LL res = 0;
19     LL sum = 0;
20     cin >> n;
21     for (int i=1;i<=n;i++)
22     {
23         cin >> a[i];
24         sum += a[i];
25     }
26     if (sum % 3 != 0)
27     {
28         printf("0\n");
29     }
30     else
31     {
32         sum /= 3;
33         LL ss = 0;
34         for (int i=n;i>=1;i--)
35         {
36             ss += a[i];
37             if (ss == sum)
38                 cnt[i]++;
39         }
40         for (int i=n-1;i>=1;i--)
41         {
42             cnt[i] += cnt[i+1];
43         }
44         ss = 0;
45         for (int i=1;i<=n;i++)
46         {
47             ss += a[i];
48             if (ss == sum)
49                 res += (LL)cnt[i+2];
50         }
51         cout << res << endl;
52     }
53     return 0;
54 }