AT_arc119_c [ARC119C] ARC Wrecker 2

一道性质题，这种题据大佬说是找不变的东西来判断合法性，就比如这题，每次加减只能在相邻的数力里操作，所以可以发现，在任意一区间中把下表为奇数的数和下标为偶数的数分为两个序列，这两个序列的元素和的差无论怎么加减都是不变的，那么就考虑一个区间的这个差满足什么条件时此区间合法。

手模一下，发现对于

a_i,a_{i+1},a_{i+2}

这三个数，把

a_i

和

a_{i+1}

同时加上

a_{i+2}

，再把

a_{i+1},a_{i+2}

同时减去

a_{i+2}

，就会有

a_i\rightarrow a_i+a_{i+2}~,~a_{i+1}\rightarrow a_{i+1}~,~a_{i+2}\rightarrow 0

，其实就相当于把

a_{i+2} 加到a_i

上来了，所以序列是否合法就看上文所述的那个差值是否为 0 ，即奇下标的数的和是否等于偶下标的数的和就好了。

做法就是顺序扫，前缀和

s_1~,~s_2

分别记录奇项和和偶项和，对于每个

i

把

s_{1,i}-s_{2,i}

扔进一个map中维护，并且答案加上

i

之前，有几个

i

有相同差值就好了。

CPP

#include<bits/stdc++.h>
using namespace std;
#define MAXN 300010
#define ll long long
int n,a[MAXN];
ll s1[MAXN],s2[MAXN];
map<ll,int>ds;
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    ll ans=0;
    ds[0]=1;
    for(int i=1;i<=n;i++)
    {
        if(i&1)s1[i]=s1[i-1]+a[i],s2[i]=s2[i-1];
        else s2[i]=s2[i-1]+a[i],s1[i]=s1[i-1];
        ans+=ds[s2[i]-s1[i]];
        ds[s2[i]-s1[i]]++;
    }
    printf("%lld\n",ans);
    return 0;
}

AT_arc119_c [ARC119C] ARC Wrecker 2

文章操作

AT_arc119_c [ARC119C] ARC Wrecker 2

相关推荐

评论

AT_arc119_c [ARC119C] ARC Wrecker 2