P4045 [JSOI2009]密码

题目

P4045 [JSOI2009]密码

做法

AC自动机+状压+爆搜

建AC自动机是显然的，顺便预处理\(lst_i\)表示\(i\)结点以哪些串结束(二进制)

然后跑状压\(dp[i][j][k]\)表\(i\)长度现在在\(j\)结点已经出现的串\(k\)，理解：自由结点则由根节点\(0\)传递

毒瘤的地方在于输出串，显然\(ans<=42\)时，没有自由结点

两遍爆搜：

\(~~~~~\)第一遍预处理\(visit[i][j][k]\)，其中\(i,j,k\)和\(dp\)数组相同，数组内存的值表示是否有效

\(~~~~~\)第二遍直接跑\(visit\)，有效才能搜过去

My complete

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<string>

#include<iostream>

#include<cmath>

#include<queue>

using namespace std;

typedef int LL;

const LL maxn=200;

LL L,n,nod,Up;

long long ans;

LL lst[maxn],son[maxn][26],fail[maxn];

long long dp[30][maxn][1<<11];

inline void Insert(char *s,LL id){

	LL Len(strlen(s+1)),now(0);

	for(LL i=1;i<=Len;++i){

		LL c(s[i]-'a');

		if(son[now][c]==0) son[now][c]=++nod;

		now=son[now][c];

	}lst[now]=1<<(id-1);

}

inline void F_trie(){

	queue<LL>que;

	for(LL i=0;i<26;++i)

	    if(son[0][i]) que.push(son[0][i]);

	while(que.size()){

		LL u(que.front()); que.pop();

		lst[u]|=lst[fail[u]];

		for(LL i=0;i<26;++i){

			LL v(son[u][i]);

			if(v){

				fail[v]=son[fail[u]][i];

				que.push(v);

			}else son[u][i]=son[fail[u]][i];

		}

	}

}

LL sta[30],visit[30][maxn][1<<11];

void Dfs(LL len,LL now,LL bit){

	if(len==L){

		for(LL i=0;i<L;++i)

		    printf("%c",sta[i]+'a');printf("\n");

		return;

	}

	for(LL i=0;i<26;++i){

		LL v(son[now][i]);

		if(v==0||visit[len+1][v][bit|lst[v]]!=1) continue;

		sta[len]=i;

		Dfs(len+1,v,bit|lst[v]);

	}

}

bool First(LL len,LL now,LL bit){

	if(visit[len][now][bit]==1) return true;

	else if(visit[len][now][bit]==-1) return false;

	else if(len==L){

		visit[len][now][bit]=-1; return false;

	}

	for(LL i=0;i<26;++i){

		LL v(son[now][i]);

		if(v==0) continue;

		if(First(len+1,v,bit|lst[v]))

		    visit[len][now][bit]=1;

	}

	if(visit[len][now][bit]!=1){

	    visit[len][now][bit]=-1;

	    return false;

	}return true;

}

inline void Solve(){

	for(LL i=0;i<L;++i)

		for(LL u=0;u<=nod;++u)

		    for(LL pre=0;pre<Up;++pre)

		        if(dp[i][u][pre]) First(i,u,pre);

    Dfs(0,0,0);

}

char s[maxn];

int main(){

	scanf("%d %d",&L,&n);

	for(LL i=1;i<=n;++i){

		scanf(" %s",s+1),

		Insert(s,i);

	}F_trie();

	Up=(1<<n);

	dp[0][0][0]=1;

	for(LL i=1;i<=L;++i)

	    for(LL u=0;u<=nod;++u)

	        for(LL pre=0;pre<Up;++pre){

	        	if(dp[i-1][u][pre]==0) continue;

	        	for(LL k=0;k<26;++k){

	        		LL v(son[u][k]);

	        		dp[i][v][pre|lst[v]]+=dp[i-1][u][pre];

				}

			}

	for(LL i=0;i<=nod;++i){

		if(dp[L][i][Up-1])

			visit[L][i][Up-1]=1,

	        ans+=dp[L][i][Up-1];

		else visit[L][i][Up-1]=-1;

	}

	printf("%lld\n",ans);

	if(ans<=42)

		Solve();

	return 0;

}/*

*/

巴特西

P4045 [JSOI2009]密码

题目

做法

My complete

最新文章

热门文章