AT_arc119_c [ARC119C] ARC Wrecker 2

yokai_ing · 2025-04-21 21:51:35 · 题解

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 有相同差值就好了。

#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;
}