CF 1398F Controversial Rounds

题目描述

https://codeforces.com/contest/1398/problem/F

简要题意:给定一个包含 $0,1,?$ 的长度为 $n$ 的字符串 $S$,需要对 $k\in[1,n]$,求每次将 $S$ 中的 $?$ 变成 $0$ 或 $1$ 后的最多操作次数,对于某一个 $k$,字符串 $S$ 的一次操作为每次删掉连续 $k$ 个相同字符

$|S|\le 10^6$

Solution

首先我们考虑暴力枚举答案,能够发现答案是一个调和级数,最多不超过 $O(n\log n)$

我们考虑用并查集维护每个点右边第一个长度超过 $l$ 的连续段的起点

随着 $l$ 的增加,我们只需要每次把向右连续段的长度刚好为 $l$ 的点的并查集向右合并即可

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
48
49
50
51
#include <iostream>
#include <cstdio>
#include <unordered_map>
#include <vector>
#include <cstring>
#include <algorithm>
#include <set>
#define maxn 1000010
#define ll long long
#define INF 100000000000000ll
using namespace std;

int n;

char s[maxn];

int r[maxn][2];

int fa[maxn];
void init_fa(int n) { for (int i = 1; i <= n; ++i) fa[i] = i; }

int find(int x) { return fa[x] == x ? x : fa[x] = find(fa[x]); }

vector<int> a[maxn];

int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr); cout.tie(nullptr);

cin >> n >> s + 1; init_fa(n + 1);
for (int i = n; i; --i) {
r[i][0] = r[i + 1][0] + 1;
r[i][1] = r[i + 1][1] + 1;
if (s[i] == '?') continue;
r[i][s[i] - '0' ^ 1] = 0;
}
for (int i = 1; i <= n; ++i)
a[max(r[i][0], r[i][1])].push_back(i);
for (int l = 1; l <= n; ++l) {
int p = 1, ans = 0;
while (p <= n) {
p = find(p);
if (p > n) break;
++ans; p += l;
}
cout << ans << " ";
for (auto t : a[l]) fa[t] = t + 1;
}
return 0;
}