本文主要是介绍hnu 病毒，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
| 病毒 |
| Time Limit: 1000ms, Special Time Limit:2500ms, Memory Limit:32768KB |
| Total submit users: 36, Accepted users: 19 |
| Problem 10104 : No special judgement |
| Problem description |
| 二进制病毒审查委员会最近发现了如下的规律：某些确定的二进制串是病毒的代码。如果某段代码中不存在任何一段病毒代码，那么我们就称这段代码是安全的。现在委员会已经找出了所有的病毒代码段，试问，是否存在一个无限长的安全的二进制代码。例如如果{011, 11, 00000}为病毒代码段，那么一个可能的无限长安全代码就是010101…。如果{01, 11, 000000}为病毒代码段，那么就不存在一个无限长的安全代码。任务：请写一个程序：读入病毒代码；判断是否存在一个无限长的安全代码；将结果输出。 |
| Input |
| 第一行包括一个整数n，表示病毒代码段的数目。以下的n行每一行都包括一个非空的01字符串——就是一个病毒代码段。所有病毒代码段的总长度不超过30000。 |
| Output |
| 输出一个单词：TAK——假如存在这样的代码；NIE——如果不存在 |
| Sample Input |
3 01 11 00000 |
| Sample Output |
NIE |
| Problem Source |
| SDOI |
| Submit Discuss Judge Status Problems Ranklist |
AC自动机+判环
思路：题目给出了最多3w个节点，采用 dfs 判环，在第一次搜到的时候标号为1，然后回溯的时候标号为-1，如果遇到1的节点就说明有环，标号为0表示还没有遍历到的点，这个思路是问的队友的
#include <cstdlib>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <queue>using namespace std;const int NODE=30010;
int chd[NODE][2],word[NODE],fail[NODE],sz;
char s[NODE];void ins(char *s)
{int p=0;for(;*s;s++){int id=*s-'0';if(!chd[p][id]){memset(chd[sz],0,sizeof(chd[sz]));word[sz]=0;chd[p][id]=sz++;}p=chd[p][id];}word[p]=1;
}
void ac()
{queue<int> q;if(chd[0][0]) q.push(chd[0][0]),fail[chd[0][0]]=0;if(chd[0][1]) q.push(chd[0][1]),fail[chd[0][1]]=0;for(;!q.empty();q.pop()){int p=q.front();for(int i=0;i<2;i++)if(chd[p][i]){q.push(chd[p][i]);fail[chd[p][i]]=chd[fail[p]][i];word[chd[p][i]]|=word[fail[chd[p][i]]];}else chd[p][i]=chd[fail[p]][i];}
}int dfn[NODE],index;bool dfs(int u)
{dfn[u]=1;for(int i=0;i<2;i++){int v=chd[u][i];if(word[v]) continue;if(dfn[v]==1) return 1;if(dfn[v]==0&&dfs(v)) return 1;}dfn[u]=-1;return 0;
}
int main()
{int n;while(scanf("%d",&n)==1){memset(chd[0],0,sizeof(chd[0]));sz=1;for(int i=0;i<n;i++){scanf("%s",s);ins(s);}ac();bool ok=0;memset(dfn,0,sizeof(dfn));index=1;for(int i=0;i<sz;i++)if(!dfn[i]&&dfs(i)) { ok=1;break; }puts(ok?"TAK":"NIE");}return 0;
}
这篇关于hnu 病毒的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
