DDOSvoid's Blog

CF 1398F Controversial Rounds

发表于 更新于 分类于
本文字数： 1.3k 阅读时长 ≈ 1 分钟

题目描述

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