今天大概给高一大佬讲了一下题和知识点
首先是链式前向星的相关知识
大佬不止不会链式前向星，甚至不会衔接矩阵讲起来好麻烦
这让我想起了一位树剖边权转点权解法是对于每个点建立3条边的故人
TA懂了链式前向星顺手教了TA传说中的STL容器
然后自己学了学pbds的那几个容器，pbds强强强但是我感觉不如手写Hash和平衡树
其次是给大佬跳题让他意识到getchar会读入'\n'和' '非常有成就感
不过很可惜作为废物的我在学完AC自动机之后我仍然只会打一道板子题，OJ上的第二道我便没看出来
我估计是AC自动机掌握的不够好，那么就又去找了几篇看起来不错的博客
画了几张图研究了一下
稍微搞懂一些感觉好多了
然后就是写了道AC自动机（就是OJ上第二道题QAQ）
可以rand骗分
多模式串明显AC自动机，我们可以发现正常的AC自动机是去文本串里匹配模式串但是本题明显不是这样的，而本题却希望在文本串里不要出现模式串
想要找到一个无限长的01串可以明显得出需要在AC自动机形成的字典图里面找环，这个环不包含任何一个字符串的末尾同时需要能被根节点访问到
找环直接DFS就行
$My\ Code$
#include<bits/stdc++.h>
using namespace std;
namespace IO{
inline void close(){std::ios::sync_with_stdio(false);std::cin.tie(0);std::cout.tie(0);}
inline void Fire(){freopen(".in","r",stdin);freopen(".out","w",stdout);}
inline int read(){int s = 0,w = 1;char ch = getchar();while(ch<'0'||ch>'9'){ if(ch == '-') w = -1;ch = getchar();}while(ch>='0'&&ch<='9'){ s = s*10+ch-'0';ch = getchar();}return s*w;}
inline void write(int x){char F[200];int tmp=x>0?x:-x,cnt=0;;if(x<0)putchar('-') ;while(tmp>0){F[cnt++]=tmp%10+'0';tmp/=10;}if(cnt==0)putchar('0');while(cnt>0)putchar(F[--cnt]);putchar(' ');}
}
using namespace IO;
class AC{
public:
class Trie{
public:
int fail,vis[2],end;
}Tr[1000000];
int cnt=1;
inline void ins(string s){
int l=s.length(),q=1;
for(int i=0;i<l;++i){
if(!Tr[q].vis[s[i]-'0'])
Tr[q].vis[s[i]-'0']=++cnt;
q=Tr[q].vis[s[i]-'0'];
}
Tr[q].end=1;
}
inline void Get(){
queue<int>Q;
Q.push(1);
Tr[0].vis[0]=Tr[0].vis[1]=1;
while(!Q.empty()){
int u=Q.front();
Q.pop();
for(int i=0;i<2;++i){
if(Tr[u].vis[i]){
Q.push(Tr[u].vis[i]);
int t=Tr[u].fail;
while(t && !Tr[t].vis[i])
t=Tr[t].fail;
Tr[Tr[u].vis[i]].fail=Tr[t].vis[i];
Tr[Tr[u].vis[i]].end|=Tr[Tr[t].vis[i]].end;
}
else
Tr[u].vis[i]=Tr[Tr[u].fail].vis[i];
}
}
}
// inline int Ask(string s){
// int l=s.length(),q=0,ans=0;
// for(int i=0;i<l;++i){
// q=Tr[q].vis[s[i]-'a'];
// for(int t=q;t&&Tr[t].end!=-1;t=Tr[t].fail){
// ans+=Tr[t].end;
// Tr[t].end=-1;
// }
// }
// return ans;
// }
}AC;
bool vis[1000000],inss[1000000];
bool dfs(int x){
inss[x]=vis[x]=1;
int y;
for(int i=0;i<2;i++){
y=AC.Tr[x].vis[i];
if(inss[y]||(!vis[y]&&!AC.Tr[y].end&&dfs(y)))
return 1;
}
inss[x]=0;
return 0;
}
signed main(){
// freopen("1.in","r",stdin);
// freopen("1.out","w",stdout);
string s;
int m=read();
for(int i=1;i<=m;++i){
cin>>s;
AC.ins(s);
}
AC.Get();
puts(dfs(1)?"TAK":"NIE");
}
