本文共 1300 字，大约阅读时间需要 4 分钟。

先建出序列自动机,那么可以在字符集的时间内判断一个串是不是阶乘字符串

如果枚举排列去验证复杂度不对,考虑$dp$

然后发现状态的定义几乎只能这么定义

$f[i][s]$表示前$i$个字符满足状态为$s$的字符集的阶乘字符串

但是发现并不好转移,在原来的基础上加入新的字符,无法判断是否能转移

重新定义状态

$f[s]$表示字符集为$s$的阶乘字符串最早满足的位置是$[1,f[s]]$

$f[s]$可以由状态$f[a_1],f[a_2],f[a_3]...$转移而来

其中$a_1,a_2,a_3$之和$s$相差一个字符

那么设$f[a_1]$后面第一个出现的缺失字符位置在$q$,那么$f[s]$的答案至少是$q$

设$f[a_2]$后面第一个出现缺失字符的位置在$w$,那么$f[s]$的答案至少是$w$

…

一次类推,我们不断取$max$就能得到$f[s]$的最小值

这样一定是一个阶乘字符串,因为我们考虑了每一个字符结尾的情况,而且结尾前都是阶乘字符串

#include 
   
    using namespace std;const int maxn = 1e7+10;int t,n,f[maxn],nxt[1998][27];char a[maxn],b[maxn];int main(){
   	cin >> t;	while( t-- )	{
   		cin >> n >> ( a+1 ); int len = strlen( a+1 );		if( n>21 ) {
    cout << "NO\n"; continue; }		for(int i=0;i<=26;i++)	nxt[len][i] = 1e9;		for(int i=len-1;i>=0;i--)		{
   			for(int j=0;j<=25;j++)	nxt[i][j] = nxt[i+1][j];			nxt[i][a[i+1]-'a'] = i+1;		}		memset( f,0,sizeof f );		for(int i=1;i<(1<
    
     =1e9 )	f[i] = f[u];				else	f[i] = max( f[i],nxt[f[u]][j] );			}		}		if( f[(1<
     
      <=len  )	cout << "YES\n";		else	cout << "NO\n";	}} //Fe+O2=Fe3O4
     
    
   

转载地址：https://issue-is-vegetable.blog.csdn.net/article/details/116241504 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！