题目描述
https://atcoder.jp/contests/arc081/tasks/arc081_c
简要题意：给定一个字符串 $s$，求最短的不是 $s$ 子序列的字典序最小的串
$|s| \le 2\times 10^5$
Solution
我们考虑子序列自动机，我们令 $f[i]$ 表示从 $i$ 跳到 $n+1$ 最小的步数
转移直接枚举填那个字母，然后根据子序列自动机跳到对应的位置
时间复杂度 $O(26n)$
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
| #include <iostream>
#include <vector>
#include <cmath>
#include <cstring>
#include <algorithm>
#define maxn 200010
#define ll long long
#define INF 1000000000
using namespace std;
int n;
char s[maxn];
int nxt[maxn][26];
int f[maxn];
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr); cout.tie(nullptr);
cin >> s + 1; n = strlen(s + 1);
for (int i = 0; i < 26; ++i) nxt[n][i] = n + 1;
for (int i = n; i; --i) {
for (int j = 0; j < 26; ++j) nxt[i - 1][j] = nxt[i][j];
nxt[i - 1][s[i] - 'a'] = i;
} f[n + 1] = 0;
for (int i = n; ~i; --i) {
f[i] = n - i + 1;
for (int j = 0; j < 26; ++j)
f[i] = min(f[i], f[nxt[i][j]] + 1);
}
int p = 0, len = f[0];
while (len)
for (int i = 0; i < 26; ++i)
if (f[nxt[p][i]] == len - 1) {
cout << (char) (i + 'a');
p = nxt[p][i]; --len; break;
}
return 0;
}
|