Two Hundred Twenty One (easy version)

发表于 更新于 分类于 ，

    给出n个数的数组a，每个元素非-1即1。

    设 $f(a) = a_1 - a_2 + a_3 - a_4 + ...$

    现有q个查询，每次查询子数组a[l,r]中删除最少数量的元素，使得剩余数字组成的数组b其$f(b) = 0$。

Two Hundred Twenty One (easy version)

Created by LXC on Fri May 12 13:03:52 2023

https://codeforces.com/problemset/problem/1562/D1

ranting: 1700

tag: data structures, dp, math

题意

给出n个数的数组a，每个元素非-1即1。

设 $f(a) = a_1 - a_2 + a_3 - a_4 + …$

现有q个查询，每次查询子数组a[l,r]中删除最少数量的元素，使得剩余数字组成的数组b其$f(b) = 0$。

题解

考虑每个$a_i$被删除后剩余的数组成的数组$b_i$，其$f(b_i)$

观察到$|f(b_i)-f(b_{i+1})| = 2 或 1$

当n是奇数时所有$f(b_i)$是偶数。$b_1 = -f(a) \pm 1$而$b_n = f(a) \pm 1$，因此$b_1$和$b_n$不同符号，或者为0，而相邻$f(b_i)$相差为0或2。所以必定存在$f(b_i) = 0, i \in [1,n]$，所以答案只需删除一个。

当n为偶数时，可以删掉一个变为奇数。所以答案是删除两个。

特殊情况$f(a) = 0$就不需要删除。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47

#include <bits/stdc++.h>
// #define SINGLE_INPUT
#define ll long long
#define N 500005
#define MOD 998244353
using namespace std;

void sol() {
    int n, q;
    cin >> n >> q;
    string s;
    cin >> s;
    vector<int> p(n + 1);
    for (int i = 1; i <= n; i++) {
        if (i % 2) {
            p[i] = p[i - 1] + (s[i - 1] == '+' ? 1 : -1);
        } else {
            p[i] = p[i - 1] - (s[i - 1] == '+' ? 1 : -1);
        }
    }
    while (q--) {
        int x, y;
        cin >> x >> y;
        if (p[y] - p[x - 1] == 0) {
            cout << "0\n";
        } else {
            cout << ((y - x + 1) % 2 ? 1 : 2) << "\n";
        }
    }
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
#ifndef SINGLE_INPUT
    int t;
    cin >> t;
    while (t--) {
        sol();
    }
#else
    sol();
#endif
    return 0;
}