题解 P3989 【[SHOI2013]阶乘字符串】

## 题意简述 - 定义一个由前 $n$ 个字母组成的字符串为阶乘字符串，前 $n$ 个小写字母的全排列都作为它的子序列出现。 - 给定一个字符串 $S$，询问它是否是阶乘字符串。 - 多组数据，$1 \le T \le 5$, $1 \le n \le26$, $1 \le |S| \le 450$ ## 分析与解答 #### 1. 关于 $n$ 的范围 - 考虑一个包含前 $n$ 种小写字母的字符串，长度至少要为多少才能满足其为阶乘字符串。换句话说，构造一个由前 $n$ 个字母组成的阶乘字符串，使得它的长度最小。 - 容易想到一种最 naive 的构造方式，将前 $n$ 个小写字母顺序排列再复制 $n$ 次，得到一个长度为 $n^2$ 的字符串。例如，当 $n=3$ 时，为 $\text{abcabcabc}$。容易证明该字符串一定为阶乘字符串。 - 在上面的构造方式中再改进一步，删去一些无用的字符，可以得到一种形如 $\text{abcdcbabcdcba}\ (n=4)$ 的构造方式（即以 $\text{abcd、dcba}$ 为基础串，将当前基础串接在前一个基础串的后面）（表述不太清楚，理解万岁，理解万岁），这种构造方式长度为 $n^2-n+1$ - **目前，我还没有找到更优秀的构造方式**。也就是说，现在可以假定，一个字符串的长度至少为 $n^2-n+1$，它才可能是前 $n$ 个字母的阶乘字符串。 - 注意到 $22^2-22+1 = 463 \gt 450, 21^2-21+1 = 421 \lt 450$，所以当 $n \ge 22$ 时一定无解。 - 通过上面的分析，我们将 $n$ 范围将至了 $1 \le n \le 21$，这就可以保证接下来的 dp 的时空复杂度了。 --- #### 2. 关于如何 dp - 如果以考虑前第 $i$ 个字符为状态，每次转移时都需要枚举之前的所有子序列并一个一个 check，显然会超时。 - 注意到 $n \le 21$，我们不妨抛开上一个思想，考虑状压小写字母。令 $f_i$ 表示 $i$ 中的小写字母集合组成的所有全排列，是否都在 $S$ 的子序列中出现过。 - 于是转移又成了很大的问题。 - 这种时候，常见的想法是改变状态。令 $f_i$ 表示 $i$ 中的小写字母集合组成的所有全排列，在 $s$ 中全部出现过，所需要的下标**最小**是多少。此时，如果一个字母集合 $i$ 不能达成阶乘字符串的要求，则 $f_i = +\infty$。 - 构造 $S$ 的序列自动机，即 $nxt_{i,j}$ 表示第 $i$ 个位置后，字符 $j$ 第一次出现的位置，其中 $i \in [1,m],\ j \in [0,n)$。 - 这种状态下的转移不妨使用刷表法。只需要考虑在当前集合中加入一种小写字母，会发生什么变化。 - 发现如果加入一种字母 $j$，则在原来子序列的最后只要加入一个 $j$ 来满足有以 $j$ 结尾的排列；而包含 $j$ 的其他排列会在其它的转移中被考虑到。 - 所以转移就为 $f_{i|(1<<j)} = nxt_{f_i,j}$。因为要保证所有的排列都能够被满足，每个 $f_i$ 在向它转移的 $nxt$ 中取最大值。 - 最后判断 $f_{(1<<n)-1}$ 是否满足条件即可。 ## Code ```cpp #include <cstdio> #include <cstring> #include <iostream> using namespace std; const int MAXM = 460; const int MAXN = 23; const int MAXS = (1<<21) + 10; const int INF = 0x3f3f3f3f; int n, m, T; char s[MAXN]; int f[MAXS], nxt[MAXM][MAXN]; inline bool work() { scanf("%d%s",&n,s+1); int m = strlen(s+1); if(n > 21) return 0; for(int i=0;i<n;i++) nxt[m][i] = INF; for(int i=m;i>=1;i--) // 序列自动机 nxt { for(int j=0;j<n;j++) nxt[i-1][j] = nxt[i][j]; nxt[i-1][s[i]-'a'] = i; } int maxs = 1<<n; for(int i=0;i<maxs;i++) f[i] = 0; for(int s=0;s<maxs;s++) { if(f[s] == INF) return 0; // 如果子集都无法满足，全部也一定不满足 for(int i=0;i<n;i++) { if(((~s)>>i)&1) { if(f[s] == INF) f[s|(1<<i)] = INF; else f[s|(1<<i)] = max(f[s|(1<<i)], nxt[f[s]][i]); } } } return f[maxs-1] != INF; } int main() { scanf("%d",&T); while(T--) puts(work()?"YES":"NO"); return 0; } ```