18.10.29 躲不开的病毒（AC自动机+dfs）

描述

有若干种病毒，每种病毒的特征代码都是一个01串。

每个程序也都是一个01串。

问是否存在不被病毒感染（不包含任何病毒的特征代码）的无限长的程序。

输入第一行是整数n，表示有n个病毒
接下来n行，每行是一个由 0,1构成的字符串，表示一个病毒特征代码
所有的病毒的特征代码总长度不超过30000输出如果存在无限长的没有被病毒感染的程序，输出 "TAK"，否则输出"NIE"

样例输入

样例1:
2
10
11
样例2:
2
1
0

样例输出

样例1:
TAK
样例2:
NIE

来源

test cases by Xu Yewen

  1 #include <iostream>
  2 #include <string.h>
  3 #include <algorithm>
  4 #include <stack>
  5 #include <string>
  6 #include <math.h>
  7 #include <queue>
  8 #include <stdio.h>
  9 #include <string.h>
 10 #include <vector>
 11 #include <fstream>
 12 #include <set>
 13 
 14 using namespace std;
 15 const int maxn = 30005;
 16 int n, nodecou;
 17 char virus[maxn];
 18 bool instack[maxn];
 19 
 20 struct node {
 21     int next[2];
 22     int prev;
 23     bool isdanger;
 24     node() {
 25         memset(next, 0, sizeof(next));
 26         prev = -1;
 27         isdanger = false;
 28     }
 29 }tree[maxn];
 30 
 31 void insert() {
 32     int now = 1, l = strlen(virus);
 33     for (int i = 0; i < l; i++) {
 34         int idx = virus[i] - '0';
 35         if (tree[now].next[idx] == 0) {
 36             nodecou++;
 37             tree[now].next[idx] = nodecou;
 38         }
 39         now = tree[now].next[idx];
 40         if (i == l - 1)
 41             tree[now].isdanger = true;
 42     }
 43 }
 44 
 45 void build() {
 46     tree[0].next[0] = 1, tree[0].next[1] = 1;
 47     tree[1].prev = 0;
 48     queue<int>q;
 49     q.push(1);
 50     while (!q.empty()) {
 51         int now = q.front(); q.pop();
 52         for (int i = 0; i < 2; i++) {
 53             int child = tree[now].next[i];
 54             int prev = tree[now].prev;
 55             if (child) {
 56                 while (tree[prev].next[i] == NULL)
 57                     prev = tree[prev].prev;
 58                 tree[child].prev = tree[prev].next[i];
 59                 if (tree[tree[child].prev].isdanger)
 60                     tree[child].isdanger = true;
 61                 q.push(child);
 62             }
 63             else {
 64                 while (!tree[prev].next[i])
 65                     prev = tree[prev].prev;
 66                 tree[now].next[i] = tree[prev].next[i];
 67                 if (tree[child].isdanger)
 68                     tree[now].next[i] = 0;
 69             }
 70         }
 71     }
 72 }
 73 
 74 bool dfs(int rt) {
 75     if (instack[rt])return true;
 76     instack[rt] = true;
 77     bool ans = false;
 78     for (int i = 0; i < 2; i++)
 79         if (tree[rt].next[i] && !tree[tree[rt].next[i]].isdanger)
 80         {
 81             ans = ans || dfs(tree[rt].next[i]);
 82             if (ans)return true;
 83         }
 84     instack[rt] = false;
 85     return false;
 86 }
 87 
 88 void init() {
 89     scanf("%d", &n);
 90     nodecou = 1;
 91     while (n--) {
 92         scanf("%s", virus);
 93         insert();
 94     }
 95     build();
 96     if (dfs(1))
 97         printf("TAK
");
 98     else
 99         printf("NIE
");
100 }
101 
102 int main()
103 {
104     init();
105     return 0;
106 }

View Code

看见大家跑的时间都很少就放心地使用了递归

不用指针就舒爽多了

再也不用担心RE了，快乐

PPT上写的是栈中保存的元素，大概可以用栈来做？反正我是懒得写栈做法

=======================update===========================

惊了刚刚看群里发现这题居然是有来源的

luogu 2444

当时搜过并没有找到任何题源所以就没有加上，现在补上

注定失败的战争，也要拼尽全力去打赢它；就算输，也要输得足够漂亮。