AtCoder-ARC119C ARC Wrecker 2

Table of Contents

AtCoder-ARC119C ARC Wrecker 2 #

题目大意 #

给定长度为 $n$ 的数组 $a$ . 对于 $a$ 的子数组 $b$ , 可以进行如下操作:

选择相邻的两个数, 同时 $+1$ 或 $-1$

如果经过若干次操作能够使得 $b$ 中元素全部变为 $0$ , 那么称 $b$ 是 $a$ 的一个好子数组. 求 $a$ 的好子数组的数量.

Solution 1 #

一个数组是好子数组当且仅当它奇数项的和与偶数项的和相等. 如果把 $a$ 的奇数项变为其相反数, 那么问题转化为求 $a$ 和为 $0$ 的子数组个数, 这个问题很常规, 可以使用哈希表解决.

代码如下:

#include <bits/stdc++.h>
using namespace std;
#define ll long long

int main() {
    int n;
    cin >> n;
    ll a[n];
    map<ll, ll> book;
    book[0]++;
    ll sum = 0, ans = 0;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        if (i & 1) {
            a[i] = -a[i];
        }
        sum += a[i];
        if (book.count(sum)) {
            ans += book[sum];
        }
        book[sum]++;
    }
    cout << ans << endl;
    return 0;
}