发布时间: 2017年3月5日 16:01 最后更新: 2017年3月5日 16:04 时间限制: 1000ms 内存限制: 128M
描述百度是喵哈哈村的赞助商，所以百度派出了嘟嘟熊给大家展现魔法：
“抽刀断水水更流，举杯消愁愁更愁。”
只见刹那间，嘟嘟熊就从兜里面掏出了一堆数字，这一堆数字仿佛有了生命，不停的在空气中跃动。
这些数字排成一排。
嘟嘟熊又从兜里面拿出了三把大刀，欲将这些数字斩断，连续三刀斩成四节，使得每一节的和都一样，且每一节的长度至少大于0。
比如数组A={2,5,1,1,1,1,4,1,7,3,7}，就可以把下标为2,7,9的斩断，就变成了{2,5},{1,1,1,4},{7},{7}，每一节的和都一样。
但是对于数组A={10,2,11,13,1,1,1,1,1}，就不存在可以使得四节的和相同的方案。
输入本题包含若干组测试数据。 第一行一个n，表示有n个数字。 第二行n个整数a[i]。 保证 1<=n<=100000,-100000<=a[i]<=100000
输出如果可行的话，输出Yes，否则输出No
样例输入1 复制 11 2 5 1 1 1 1 4 1 7 3 7 9 10 2 11 13 1 1 1 1 1 样例输出1 Yes No题意：将一个数组切三次，每次删除一个数，最后剩余4段，且每段和相等 长度大于0；
解：因为最后剩余4段，则突破口在，第一段一定是开头的一部分，最后一段一定是结尾的一部分，记录前后前缀和出现的位置，然后判断长度是否大于0；
#include <iostream> #include <cstdio> #include <cstring> #include <cmath> #include <algorithm> #include <vector> #include <map> using namespace std; typedef long long LL; const int N = 1e5+10; LL a[N], sum1[N], sum2[N]; map<LL,int>p; int path[N]; int main() { int n; while(scanf("%d", &n)!=EOF) { sum1[0]=0, sum2[n+1]=0; for(int i=1;i<=n;i++) { scanf("%lld", &a[i]); sum1[i]=sum1[i-1]+a[i]; } p.clear(); memset(path,0,sizeof(path)); for(int i=n;i>=1;i--) { sum2[i]=sum2[i+1]+a[i]; path[i]=p[sum2[i]]; p[sum2[i]]=i; } int f=0; for(int i=1;i<=n;i++) { if(p.count(sum1[i])) { for(int j=p[sum1[i]];j!=0;j=path[j]) { if(j>i&&p.count(sum1[i]*2+a[j-1])) { for(int u=p[sum1[i]*2+a[j-1]];u!=0;u=path[u]) { if(u-2>=i+2&&u<=j-2&&sum1[u-2]-sum1[i+1]==sum1[i]) { f=1; break; } } } } } } if(f) puts("Yes"); else puts("No"); } return 0; }
