Tanya and Candies

题目链接http://codeforces.com/problemset/problem/1118/B
time limit per test:1 second
memory limit per test:256 megabytes

Examples

Input
7
5 5 4 5 5 5 6

Output
2

Input
8
4 8 8 7 8 4 4 5

Output
2

Input
9
2 3 4 2 2 3 2 2 4

Output
3

Note

In the first example indices of good candies are [1,2]
.

In the second example indices of good candies are [2,3]
.

In the third example indices of good candies are [4,5,9]
.

---

题目大意：给你n个数从中删去一个位置使得奇数位的和=偶数位的和，问你有多少种删法。
emmm。。。最朴素的算法就是一个个删掉然后一个个加起来查询。不过这样肯定会超时。毕竟是n²的算法。但它既然要求的是和，那么我们很容易想到可以用前缀和来优化使它达到O(n)：

if (i&1) odd[i]=odd[i-1]+a[i],even[i]=even[i-1];
else even[i]=even[i-1]+a[i],odd[i]=odd[i-1]; 

即构造两个前缀和，一个存奇数一个存偶数。
不过前缀和是静态的，这里删去了一个数之后整个数列就有所变化。不过我们细心一些就会发现，删去第i个数之后，i前面的i-1个数的奇偶性是不变的，则它们的和依旧是sum[i-1]。i之后的数奇偶性就会颠倒，则它们的和就相反了，即偶数=原本奇数的前缀和，奇数=原本偶数的前缀和。

#include <cstdio>
int a[200050],odd[200050],even[200050];
int main()
{
	int n,num=1;
	scanf ("%d",&n);
	for (int i=1; i<=n; i++){
		scanf ("%d",&a[i]);
		if (i&1) odd[i]=odd[i-1]+a[i],even[i]=even[i-1];
		else even[i]=even[i-1]+a[i],odd[i]=odd[i-1]; 
	}
	num--;
	int odd2=0,even2=0,ans=0;
	for (int i=1; i<=n; i++){//枚举删去第i天
		odd2=0,even2=0;
		if (i&1){
			odd2=odd[i]-a[i];
			even2=even[i];   //i之前奇偶不变
			odd2+=even[n]-even[i];//i之后奇偶颠倒
			even2+=odd[n]-odd[i];
		}
		else {
			odd2=odd[i];
			even2=even[i]-a[i];
			odd2+=even[n]-even[i];
			even2+=odd[n]-odd[i];
		}
		if (odd2==even2) ans++;
	}
	printf ("%d\n",ans);
	return 0;
}