题解：AT_arc119_c [ARC119C] ARC Wrecker 2

· · 题解

题意

在给定序列中选取一个区间 [L,R] 并在这个区间内选取相邻两个数同时加一或减一，使得区间和为 0，求有多少个这样的区间。

思路

从区间长度为 2 开始想，则当前区间内两个数必须相等才为合法。接着区间长度为 3 时，要使区间合法，则中间的数必须等于两端数的和才为合法。继续扩大区间，当区间长度为 4 时，令 x_1,x_2,x_3,x_4 分别为区间四个数，减去两端的数，则为 0,x_2-x_1,x_3-x_4,0，这时就变成区间长度为 2 的情况，整理可得 x_1+x_3=x_2+x_4。区间长度扩大到 5 时，我们令 x_1,x_2,x_3,x_4,x_5 分别为区间五个数。减去两端的数，则为 0,x_2-x_1,x_3,x_4-x_5,0，此时就变成了长度为 3 是的区间情况。

优化

令 s[i] 为前缀和数组。则每当 s[i],s[j](j<i) 相等时就为一个合法的区间。考虑用 map 来记录前 i 个 s[i] 出现的个数，则条件符合时 ans+=m[s[i]] 组合答案。

代码

#include<bits/stdc++.h>
using namespace std;
long long n,sum,ans,t; 
map<long long,long long>m;
int main()
{
    scanf("%lld",&n);
    m[0]=1;
    for(long long i=1;i<=n;i++)
    {
        scanf("%lld",&t);
        if(i%2!=0)sum+=t*1;
        else sum+=t*(-1);
        ans+=m[sum]++;
    }
    printf("%lld",ans);
    return 0;
}