D. 病毒
题目描述
原题来自: POI 2000
二进制病毒审查委员会最近发现了如下的规律: 某些确定的二进制串是病毒的代码. 如果某段代码中不存在任何一段病毒代码, 那么我们就称这段代码是安全的. 现在委员会已经找出了所有的病毒代码段, 试问, 是否存在一个无限长的安全的二进制代码.
示例: 例如如果 {011,11,00000}\{011, 11, 00000\}{011,11,00000} 为病毒代码段, 那么一个可能的无限长安全代码就是 010101?010101\cdots 010101?. 如果 {01,11,000000}\{01, 11, 000000\}{01,11,000000} 为病毒代码段, 那么就不存在一个无限长的安全代码.
请写一个程序, 读入病毒代码, 判断是否存在一个无限长的安全代码, 将结果输出.
输入格式
第一行包括一个整数 nnn, 表示病毒代码段的数目;
以下的 nnn 行, 每一行都包括一个非空的 010101 字符串 -- 就是一个病毒代码段.
输出格式
第一行输出一个单词. 假如存在这样的代码, 则输出 TAK, 否则输出 NIE.
样例
样例输入
3 01 11 00000
样例输出
NIE
数据范围与提示
对于全部数据, 所有病毒代码段的总长度不超过 3*1044??.
对 trie 图的理解还是没有那么透彻啊 (以前就只是知道他比 trie 树快...).
安全的串可以在 AC 自动机上在不匹配单词终点的情况下无限匹配 (颓题解之前就想到这里), 在 trie 图上, 如果能无线匹配那么意味着 trie 图上有环, dfs 判环即可.
注意还有两个剪枝 (zz 的我刚开始居然用队列模拟深搜...):
1. 单词终点不能走, 那么 fail 指向单词终点的点也不能走. 设一个单词终点为 x,y->fail=x, 那么 root~x 为 root~y 的后缀, y 也不能走. 将 x 设为危险节点, fail 指向 x 的 y 也是危险节点, 同理所有 fail 指向危险节点的点都是危险节点 (之前一直不能理解这玩意儿有啥用),dfs 时将危险节点剪掉.
2. 由于一个节点可能会搜多次, 所以将搜索过但是 return 0 的节点标记, 剪掉.
- #include<iostream>
- #include<cstdio>
- using namespace std;
- struct trie
- {
- int count;
- bool pd,danger,vis;
- trie *next[2],*fail;
- trie()
- {
- count=0;pd=0;danger=0;vis=0;
- next[1]=next[2]=fail=NULL;
- }
- }*q[100000],*root=new trie();
- int head,tail;
- void insert(char s[],trie *root)
- {
- trie *p=root;
- int i=0,index;
- while(s[i])
- {
- index=s[i]-'0';
- if(p->next[index]==NULL)p->next[index]=new trie();
- p=p->next[index];
- i++;
- }
- p->count++;
- p->danger=1;
- }
- void build_ac(trie *root)
- {
- q[++tail]=root;
- while(head!=tail)
- {
- trie *p=q[++head];
- trie *temp=NULL;
- for(int i=0;i<=1;i++)
- if(p->next[i])
- {
- if(p==root) p->next[i]->fail=p;
- else
- {
- p->next[i]->fail=p->fail->next[i];
- if(p->fail->next[i]->danger)p->next[i]->danger=1;
- }
- q[++tail]=p->next[i];
- }
- else
- if(p==root) p->next[i]=root;
- else p->next[i]=p->fail->next[i];
- }
- }
- bool dfs(trie *p)
- {
- p->pd=1;
- for(int i=0;i<=1;i++)
- {
- if(p->next[i]->pd)return 1;
- if(p->next[i]->danger || p->next[i]->vis)continue;
- if(dfs(p->next[i]))return 1;
- p->next[i]->vis=1;
- }
- p->pd=0;
- return 0;
- }
- int n;
- char keyword[30010];
- char str[100000];
- signed main()
- {
- //freopen("in.txt","r",stdin);
- cin>>n;
- for(int i=1;i<=n;i++)
- {
- scanf("%s",keyword);
- insert(keyword,root);
- }
- build_ac(root);
- if(dfs(root))cout<<"TAK";
- else cout<<"NIE";
- }
- View Code
[BZOJ2938] 病毒
来源: http://www.bubuko.com/infodetail-3098009.html