CF1915E Romantic Glasses 题解

我们考虑维护 \(sum_i\) 表示前 \(i\) 个数中偶数下标的数之和与奇数下标的数之和之差，其中 \(sum_0=0\)。

若在某一时刻，有 \(sum_i=sum_j(j<i)\)，说明 \(j \sim i\) 中偶数下标的数之和与奇数下标的数之和之差为 \(0\)。这个使用 map 判断即可。

实现：

int n,f=0; cin>>n;
m.clear(),m[0]=1; //m是用于判断的map
memset(sum,0,sizeof(sum));
for(int i=1,x;i<=n;i++){
	cin>>x;
	if(i%2==0) sum[i]=sum[i-1]+x;
	else sum[i]=sum[i-1]-x;
	if(m[sum[i]]) f=1;
	m[sum[i]]=1;
}
return f; //f为1输出YES，否则输出NO