JZOJ 3293. 阶乘字符串

题目

 

Description

给定一个由前n个小写字母组成的串S。

串S是阶乘字符串当且仅当前n个小写字母的全排列（共n!种）都作为S的子序列（可以不连续）出现。

由这个定义出发，可以得到一个简单的枚举法去验证，但是它实在太慢了。所以现在请你设计一个算法，在1秒内判断出给定的串是否是阶乘字符串。

 

 

 

Input

输入第1行一个整数T，表示这个文件中会有T组数据。

接下来分T个块，每块2行：

第1行一个正整数n，表示S由前n个小写字母组成。

第2行一个字符串S。

Output

对于每组数据，分别输出一行。每行是YES或者NO，表示该数据对应的串S是否是阶乘字符串。

 

 

 

Sample Input

2

2

bbaa

2

aba

Sample Output

NO

YES

 

 

 

Data Constraint

 

 

 

Hint

样例解释：

第一组数据中，ab这个串没有作为子序列出现。

 

 

分析

 

• 设f[s]为满足阶乘字符串的集合的最后一个字母的位置
  

• g[i][j]表示以i+1开始的第一个j字母出现的位置。

  然后枚举子集转移，最后判断一下是否满足f[(1<<n)−1]≤m 即可，本题解决。

 

代码

 

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
using namespace std;
int g[1001][1001];
int f[10000001];
string s;
int n;
int main ()
{
    int T;
    cin>>T;
    while(T)
    {
        T--;
        cin>>n;
        cin>>s;
        int m=1<<n;
        int len=s.size();
        if (n>21)
        {
            cout<<"NO"<<endl;
            continue;
        }
        for (int i=0;i<n;i++) g[len][i]=g[len+1][i]=len+1;
        for (int i=len;i;i--)
        {
            for (int j=0;j<n;j++) g[i-1][j]=g[i][j];
            g[i-1][s[i-1]-'a']=i;
         } 
         memset(f,0,sizeof(f));
         for (int i=1;i<m;i++)
         {
             for (int j=0;j<n;j++)
             {
                 if (i&(1<<j)) f[i]=max(f[i],g[f[i^(1<<j)]][j]);
             }
          }
          if (f[m-1]<=len) cout<<"YES"<<endl;
          else cout<<"NO"<<endl;
    }
}