题目概述
求所有不是 A 的子序列的最短小写英文字母字符串中字典序最小的一个。
分析
一个类似于 CSP2025-S 中第三题的动态规划。
倒着做。
设 \(f_i\) 表示以 \(A_i\) 为开头的子序列不在 \(A_{i\dots |A|}\) 出现的最短长度。
然后从后面挑一个转移即可。
但是我们发现这样子是 \(\mathcal{O}(n^2)\) 的。
但是我们可供转移的字符集最多只有 \(26\) 个。
于是优化状态：设 \(f_i\) 表示以字符 \(i\) 为开头的子序列不在当前 \(A\) 的后缀当中的最短长度。
\[f_i=1+\min_x f_{p_x}
\]
然后就做完了。
代码
时间复杂度 \(\mathcal{O}(n)\)。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <stdlib.h>
#include <algorithm>
#include <vector>
#define int long long
#define N 200005
#define M 30
using namespace std;
char s[N + M];
int n;
int p[M],f[M],g[N + M];
signed main(){scanf("%s",s + 1);n = strlen(s + 1);for (int i = 0;i < 26;i ++) s[++n] = i + 'a',p[i] = n;for (int i = n - 26;i >= 0;i --) {g[i] = p[0];for (int j = 1;j < 26;j ++)if (f[j] < f[s[g[i]] - 'a']) g[i] = p[j];if (i) f[s[i] - 'a'] = f[s[g[i]] - 'a'] + 1,p[s[i] - 'a'] = i;}for (int x = g[0];x;x = g[x]) putchar(s[x]);return 0;
}
入门黑科技：子序列自动机
利用空间换时间的做法。
推荐阅读：https://www.cnblogs.com/zhln/p/18432582
设 \(nxt_{i,j}\) 表示从 \(i\) 开始字符 \(j\) 最开始的位置。
然后按照序列的顺序跑bfs就可以了。
代码
时间复杂度 \(\mathcal{O}(n)\)。
以下代码来自zjc5：
#include <bits/stdc++.h>
using namespace std;
const int N = 200010;
char ch[N], ans[N];
int n, nxt[N][26], pre[N], cnt;
bool vs[N];
int main() {cin >> (ch + 1);n = strlen(ch + 1);for (int i = n; i; i--) {for (int j = 0; j < 26; j++)nxt[i][j] = nxt[i + 1][j];nxt[i][ch[i] - 'a'] = i;}//预处理queue<int>q;vs[0] = 1;q.push(0);while (!q.empty()) {int x = q.front();q.pop();for (int i = 0; i < 26; i++) {int t = nxt[x + 1][i];if (!t) {//第一个未被找到的字符串ans[++cnt] = 'a' + i;while (x) {ans[++cnt] = ch[x];x = pre[x];}for (int i = cnt; i; i--)cout << ans[i];return 0;} else if (vs[t])continue;pre[t] = x, vs[t] = 1;q.push(t);}}return 0;
}