题解 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
#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;
}