bzoj2938 [Poi2000]病毒

bzoj2938 [Poi2000]病毒

​​ Description

二进制病毒审查委员会最近发现了如下的规律：某些确定的二进制串是病毒的代码。如果某段代码中不存在任何一段病毒代码，那么我们就称这段代码是安全的。现在委员会已经找出了所有的病毒代码段，试问，是否存在一个无限长的安全的二进制代码。 示例： 例如如果{011, 11, 00000}为病毒代码段，那么一个可能的无限长安全代码就是010101…。如果{01, 11, 000000}为病毒代码段，那么就不存在一个无限长的安全代码。 任务： 请写一个程序： l 读入病毒代码； l 判断是否存在一个无限长的安全代码； l 将结果输出 Input

第一行包括一个整数n，表示病毒代码段的数目。以下的n行每一行都包括一个非空的01字符串——就是一个病毒代码段。所有病毒代码段的总长度不超过30000。 Output

你应在在文本文件WIN.OUT的第一行输出一个单词： l TAK——假如存在这样的代码； l NIE——如果不存在。 Sample Input

3 01 11 00000 Sample Output

NIE HINT

Source

建出AC自动机拓扑排序判环即可

#include#include#include#include#define N 30030using namespace std;int trans[N][2],fail[N],cnt=1,n,in[N];char s[N]; bool end[N];inline void insert1(char s[]){ int len=strlen(s+1);int p=1; for (int i=1,nxt;i<=len;++i) { if (!trans[p][s[i]-'0']) trans[p][s[i]-'0']=nxt=++cnt; else nxt=trans[p][s[i]-'0'];p=nxt; }end[p]=1;}inline void buildAC(){ queueq;q.push(1);trans[0][0]=trans[0][1]=1; while(!q.empty()){ int x=q.front();q.pop(); for(int i=0;i<=1;++i){ if (trans[x][i])fail[trans[x][i]]=trans[fail[x]][i],q.push(trans[x][i]);else {trans[x][i]=trans[fail[x]][i];continue;}end[trans[x][i]]|=end[fail[trans[x][i]]]; } }}int main(){ freopen("bzoj2938.in","r",stdin); scanf("%d",&n);queueq; for (int i=1;i<=n;++i) scanf("%s",s+1),insert1(s);buildAC(); for (int i=0;i<=cnt;++i) { if(end[i]) continue; for (int j=0;j<=1;++j) if (!end[trans[i][j]])++in[trans[i][j]]; }for (int i=0;i<=cnt;++i) if (!in[i]&&!end[i]) q.push(i); while(!q.empty()){ int x=q.front();q.pop(); for (int i=0;i<=1;++i){ if(end[trans[x][i]]) continue; if(!--in[trans[x][i]]) q.push(trans[x][i]); } }for (int i=0;i<=cnt;++i) if (in[i]&&i!=1) {puts("TAK");return 0;}puts("NIE"); return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。