【bzoj1559】[JSOI2009]密码

2015.06.12 19:59 Fri | 21次阅读 | 旧日oi | 固定链接 | 源码

题目大意

求只包含小写字母的长度为L的串的个数,要求这些串包含给定的一些单词(可重叠)。单词个数<=10,长度<=10,L<=25,如果答案小于42要求输出方案

题解

这种题一看就是ac自动机嘛,把n个串建成ac自动机,然后dp一下就行了,输出方案的话由于ans非常小,所以可以采用记录每个状态的前驱状态,然后搜索就行了。
代码能力!代码能力!这么水的题调一下午!!!!

我的程序

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
using namespace std;
int l,n,cnt=1,tot;
struct Node
{
    int node,w,msk,next;
}e[10005];
long long dp[26][101][1024];
bool vis[26][101][1024];
int h[26][101][1024],dex;
char s[15];
int son[101][26],mark[101],fail[101],alp[101];
string rec[43];
struct ACM
{
    void insert(int k)
    {
        scanf("%s",s);
        int now,i,x=1,len=strlen(s);
        for(i=0;i<len;i++)
        {
            now=s[i]-'a';
            if(!son[x][now])
            {
                son[x][now]=++cnt;
                alp[cnt]=now;
            }
            x=son[x][now];
        }
        mark[x]=(1<<k);
    }
    queue<int> q;
    void build()
    {
        for(int i=0;i<26;i++)
        {
            if(!son[1][i]) son[1][i]=1;
            else
            {
                fail[son[1][i]]=1;
                q.push(son[1][i]);
            }
        }
        while(!q.empty())
        {
            int u=q.front();q.pop();
            mark[u]|=mark[fail[u]];
            for(int i=0;i<26;i++)
            if(son[u][i])
            {
                int v=son[u][i];
                fail[v]=son[fail[u]][i];
                q.push(v);
            }
            else son[u][i]=son[fail[u]][i];
        }
    }
    void dfs(int len,int no,int st,string w)
    {
        if(!len)
        {
            rec[++tot]=w;
            return;
        }
        for(int i=h[len][no][st];i;i=e[i].next)
        dfs(len-1,e[i].node,e[i].msk,char(e[i].w+'a')+w);
    }
    void DP()
    {
        dp[0][1][0]=1;
        for(int i=0;i<l;i++)
        for(int j=1;j<=cnt;j++)
        for(int k=0;k<(1<<n);k++)
        if(dp[i][j][k])
        {
            for(int p=0;p<26;p++)
            {
                int nxt=son[j][p];
                dp[i+1][nxt][k|mark[nxt]]+=dp[i][j][k];
            }
        }
        long long ans=0;
        for(int i=1;i<=cnt;i++)
        if(dp[l][i][(1<<n)-1])
        {
            ans+=dp[l][i][(1<<n)-1];
            vis[l][i][(1<<n)-1]=1;
        }
        printf("%lld\n",ans);
        if(ans<=42)
        {
            for(int i=l-1;i+1;i--)
            for(int j=1;j<=cnt;j++)
            for(int k=0;k<(1<<n);k++)
            if(dp[i][j][k])
            {
                for(int p=0;p<26;p++)
                {
                    int nxt=son[j][p];
                    int st=k|mark[nxt];
                    if(vis[i+1][nxt][k|mark[nxt]])
                    {
                        vis[i][j][k]=1;
                        ++dex;
                        e[dex].msk=k;
                        e[dex].next=h[i+1][nxt][st];
                        e[dex].w=p;
                        e[dex].node=j;
                        h[i+1][nxt][st]=dex;
                    }
                }
            }
            for(int i=1;i<=cnt;i++)
            if(vis[l][i][(1<<n)-1])
            dfs(l,i,(1<<n)-1,"");
            sort(rec+1,rec+tot+1);
            for(int i=1;i<=tot;i++)
            cout<<rec[i]<<endl;
        }
    }
}acm;
int main()
{
    cin>>l>>n;
    for(int i=0;i<n;i++) acm.insert(i);
    acm.build();
    acm.DP();
}```