首页 > 代码库 > [bzoj 2938] [Poi2000]病毒]

[bzoj 2938] [Poi2000]病毒]

2024-09-27 16:54:02   216人阅读

传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=2938

[Poi2000]病毒

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 870  Solved: 447
[Submit][Status][Discuss]

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

建出ac自动机，把非法的节点向前并，这样就成了一个图，

由题意得，我们要构造的字符串，要让ac自动机匹配不到任意一个答案。

也就是这个图形成了一个环。

我连有向图判环都写错了

 1 #include<cstdio> 2 #include<cstring> 3 const int maxn = 300006; 4 char ch[maxn]; 5 int n; 6 int a[maxn][4],point[maxn],q[maxn],sz=1; 7 bool danger[maxn]; 8 bool inq[maxn],vis[maxn]; 9 void ins(){10     int now=1,c;11     int len=strlen(ch);12     for(int i=0;i<len;i++){13         c=ch[i]-‘0‘+1;14         if(a[now][c])now=a[now][c];15         else now=a[now][c]=++sz;16     }17     danger[now]=1;18 }19 void acm(){20     for(int i=1;i<=2;i++)a[0][i]=1;21     int l=0,r=0;22     point[1]=0;q[r++]=1;23     while(l<r){24         int now=q[l++];25         for(int i=1;i<=2;i++){26             if(a[now][i]==0){27                 a[now][i] = a[point[now]][i];28                 continue;29             }30             int k=point[now];31             while(!a[k][i])k=point[k];32             point[a[now][i]]=a[k][i];33             danger[a[now][i]]|=danger[a[k][i]];34             q[r++]=a[now][i];35         }36     }37 }38 void dfs(int x){39     printf("%d %d\n",x,point[x]);40     for(int i=1;i<=2;i++){41         if(a[x][i]){42             dfs(a[x][i]);43         }44          45     }46 }47 bool check(int x){48     inq[x]=1;49     for(int i=1;i<=2;i++){50         int to=a[x][i];51         if(inq[to]==1)return 1;52         if(danger[to]||vis[to])continue;53         vis[to]=1;54         if(check(to))return 1;55     }56     inq[x]=0;57     return 0;58 }59 int main(){60     scanf("%d",&n);61     for(int i=1;i<=n;i++){62         scanf("%s",ch);63         ins();64     }65     acm();66     check(1)?puts("TAK"):puts("NIE");67     return 0;68 }

 

[bzoj 2938] [Poi2000]病毒]


联系
我们