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

时间：2022-09-18 15:27:04

正解:$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;

}

随机推荐

  1. SQLServer2005如何批量修改架构名 - wuxiaokaixinguo的专栏

    原文地址:http://blog.csdn.net/wuxiaokaixinguo/article/details/8523093 ) BEGIN SET @name='原构架名.' + @name ...

  2. VBA用户控件

    窗体相关 1.显示窗体 UserForm1.show  [vbModeless] vbModeless 可选参数,参数设定后,变成无模式窗体.窗体保持显示状态,仍可操作Excel文件. UserFor ...

  3. Java 集合系列12之 TreeMap详细介绍&lpar;源码解析&rpar;和使用示例

    概要 这一章,我们对TreeMap进行学习.我们先对TreeMap有个整体认识,然后再学习它的源码,最后再通过实例来学会使用TreeMap.内容包括:第1部分 TreeMap介绍第2部分 TreeMa ...

  4. Java位操作全面总结

    转载: Java位操作全面总结 在计算机中所有数据都是以二进制的形式储存的.位运算其实就是直接对在内存中的二进制数据进行操作,因此处理数据的速度非常快.在实际编程中,如果能巧妙运用位操作,完全可以达到 ...

  5. &lbrack;OC Foundation框架 - 1&rsqb; 常用结构体

    底层封装是使用了typedef定义的结构体 typedef struct _NSString{ xxx xxx } NSString;   1. NSRange 结构体 #注意结构体不是对象 3种定义 ...

  6. java技术栈&colon;一、java编程语言概述

    Java是一种编程语言,起源于20世纪90年代初Sun公司的一个叫Green的项目,该项目主要目的是是开发嵌入家用电器的分布式软件系统,从而使电器更加智能化.因为项目小组成员皆为C++的高手(那个年代 ...

  7. AE-分享&lt&semi;学习后&comma;制作的视频实例&gt&semi;小视频-与大家交流&excl;

  8. Python学习笔记3-文件的简单操作

    Python中的文件操作 Python中文件打操作离不开两个模块  os 和 shutil os:操作文件.目录: Python os模块包含普遍的操作系统功能.如果你希望你的程序能够与平台无关的话, ...

  9. 国产编程语言R&plus;&plus; V1&period;5发布

    R++ v1.5内核改动较大,下面是一些主要变化: 1.使用PJIT(Pseudocode Just-In-Time),编译速度大幅提高,但运行效率远远不如C++,不过R++将在下一版本支持RJIT( ...

  10. OWIN 自托管静态网站

    我们知道,借助OWIN,WebApi,SignalR,WCF 都可以创建自托管(Self-Host)实例,完全不需要IIS,静态网站也可以. 最近做一个服务器监控小工具,用 SignalR 通信,监控 ...

相关文章