DDOSvoid's Blog

CF 526D Om Nom and Necklace

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

题目描述

https://codeforces.com/problemset/problem/526/D

简要题意：给定字符串 $S$ 和 $k$，$len(S)=n$，对于所有 $i\in[1,n]$，求 $pre(S,i)$ 是否可以被表示成 $ABAB\cdots A$ 的形式，其中 $A$ 出现 $k+1$ 次，$B$ 出现 $k$​ 次，$A$ 和 $B$ 都可以是空串

$n,k\le 10^6$

Solution

我们注意到 $AB$ 的一定是由 $per(S)$​ 组成的，因为 $A$ 是 $AB$ 的前缀，令 $d=\lfloor\frac{len(S)}{per(S)}\rfloor$，则 $AB$ 的长度只能是 $\lfloor\frac{d}{k}\rfloor$

如果 $S\equiv 0(\bmod per(S))$，那么我们只需要满足 $\lfloor\frac{d}{k}\rfloor\ge d\bmod k$，否则必须满足 $\lfloor\frac{d}{k}\rfloor> d\bmod k$，因为 $S$ 分成 $d$ 块之后还剩一个小于 $d$ 的块

求完 $nxt$ 数组后，对于 $S$​ 的每个前缀判断即可，时间复杂度 $O(n)$

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
#include <iostream>
#include <cstring>
#include <vector>
#define maxn 1000010
#define ll long long
using namespace std;

int n, k;
char s[maxn];

int nxt[maxn]; 
void init_nxt(char *s) {
    int k = 0, t = 0, n = strlen(s + 1); nxt[1] = 0; 
    for (int i = 2; i <= n; ++i) {
        while (k && s[k + 1] != s[i]) k = nxt[k];
        if (s[k + 1] == s[i]) ++k;
        nxt[i] = k; 
    }
}

bool ans[maxn];
int main() { 
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    cin >> n >> k >> s + 1; init_nxt(s);
    for (int i = 1; i <= n; ++i) {
        int len = i - nxt[i], d = i / len;
        if (i % len == 0) ans[i] = d / k >= d % k;
        else ans[i] = d / k > d % k;
        cout << ans[i];
    } 
    return 0; 
}