codeforces 466 C. Number of Ways

Posted by 111qqz on Tuesday, December 15, 2015

TOC

http://codeforces.com/problemset/problem/466/C 题意:给定一个序列。要将序列分成三个非零的连续部分,使得三部分的和相等。问有多少中分法。 思路:首先可以知道,如果是序列的和不为3的倍数,那么一定无解,输出0.设序列的和为sum,那么每一部分的和就应该为sum/3。我们可以预处理出从1开始的和为sum/3的点(我开了数组表示前缀和。。想了下其实不用。。我只需要点的信息。。所以用一个变量表示即可),将点的下标存在p[i]里。对于每一个p[i],我想要知道比p[i]大且补与p[i]相邻的点中,有多少个j,使得从j到n的和为sum/3。因为如果有两部分的和都为sum/3,那么剩下的那部分也一定为sum/3.然后要知道有多少个满足题意的j,我们可以从后往前扫一遍,标记从n开始往前扫,和为sum/3的点,可以用一个0,1数组表示。如果和为sum/3,那么标记为1,否则为0.然后再用一个类似前缀和的思路。再开一个数组c记录从j到n有的和为多少,也就是从j到n有多少个点满足该点到n的和为sum/3.

预处理完这些之后。只需要从前往后扫一遍p[i],然后ans+=c[p[i]+2]即可。

/* ***********************************************
Author :111qqz
Created Time :2015年12月15日 星期二 20时28分44秒
File Name :code/cf/problem/466C.cpp
************************************************ */

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <string>
#include <cmath>
#include <cstdlib>
#include <ctime>
#define fst first
#define sec second
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define ms(a,x) memset(a,x,sizeof(a))
typedef long long LL;
#define pi pair < int ,int >
#define MP make_pair

using namespace std;
const double eps = 1E-8;
const int dx4[4]={1,0,0,-1};
const int dy4[4]={0,-1,1,0};
const int inf = 0x3f3f3f3f;
const int N=5E5+7;
int n;
int a[N];
LL sum[N],rsum[N];
int p[N],rp[N];
int cnt,rcnt;
int b[N];
int c[N];
LL ans;
LL solve()
{
    LL total = sum[n];
    if (total%3!=0) return 0;
    LL ave = total/3;
    cnt = 0 ;
    for ( int i = 1 ; i <= n ; i++)
    {
    if (sum[i]==ave)
    {
        cnt++;
        p[cnt] = i;
       // cout<<"i:"<<i<<endl;
    }
    }
    ms(b,0);
    for ( int i =  n ; i >= 1 ; i--)
    {
    if (rsum[i]==ave)
    {
        b[i] = 1; //b[i]为1表示可以,为0表示不可以。
    }
    }
    c[n] = b[n]; //c[i]表示i..n一共有多少个b[i]可以。
    for ( int i = n-1  ; i >= 1 ; i--)
    {
    c[i] = c[i+1] + b[i];
    }
    
     
    LL res =  0 ;
    for (  int i = 1 ; i <= cnt ; i++)
    {
    res+= c[p[i]+2]; //中间至少隔一个,因为要分成三组。
    }
    return res;

}
int main()
{
    #ifndef  ONLINE_JUDGE 
    freopen("code/in.txt","r",stdin);
  #endif

    cin>>n;
    sum[0] = 0 ;

    for ( int i = 1 ; i <= n ; i++)
    {
        scanf("%d",&a[i]);
        sum[i] = sum[i-1] + a[i];
    }
    rsum[n+1] = 0 ;
    for ( int i = n ; i >= 1 ; i --)
    {
        rsum[i] = rsum[i+1] + a[i];
    }
    ans = solve();
    cout<<ans<<endl;


  #ifndef ONLINE_JUDGE  
  fclose(stdin);
  #endif
    return 0;
}