首页 > 代码库 > Codeforces466C Number of Ways
Codeforces466C Number of Ways
题目链接:
http://codeforces.com/problemset/problem/466/C
题意:
给一个长度为n的数组,将其分成连续的三段使三段的和相等,求有几种这样的组合
分析:
从头扫到尾,将所有的前缀和为(sum/3)的点统计起来,然后再从尾开始统计,找到统计所有后缀和为(sum/3)的节点 然后这种方案的数为
这个点之前所有前缀和为sum/3的个数
代码如下:
#include <iostream> #include <cstring> #include <cstdio> #include <algorithm> using namespace std; const int maxn = 500010; typedef long long LL; LL a[maxn]; int cnt[maxn]; int main() { int n; LL x; while(~scanf("%d",&n)){ LL s=0,p=0; memset(cnt,0,sizeof(cnt)); for(int i=1;i<=n;i++){ scanf("%lld",&a[i]); s+=a[i]; } if(s%3){puts("0");continue;} s/=3; int com=0; for(int i=1;i<=n;i++){ p+=a[i]; if(p==s) cnt[com++]=i; } LL ans = 0; p=0; for(int i=n;i>=1;i--){ p+=a[i]; // cout<<"p "<<p<<endl; if(p==s){ int pos=lower_bound(cnt,cnt+com,i-1)-cnt; // cout<<"pos "<<pos<<endl; ans+=pos; } } cout<<ans<<endl; } return 0; }
Codeforces466C Number of Ways
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。