[POI2000]病毒 题解
题目地址:洛谷:【P2444】[POI2000]病毒 – 洛谷、BZOJ:Problem 2938. — [Poi2000]病毒
题目描述
二进制病毒审查委员会最近发现了如下的规律:某些确定的二进制串是病毒的代码。如果某段代码中不存在任何一段病毒代码,那么我们就称这段代码是安全的。现在委员会已经找出了所有的病毒代码段,试问,是否存在一个无限长的安全的二进制代码。
示例:
例如如果{011, 11, 00000}为病毒代码段,那么一个可能的无限长安全代码就是010101…。如果{01, 11, 000000}为病毒代码段,那么就不存在一个无限长的安全代码。
任务:
请写一个程序:
1.在文本文件WIR.IN中读入病毒代码;
2.判断是否存在一个无限长的安全代码;
3.将结果输出到文件WIR.OUT中。
输入输出格式
输入格式:
在文本文件WIR.IN的第一行包括一个整数n(n≤2000),表示病毒代码段的数目。以下的n行每一行都包括一个非空的01字符串——就是一个病毒代码段。所有病毒代码段的总长度不超过30000。
输出格式:
在文本文件WIR.OUT的第一行输出一个单词:
TAK——假如存在这样的代码;
NIE——如果不存在。
输入输出样例
输入样例#1:
3 01 11 00000
输出样例#1:
NIE
题解
这个题要找的是一个无限的安全代码,我们考虑用AC自动机的理论来做。
如果把AC自动机的fail和边全部看成有向边,这个图就叫做trie图,图上的某一条路径可以代表我们匹配的过程。安全代码的匹配过程中肯定是不会有不安全的代码段结尾的节点的,又因为无限长的安全代码匹配过程肯定是无限的,如果在trie图上找到一个环,使得环上不出现不安全代码的结尾,那么说明存在这样一个无限循环的安全代码。
因此本题的思路就是在trie图上DFS找环。
代码
// Code by KSkun, 2018/3
#include <cstdio>
#include <queue>
const int MAXN = 30005;
int ch[MAXN][2], fail[MAXN], cnt;
bool val[MAXN];
std::queue<int> que;
inline void insert(char *str) {
int p = 0;
for(int i = 0; str[i]; i++) {
if(!ch[p][str[i] - '0']) ch[p][str[i] - '0'] = ++cnt;
p = ch[p][str[i] - '0'];
}
val[p] = true;
}
inline void calfail() {
for(int i = 0; i <= 1; i++) {
if(ch[0][i]) {
fail[ch[0][i]] = 0;
que.push(ch[0][i]);
}
}
while(!que.empty()) {
int u = que.front(); que.pop();
for(int i = 0; i <= 1; i++) {
if(ch[u][i]) {
fail[ch[u][i]] = ch[fail[u]][i];
val[ch[u][i]] |= val[fail[ch[u][i]]];
que.push(ch[u][i]);
} else {
ch[u][i] = ch[fail[u]][i];
}
}
}
}
bool vis[MAXN], visd[MAXN], success = false;
inline void dfs(int p) {
vis[p] = true;
for(int i = 0; i <= 1; i++) {
if(vis[ch[p][i]]) {
success = true;
return;
}
if(!val[ch[p][i]] && !visd[ch[p][i]]) {
visd[ch[p][i]] = true;
dfs(ch[p][i]);
if(success) return;
}
}
vis[p] = false;
}
int n;
char str[MAXN];
int main() {
scanf("%d", &n);
for(int i = 0; i < n; i++) {
scanf("%s", str);
insert(str);
}
calfail();
dfs(0);
puts(success ? "TAK" : "NIE");
return 0;
}