2019 牛客多校第三场 B - Crazy Binary String

发表于 更新于 分类于 阅读次数：

题目链接：2019牛客多校第三场B

Substring：从第一个位置开始，为 0 就 -1，为 1 就 +1，两个值为 \(x\) 的位置中间的是合法串，统计所有的合法串中最长的即可。

Subsequence：记 0 的个数为 \(n_0\)，1的个数为 \(n_1\)，答案为 \(\min \{ n_0, n_1\}\)。

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
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int MAX_N = 100000 + 5;
int n, z, o;
char s[MAX_N];
map < int, vector <int> > pos;
int main() {
    scanf("%d", &n);
    scanf("%s", s + 1);
    int cnt = 0;
    pos[0].push_back(0);
    for (int i = 1; i <= n; ++i) {
        if (s[i] == '0') --cnt;
        else ++cnt;
        pos[cnt].push_back(i);
    }
    int maxString = 0;
    for (auto const &e: pos) {
        if (e.second.size() >= 2) {
            maxString = max(maxString, e.second.back() - e.second.front());
        }
    }
    for (int i = 1; i <= n; ++i) {
        z += (s[i] == '0');
        o += (s[i] == '1');
    }
    int maxSub = min(o, z);
    printf("%d %d\n", maxString, maxSub * 2);
    return 0;
}