2938: [Poi2000]病毒
Time Limit: 1 Sec Memory Limit: 128 MB
Submit: 345 Solved: 176
[Submit][Status][Discuss]
Description
二進制病毒審查委員會最近發現了如下的規律：某些確定的二進制串是病毒的代碼。如果某段代碼中不存在任何一段病毒代碼，那麼我們就稱這段代碼是安全的。現在委員會已經找出了所有的病毒代碼段，試問，是否存在一個無限長的安全的二進制代碼。
示例：
例如如果{011, 11, 00000}為病毒代碼段，那麼一個可能的無限長安全代碼就是010101…。如果{01, 11, 000000}為病毒代碼段，那麼就不存在一個無限長的安全代碼。
任務：
請寫一個程序：
l 讀入病毒代碼；
l 判斷是否存在一個無限長的安全代碼；
l 將結果輸出
Input
第一行包括一個整數n，表示病毒代碼段的數目。以下的n行每一行都包括一個非空的01字符串——就是一個病毒代碼段。所有病毒代碼段的總長度不超過30000。
Output
你應在在文本文件WIN.OUT的第一行輸出一個單詞：
l TAK——假如存在這樣的代碼；
l NIE——如果不存在。
Sample Input
3
01
11
00000
Sample Output
NIE
HINT
Source
這道題的思路很好
首先我們跑一次AC自動機，Trie樹和失配邊就構成了一個有向圖。那麼，能找到一個無限長的安全代碼，當且僅當在非單詞節點中存在環，用拓撲排序判斷即可。
#include
#include
#include
#include
#include
#include
#include
#define F(i,j,n) for(int i=j;i<=n;i++)
#define D(i,j,n) for(int i=j;i>=n;i--)
#define ll long long
#define pa pair
#define maxn 30100
#define inf 1000000000
using namespace std;
struct edge_type
{
int next,to;
}e[maxn*2];
int go[maxn],in[maxn],head[maxn],t[maxn][2];
int n,tot=1,cnt=0;
bool v[maxn];
char s[maxn];
inline void add_edge(int x,int y)
{
e[++cnt]=(edge_type){head[x],y};
head[x]=cnt;
}
inline void insert()
{
scanf("%s",s);
int len=strlen(s),now=1;
F(i,0,len-1)
{
int x=s[i]-'0';
if (!t[now][x]) t[now][x]=++tot;
now=t[now][x];
}
v[now]=true;
}
inline void bfs()
{
queue q;
q.push(1);
while (!q.empty())
{
int x=q.front(),y,j;q.pop();v[x]|=v[go[x]];
F(i,0,1)
{
j=go[x];
while (j&&!t[j][i]) j=go[j];
if (t[x][i])
{
go[y=t[x][i]]=j?t[j][i]:1;
q.push(y);
}
else t[x][i]=j?t[j][i]:1;
}
}
}
inline bool topsort()
{
queue q;
int sum=0;
F(i,1,tot)
{
if (v[i]) sum++;
else F(j,0,1) if (!v[t[i][j]])
{
add_edge(i,t[i][j]);
in[t[i][j]]++;
}
}
F(i,1,tot) if (!v[i]&&!in[i]) q.push(i);
while (!q.empty())
{
int x=q.front();q.pop();sum++;
for(int i=head[x];i;i=e[i].next)
{
int y=e[i].to;
in[y]--;
if (!in[y]) q.push(y);
}
}
return sum==tot;
}
int main()
{
scanf("%d",&n);
F(i,1,n) insert();
bfs();
printf("%s\n",topsort()?"NIE":"TAK");
return 0;
}
