C. Number of Ways(前缀和)

发布时间：2020-12-16 07:19:53 所属栏目：百科来源：网络整理

导读：题目链接：http://codeforces.com/problemset/problem/466/C ? 题目大意：给你一个长度为n的序列，让你将其分为三个区间，每个区间的和相等，求分的方法有几种？ ? 正好最近学了前缀和，这道题目恰巧是一个前缀和的题首先我们进行判断该序列的总和是否可以

题目链接：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("0n");
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 }

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!