首页 > 代码库 > 【BZOJ1030】【JSOI2007】文本生成器

【BZOJ1030】【JSOI2007】文本生成器

2024-09-08 08:02:37   218人阅读

我现在连AC自动姬都不会，怎么办嘛QAQ

原题：

JSOI交给队员ZYX一个任务，编制一个称之为“文本生成器”的电脑软件：该软件的使用者是一些低幼人群，
他们现在使用的是GW文本生成器v6版。该软件可以随机生成一些文章―――总是生成一篇长度固定且完全随机的文
章—— 也就是说，生成的文章中每个字节都是完全随机的。如果一篇文章中至少包含使用者们了解的一个单词，
那么我们说这篇文章是可读的（我们称文章a包含单词b，当且仅当单词b是文章a的子串）。但是，即使按照这样的
标准，使用者现在使用的GW文本生成器v6版所生成的文章也是几乎完全不可读的?。ZYX需要指出GW文本生成器 v6
生成的所有文本中可读文本的数量，以便能够成功获得v7更新版。你能帮助他吗？

N <= 60，所有单词及文本的长度不会超过100

 

如果一个串的后缀不能选，这个串当然也不能选

延伸到AC自动姬上就是如果一个串fail指向的节点不能选，这个节点就不能选

然后就可以预处理出那些节点不能选

然后用f[i][j]表示在文本串走到i时AC自动姬上走到j节点的方案数

首先外层枚举i，再枚举j，如果j可选，就枚举26个字符k，f[i][j]就给j沿着k往下能走到的状态（包括走fail）v贡献

能理解这道题怎么写，但是似乎不能往更广泛的地方延伸，想不动东西……感觉状态不是很好啊QAQ

代码：

技术分享 
 1 #include<iostream>
 2 #include<cstdio>
 3 #include<algorithm>
 4 #include<cstring>
 5 #include<cmath>
 6 using namespace std;
 7 const int dalao=10007;
 8 int rd(){int z=0,mk=1;  char ch=getchar();
 9     while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)mk=-1;  ch=getchar();}
10     while(ch>=‘0‘&&ch<=‘9‘){z=(z<<3)+(z<<1)+ch-‘0‘;  ch=getchar();}
11     return z*mk;
12 }
13 int n,m;
14 char s[110];  int ls;
15 int nxt[6100][26],fl[6100],tt=0;
16 int q[6100],hd=0;
17 bool mk[6100];
18 int f[110][6100];
19 void ist(){
20     int tmp=0;
21     for(int i=1;i<=ls;++i){
22         if(!nxt[tmp][s[i]-‘A‘])  nxt[tmp][s[i]-‘A‘]=++tt;
23         tmp=nxt[tmp][s[i]-‘A‘];
24     }
25     mk[tmp]=true;
26 }
27 void gtac(){
28     for(int i=0;i<26;++i)if(nxt[0][i])  q[++hd]=nxt[0][i];
29     for(int k=1;k<=hd;++k)for(int i=0;i<26;++i){
30         if(!nxt[q[k]][i])  nxt[q[k]][i]=nxt[fl[q[k]]][i];
31         else{
32             fl[nxt[q[k]][i]]=nxt[fl[q[k]]][i],q[++hd]=nxt[q[k]][i];
33             mk[nxt[q[k]][i]]|=mk[nxt[fl[q[k]]][i]];
34         }
35     }
36 }
37 int main(){//freopen("ddd.in","r",stdin);
38     cin>>n>>m;
39     for(int i=1;i<=n;++i)  scanf("%s",s+1),ls=strlen(s+1),ist();
40     gtac();
41     f[0][0]=1;
42     for(int i=1;i<=m;++i)for(int j=0;j<=tt;++j)if(!mk[j] && f[i-1][j])
43         for(int k=0;k<26;++k)
44             f[i][nxt[j][k]]=(f[i][nxt[j][k]]+f[i-1][j])%dalao;
45     int bwl=0,ans=1;
46     for(int i=1;i<=m;++i)  ans=(ans*26)%dalao;
47     for(int i=0;i<=tt;++i)if(!mk[i])  bwl=(bwl+f[m][i])%dalao;
48     cout<<(ans-bwl+dalao)%dalao<<endl;
49     return 0;
50 }
View Code

 

【BZOJ1030】【JSOI2007】文本生成器


联系
我们