推歌
一梦千宵
漫步在 没来过 的街巷
灯火下 看人潮 多熙攘
原来是 过节了 要换装
楼阁也挂满彩帐
买一串 糖葫芦 先尝尝
再挑个 俏铃铛 戴手上
不远处 说书人 开了嗓
约上谁 捧捧场
莺歌蝶舞韶光长
红炉煮茗松花香
旧时华彩今又唱
一夜花灯漾
明宵梦长
借漫天的 烟火斑斓
连同霄灯 许下期盼
只要身边 有你陪伴
往后时光 绝不遗憾
就算世界 太多美好 只一眨眼 就变幻
可回忆 始终璀璨
这一侧 台上谁 起花腔
那一边 又几人 捏面糖
你赶忙 招呼我 少张望
别傻傻跟丢地方
猜是那 仙人们 也一样
会牵手 趁热闹 逛市坊
听海风 徐徐吹 心摇晃
做宵灯 把它放
莺歌蝶舞韶光长
红炉煮茗松花香
旧时华彩今又唱
一夜花灯漾
你我之间 无数牵绊
像这首歌 越唱越暖
哪怕有天 终将分散
相同旅程 也未孤单
就让故事 随着旋律 轻轻地哼 飘天畔
永远都 不会断
一盏一盏 一闪一闪
从手中升起飞去 彼岸
汇成星路一段
牵引迷途的人 启帆
心中的愿 不会暗淡
借漫天的 烟火斑斓
连同霄灯 许下期盼
只要身边 有你陪伴
往后时光 绝不遗憾
就算世界 太多美好 只一眨眼 就变幻
可回忆 始终璀璨
那些一时擦肩而过 错开的你我
也许仍沿相对方向 朝未来穿梭
终有天在某处相遇 最熟悉轮廓
依然是 如此闪烁
今天大概给高一大佬讲了一下题和知识点
首先是链式前向星的相关知识
大佬不止不会链式前向星，甚至不会衔接矩阵讲起来好麻烦
这让我想起了一位树剖边权转点权解法是对于每个点建立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");
}
