Description
二进制病毒审查委员会最近发现了如下的规律: 某些确定的二进制串是病毒的代码. 如果某段代码中不存在任何一段病毒代码, 那么我们就称这段代码是安全的. 现在委员会已经找出了所有的病毒代码段, 试问, 是否存在一个无限长的安全的二进制代码.
示例:
例如如果 {011, 11, 00000} 为病毒代码段, 那么一个可能的无限长安全代码就是 010101.... 如果 {01, 11, 000000} 为病毒代码段, 那么就不存在一个无限长的安全代码.
任务:
请写一个程序:
l 读入病毒代码;
l 判断是否存在一个无限长的安全代码;
l 将结果输出
只要 trie 图上有一个能从 0 到达且没有结束标记的环, 我们就可以在那个环上绕啊绕啊绕啊
- #include<iostream>
- #include<cstdio>
- #include<cstring>
- #include<queue>
- #define M 800001
- using namespace std;
- int n,m,k,cnt,d[M][2],a[M],fail[M],e[M];
- char c[M];
- bool b[M],bl[M];
- queue<int>q;
- void ins(char* s)
- {
- int l=strlen(s), now=0;
- for(int i=0;i<l;i++)
- {
- if(!d[now][s[i]-'0']) d[now][s[i]-'0']=++cnt;
- now=d[now][s[i]-'0'];
- }
- e[now]=1;
- }
- void built()
- {
- if(d[0][0]) q.push(d[0][0]);
- if(d[0][1]) q.push(d[0][1]);
- while(q.size())
- {
- int x=q.front(); q.pop();
- if(e[fail[x]]) e[x]=1;
- if(d[x][0])fail[d[x][0]]=d[fail[x]][0], q.push(d[x][0]);
- else d[x][0]=d[fail[x]][0];
- if(d[x][1]) fail[d[x][1]]=d[fail[x]][1], q.push(d[x][1]);
- else d[x][1]=d[fail[x]][1];
- }
- }
- bool bfs(int x)
- {
- if(e[x]) return 0;
- if(bl[x]) return 1;
- if(b[x]) return 0;
- bl[x]=b[x]=1;
- if(bfs(d[x][0])) return 1;
- if(bfs(d[x][1])) return 1;
- bl[x]=0;
- return 0;
- }
- int main()
- {
- scanf("%d",&n);
- for(int i=1;i<=n;i++) scanf("%s",c), ins(c);
- built();
- if(bfs(0)) printf("TAK");
- else printf("NIE");
- }
2938: [Poi2000]病毒
来源: http://www.bubuko.com/infodetail-2921066.html