2938: [Poi2000]病毒

Time Limit:?1 Sec??Memory Limit:?128 MB
Submit:?609??Solved:?318
[Submit][Status][Discuss]

Description

二進(jìn)制病毒審查委員會(huì)最近發(fā)現(xiàn)了如下的規(guī)律：某些確定的二進(jìn)制串是病毒的代碼。如果某段代碼中不存在任何一段病毒代碼，那么我們就稱這段代碼是安全的。現(xiàn)在委員會(huì)已經(jīng)找出了所有的病毒代碼段，試問，是否存在一個(gè)無限長(zhǎng)的安全的二進(jìn)制代碼。 示例： 例如如果{011, 11, 00000}為病毒代碼段，那么一個(gè)可能的無限長(zhǎng)安全代碼就是010101…。如果{01, 11, 000000}為病毒代碼段，那么就不存在一個(gè)無限長(zhǎng)的安全代碼。 任務(wù)： 請(qǐng)寫一個(gè)程序： l?????????讀入病毒代碼； l?????????判斷是否存在一個(gè)無限長(zhǎng)的安全代碼； l?????????將結(jié)果輸出

Input

第一行包括一個(gè)整數(shù)n，表示病毒代碼段的數(shù)目。以下的n行每一行都包括一個(gè)非空的01字符串——就是一個(gè)病毒代碼段。所有病毒代碼段的總長(zhǎng)度不超過30000。

Output

你應(yīng)在在文本文件WIN.OUT的第一行輸出一個(gè)單詞： l?????????TAK——假如存在這樣的代碼； l?????????NIE——如果不存在。

Sample Input

3
01
11
00000

Sample Output

NIE

HINT

Source

Solution

Trie圖的一大經(jīng)典應(yīng)用。

要構(gòu)造一個(gè)無限長(zhǎng)的安全串，顯然是需要找至少一個(gè)安全的子串，然后循環(huán)下去，問題在于是否存在這樣的子串。

建出Trie圖之后，滿足條件的子串必須在Trie圖上不斷匹配，而且不斷失配無法達(dá)到危險(xiǎn)節(jié)點(diǎn)。

這就說明，Trie圖中存在不經(jīng)過危險(xiǎn)節(jié)點(diǎn)的環(huán)！ 然后進(jìn)行拓?fù)渑判蚣纯伞?/p>

Code

#include<iostream> #include<cstdio> #include<cstring> #include<cmath> #include<algorithm> #include<queue> using namespace std; #define MAXN 30010 int N; char s[MAXN]; struct EdgeNode{int next,to;}edge[MAXN<<1]; int head[MAXN],cnt=1,d[MAXN],visit[MAXN]; inline void AddEdge(int u,int v) {cnt++; edge[cnt].next=head[u]; head[u]=cnt; edge[cnt].to=v;} inline void InsertEdge(int u,int v) {AddEdge(u,v); d[v]++; /*printf("%d ---> %d\n",u,v);*/} namespace ACMachine {#define id(s) s-'0'int son[MAXN][2],end[MAXN],sz=1,fail[MAXN];inline void Insert(char str[]){int len=strlen(str+1),now=1;for (int i=1; i<=len; i++)if (son[now][id(str[i])]) now=son[now][id(str[i])];else son[now][id(str[i])]=++sz,now=sz;end[now]=1;}inline void Getfail(){queue<int>q; q.push(1);while (!q.empty()){int now=q.front(); q.pop(); end[now]|=end[fail[now]];for (int i=0; i<=1; i++){int fa=fail[now];while (fa && !son[fa][i]) fa=fail[fa];if (son[now][i]) fail[son[now][i]]=fa? son[fa][i]:1,q.push(son[now][i]);else son[now][i]=fa? son[fa][i]:1;}}} } using namespace ACMachine; inline bool Topo() {queue<int>q;int sum=0;for (int i=1; i<=sz; i++){if (end[i]) sum++; elsefor (int j=0; j<=1; j++)if (!end[son[i][j]]) InsertEdge(i,son[i][j]);}for (int i=1; i<=sz; i++) if (!d[i] && !end[i]) q.push(i);while (!q.empty()){int now=q.front(); q.pop(); sum++;for (int i=head[now]; i; i=edge[i].next)if (!--d[edge[i].to]) q.push(edge[i].to);}return sum==sz; } int main() {scanf("%d",&N);for (int i=1; i<=N; i++) scanf("%s",s+1),Insert(s);Getfail();if (Topo()) puts("NIE"); else puts("TAK");return 0; }

?

轉(zhuǎn)載于:https://www.cnblogs.com/DaD3zZ-Beyonder/p/6139083.html

總結(jié)

以上是生活随笔為你收集整理的【BZOJ-2938】病毒 Trie图 + 拓扑排序的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。