BZOJ 4416 【SHOI2013】阶乘字符串

　　又是一道不会做的题……看了题解后我被吓傻了……

　　首先我们可以有一个显然的\(O(2^nn)\)的做法。我们先预处理出\(g_{i,j}\)表示字符串中\(i\)号位置开始第一个\(j\)字符出现在什么位置。然后就可以用\(f_S\)表示使得\(S\)集合内字符的排列全都出现的最小长度，然后就可以递推了。

　　然后……翻了一波题解，发现当\(n>21\)的时候无解……听说合法的串长应该是\(n^2\)级别的，所以当\(n>21\)的时候就无解了……然后就可以\(O(2^nn)\)艹过去了……

　　下面贴代码：

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<cmath>

#define File(s) freopen(s".in","r",stdin),freopen(s".out","w",stdout)

using namespace std;

typedef long long llg;

int T,n,g[500][26],m;

int f[1<<21],fr[1<<21];

char s[500];

int main(){

	File("a");

	scanf("%d",&T);

	for(int i=0;i<21;i++) fr[1<<i]=i;

	while(T--){

		scanf("%d %s",&n,s+1); m=strlen(s+1);

		if(n>21){puts("NO");continue;}

		for(int i=0;i<26;i++) g[m+1][i]=m+1;

		for(int i=m;i>=0;i--){

			for(int j=0;j<26;j++) g[i][j]=g[i+1][j];

			if(i) g[i][s[i]-'a']=i;

		}

		bool ans=1;

		for(int S=1;S<(1<<n);S++){

			f[S]=0;

			for(int s=S,x,i;s;s-=x){

				x=s&(-s); i=fr[x];

				f[S]=max(f[S],g[f[S^x]][i]);

			}

			if(f[S]>m){ans=0;break;}

		}

		printf(ans?"YES\n":"NO\n");

	}

	return 0;

}

巴特西

BZOJ 4416 【SHOI2013】阶乘字符串

最新文章

热门文章

巴特西

BZOJ 4416 【SHOI2013】 阶乘字符串

最新文章

热门文章

BZOJ 4416 【SHOI2013】阶乘字符串