Go语言视频零基础入门到精通

admin

题目大意：

有N个确定的二进制串是病毒的代码。当某段代码中不存在任何一段病毒代码，那么我们就称这段代码是安全的。现在委员会已经找出了所有的病毒代码段，试问，是否存在一个无限长的安全的二进制代码。

n≤2000
所有病毒代码段的总长度不超过30000

题解：

将所有的病毒代码构建一个AC自动机，
如果存在一个可行解，必定它在trie树中，从根节点开始走，不会碰到所有病毒的末尾节点（即不可行的点）。
而一个点，显然它的fail边连的点不可行，则这个点也必定是不可行的。
那么我们可以从trie的根节点进行dfs，
注意不走危险节点，不走历史访问过而已经不在栈中的节点
记录每个节点在当前 dfs 走的路径上有没有被选中，注意要保证路径上的点不存在不可行节点
当路径中出现环，则有解

代码：
#include<bits/stdc++.h>
#define N 233333

using namespace std;  

int n,num,next[N][2],fail[N],end[N],vis[N],rp[N];  
char s[N];

void insert(char *s)
{
     int len=strlen(s);
     int u=0;
     for (int i=0; i<len; i++)
         {
              int v=s[i]-'0';
              if (!next[u][v]) next[u][v]=++num;
              u=next[u][v];
         }
     end[u]=1;
}
void build()  
{  
     queue <int> Q;
     for (int i=0; i<=1; i++)  
          if (next[0][i]) Q.push(next[0][i]);  
     while (!Q.empty())  
           {  
               int u=Q.front();
               Q.pop();  
               for (int i=0; i<=1; i++)  
                   if (!next[u][i])
                       next[u][i]=next[fail[u]][i];   
                   else {
                            end[next[u][i]]|=end[next[fail[u]][i]];  
                            fail[next[u][i]]=next[fail[u]][i];  
                            Q.push(next[u][i]);  
                        }
           }      
}  

bool dfs(int dep)  
{  
    vis[dep]=rp[dep]=1;  
    for(int i=0; i<=1; i++)  
        {
            if (rp[next[dep][i]]) return 1;
            if (!end[next[dep][i && !vis[next[dep][i && dfs(next[dep][i])) return 1;  
        }
    rp[dep]=0;  
    return 0;  
}  

int main()  
{  
    scanf("%d",&n);  
    for (int i=1; i<=n; i++)
        {  
             scanf("%s",s);
             insert(s);  
        }  
    build();  
    if (dfs(0)) printf("TAK");
           else printf("NIE");
    return 0;  
}