题目描述
给定一个由前(n)个小写字母组成的串(S)。
串(S)是阶乘字符串当且仅当前(n)个小写字母的全排列（共(n!)种）都作为(S)的子序列（可以不连续）出现。
由这个定义出发，可以得到一个简单的枚举法去验证，但是它实在太慢了。所以现在请你设计一个算法，在(1)秒内判断出给定的串是否是阶乘字符串。
输入格式
输入第(1)行一个整数(T)，表示这个文件中会有(T)组数据。
接下来分(T)个块，每块(2)行：
第(1)行一个正整数(n)，表示(S)由前(n)个小写字母组成。
第(2)行一个字符串(S)。
输出格式
对于每组数据，分别输出一行。每行是(YES)或者(NO)，表示该数据对应的串(S)是否是阶乘字符串。
样例输入
2
2
bbaa
2
aba
样例输出
NO
YES
【样例解释】
第一组数据中，ab这个串没有作为子序列出现。
数据范围
解题报告
题意理解
这道题目,有一点点绕? 可能是我太菜了
我们初步读题可知,题目要求我们判断一个字符串.
给你一个(N),如果说一个字符串满足(N)的全排列字符串
而且这些字符串,都以序列的形式出现在这个字符串,那么我们称之为合法,否则不合法.
算法解析
这道题目运用的是.状态压缩DP.
首先我们思考一下,这道题目(N leq 26),这个数据范围似乎不太好状态压缩?
数据太大了....
但是我们发现,其实(N ge 21),完全可以判断无解.
这是为什么,有证明吗?
当(n ge 21)的时候
假设(|S| = 450)
在|S|中任意取21个数字
$ C(450, 21) < 21！$
说明这(450)个字符不能完全凑成(n!)个序列。
接下来我们着重分析一下,状态压缩思想.
我们知道状态压缩其实就是 集合二进制枚举 处理.
那么既然如此,我们不妨设置一下 状态表示.
- 状态是一个 集合
- 题目要求 全排列合法
- 一般题目中,总会有 最后一位,也就是转移过来的元素
设(f[S])表示当(S)中集合中的字母构成的排列均在原序列([1,f[S]])出现的最小值。
既然如此的话.
我们不妨预处理一下.
(g[i][j])表示从(i)开始下一个字母(j)出现的位置。
总而言之,我们就是利用 刷表法则,一步步推导状态.
因此我们不妨设置核心程序.
for(int S=1; S<(1<<n); S++)//枚举子集
{
int cnt=0;
for(int i=0; i<n; i++)
if(S & (1<<i) ) //s集合拥有这一位,其实也就是i结尾
cnt=max(cnt,g[f [S^(1<<i) ]][i] );//排除这一位,然后转移过来
f[S]=cnt;//更新
}
代码解析
#include <bits/stdc++.h>
using namespace std;
const int N=460;
#define read(x) scanf("%d",&x)
int t,n,m,g[N][32],f[1<<21];
char s[N];
inline void init()
{
read(t);
while(t--)
{
read(n);
scanf("%s",s+1);//默认读入从1开始
m=strlen(s+1);
if (n>21)//特殊判定无解情况
{
puts("NO");
continue;
}
for(int i=m+1; i>=0; i--)//从i开始下一个j出现的位置
{
for(int j=0; j<n; j++)
g[i][j]=( i>=m ? m+1 : g[i+1][j] ); //前面的位置,最近的是当前这位的
if(i!=m)
g[i][ s[i+1]-'a' ]=i;//当前位为最近的
}
for(int S=1; S<(1<<n); S++)//枚举子集
{
int cnt=0;
for(int i=0; i<n; i++)
if(S & (1<<i) ) //s集合拥有这一位,其实也就是i结尾
cnt=max(cnt,g[f [S^(1<<i) ]][i] );//排除这一位,然后转移过来
f[S]=cnt;//更新
}
printf("%s
",f[ (1<<n)-1 ] <=m ? "YES":"NO" );//是否存在
}
}
int main()
{
init();
return 0;
}