P2444 [POI2000] 病毒

[P2444 POI2000] 病毒 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

问题等价于在字典图中找一个环，这个环要满足环上节点不是所有所给字符串最后一个字符结尾的点。

找环算法：

void dfs(int u) {
	in[u] = 1; // u在当前dfs路径中
	for(auto y: g[u]) {
		if(in[y]) {
			// 与dfs路径中点重合，成环
			fg = 1;
		}
		// 如果之前已经访问过y点，表示经过y点不会有环
		if(vis[y]) continue; 
		vis[y] = 1;
		dfs(y);
	}
    in[u] = 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

本题找环，还需要保证，y点不是所给字符串中最后一个字符结尾的点。

代码：

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;

// #define Multiple_groups_of_examples
// #define int_to_long_long
#define IOS std::cout.tie(0);std::cin.tie(0)->sync_with_stdio(false); // 开IOS，需要保证只使用Cpp io流 *
#define dbgnb(a) std::cout << #a << " = " << a << '\n';
#define dbgtt cout<<" !!!test!!! "<<'\n';
#define rep(i,x,n) for(int i = x; i <= n; i++)

#define all(x) (x).begin(),(x).end()
#define pb push_back
#define vf first
#define vs second

typedef long long LL;
#ifdef int_to_long_long
#define int long long
#endif
typedef pair<int,int> PII;

const int INF = 0x3f3f3f3f;
const int N = 2e5 + 21;

namespace golitter {
namespace ACAM {
// https://www.luogu.com.cn/problem/P5357
// https://zhuanlan.zhihu.com/p/546999184
struct acam {
    static const int M = 300005;
    struct node {
        int fail;
        int ch[28] = {0};
    }tr[M];
    int cnt = 0;
    map<int,int> ref;
    vector<int> g[M];
    int ans[M];
    bitset<M> in, vis, isend;
    void insert(string &s, int id) {
        int u = 0;
        for(auto c: s) {
            int last = c == '_' ? 26 : c - 'a';
            if(!tr[u].ch[last]) {
                tr[u].ch[last] = ++cnt;
            }
            u = tr[u].ch[last];
        }
        isend[u] = 1;
        ref[id] = u;
    }
    void build() {
        queue<int> que;
        for(int i = 0; i < 27; ++i) {
            if(tr[0].ch[i]) que.push(tr[0].ch[i]);
        }
        while(que.size()) {
            int u = que.front(); que.pop();
            for(int i = 0; i < 27; ++i) {
                if(tr[u].ch[i]) {
                    tr[tr[u].ch[i]].fail = tr[tr[u].fail].ch[i];
                    que.push(tr[u].ch[i]);
                    if(isend[tr[tr[u].ch[i]].fail]) isend[tr[u].ch[i]] = 1;
                } else tr[u].ch[i] = tr[tr[u].fail].ch[i];
            }
        }
        for(int i = 1; i <= cnt; ++i) g[tr[i].fail].push_back(i);
    }
    void query(string &S) {
        int u = 0;
        for(auto c: S) {
            int last = c == '_' ? 26 : c - 'a';
            u = tr[u].ch[last];
            ans[u]++;
        }
    }
    bool fg = 0;
    bool check() {
        dfs(0);
        return fg;
    }
    void dfs(int u) {
        in[u] = 1;
        for(int i = 0; i <= 1; ++i) {
            if(in[tr[u].ch[i]]) {
                fg = 1;
                return ;
            }
            if(vis[tr[u].ch[i]] || isend[tr[u].ch[i]]) continue;
            vis[tr[u].ch[i]] = 1;
            dfs(tr[u].ch[i]);
        }
        in[u] = 0;
    }
    void clear() {
        for(int i = 0; i < M; ++i) {
            tr[i] = {};
            g[i].clear();
            ans[i] = 0;
        }
        ref.clear();
        cnt = 0;
    }
}trie;

}}
using golitter::ACAM::trie;
void inpfile();
void solve() {
    int n; cin>>n;
    for(int i = 0; i< n; ++i) {
        string s; cin>>s;
        for(auto&t: s) {
            if(t == '1') t = 'b';
            else t = 'a';
        }
        trie.insert(s, i);
    }
    trie.build();
    puts(trie.check() ? "TAK" : "NIE");
}
#ifdef int_to_long_long
signed main()
#else
int main()
#endif

{
    #ifdef Multiple_groups_of_examples
    int T; cin>>T;
    while(T--)
    #endif
    solve();
    return 0;
}
void inpfile() {
    #define mytest
    #ifdef mytest
    freopen("ANSWER.txt", "w",stdout);
    #endif
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155