正解:$dp$+$AC$自动机+搜索

解题报告:

传送门$QwQ$

首先显然先建个$AC$自动机,然后考虑设$f_{i,j,k}$表示长度为$i$,现在在$AC$自动机的第$j$个位置,已经表示出来的串的状态为$k$的方案数,直接转移就好.

然后考虑输出方案.首先一定不存在可以随便填的位置.

挺显然的随便说下昂,首先如果有一个可以随便填的位置,就有26种可能.然后可以给这个位置和字符串交换位置,就至少有2种可能,这时候就已经至少有$2\times 26=52$了,所以一定不存在可以随便填的位置.

所以直接$O(!n)$爆搜$QwQ$,$over$

因为爆搜真的很麻烦,所以我直接开了个$vector$在$dp$转移的时候顺便记了下方案.

但是挺容易$MLE$的,所以我把第一维滚了下.

然后还有一个注意点是每次转移完之后没用的$vector$清空下不然真的$MLE$到飞起$kk$

#include<bits/stdc++.h>

using namespace std;

#define il inline

#define gc getchar()

#define ll long long

#define ri register int

#define rb register bool

#define rc register char

#define rp(i,x,y) for(ri i=x;i<=y;++i)

#define my(i,x,y) for(ri i=x;i>=y;--i)

const int N=100+10,M=(1<<10)+10;

int len,n,nod_cnt,tot,nw=1,pre;

ll f[2][N][M],ans;

bool vis[N];

char s[N];

vector<string>as[2][N][M],an;

struct node{int to[27],zt,fail;}nod[N];

il int read()

{

    rc ch=gc;ri x=0;rb y=1;

    while(ch!='-' && (ch>'9' || ch<'0'))ch=gc;

    if(ch=='-')ch=gc,y=0;

    while(ch>='0' && ch<='9')x=(x<<1)+(x<<3)+(ch^'0'),ch=gc;

    return y?x:-x;

}

il void insert(ri num)

{

    scanf("%s",s+1);ri l=strlen(s+1),nw=0;

    rp(i,1,l)

    {

        if(!nod[nw].to[s[i]-'a'])nod[nw].to[s[i]-'a']=++nod_cnt;

        nw=nod[nw].to[s[i]-'a'];

    }

    nod[nw].zt=1<<num;

}

il void build()

{

    queue<int>Q;

    rp(i,0,25)if(nod[0].to[i])Q.push(nod[0].to[i]);

    while(!Q.empty())

    {

        ri nw=Q.front();Q.pop();

        rp(i,0,25)

            if(nod[nw].to[i])Q.push(nod[nw].to[i]),nod[nod[nw].to[i]].fail=nod[nod[nw].fail].to[i];

            else nod[nw].to[i]=nod[nod[nw].fail].to[i];

        nod[nw].zt|=nod[nod[nw].fail].zt;

    }

}

signed main()

{

    //freopen("4045.in","r",stdin);freopen("4045.out","w",stdout);

    len=read();n=read();rp(i,1,n)insert(i-1);build();tot=(1<<n)-1;

    f[0][0][0]=1;as[0][0][0].push_back("");

    rp(i,1,len)

    {

        rp(j,0,nod_cnt)

        {

            rp(k,0,tot)

            {

                if(f[pre][j][k])

                {

                    rp(t,0,25)

                    {

                        ri nwzt=k|nod[nod[j].to[t]].zt;

                        f[nw][nod[j].to[t]][nwzt]+=f[pre][j][k];

                        if(f[nw][nod[j].to[t]][nwzt]<=42)

                        {

                            ri sz=as[pre][j][k].size();

                            rp(tt,0,sz-1)as[nw][nod[j].to[t]][nwzt].push_back(as[pre][j][k][tt]+(char)(t+'a'));

                        }

                    }

                }

                f[pre][j][k]=0;if(!as[pre][j][k].empty())as[pre][j][k].clear();

            }

        }

        nw^=1;pre^=1;

    }

    nw^=1;

    rp(i,0,nod_cnt)

    {

        ans+=f[nw][i][(1<<n)-1];

        if(ans<=42){ri sz=as[nw][i][(1<<n)-1].size();rp(j,0,sz-1)an.push_back(as[nw][i][(1<<n)-1][j]);}

    }

    printf("%lld\n",ans);if(ans>42)return 0;

    sort(an.begin(),an.end());rp(i,0,ans-1)cout<<an[i]<<endl;

    return 0;

}

巴特西

洛谷$P4045\ [JSOI2009]$密码 $dp$+$AC$自动机

正解:$dp$+$AC$自动机+搜索

解题报告:

最新文章

热门文章