2024.7.16
### 2024.7.16 【I never lose.I either win or learn.】
### Tuesday 六月十一
---
## 0/1Trie学习笔记
使用trie维护异或极值可以使用0/1Trie，
这是一种以{0,1}为字符集的Trie树，
他支持修改和全局加一
使用异或操作时，我们其实并不需要知道每一位上的具体值，只需要知道每一位上1的个数即可
（这句非常非常重要
考虑维护节点，每次插入考虑新添加到树的位
但是需要注意，每次插入要插到最深，
这样才能保证每次异或时位是冲齐的
> [P4551 最长异或路径](https://www.luogu.com.cn/problem/P4551)
```cpp
//2024.7.16
//by white_ice
//P4551 最长异或路径
#include
using namespace std;
#define itn int
constexpr int oo = 2000006;
struct nod{itn v,w,nxt;}st[oo];
itn head[oo];
itn cnt = -1;
void add(int u,int v,int w){
st[++cnt].nxt=head[u];
st[cnt].v=v;
st[cnt].w=w;
head[u]=cnt;
}
int sum[oo];
void dfs(int x,int fa){
for(int i=head[x];~i;i=st[i].nxt){
int v=st[i].v;
int w=st[i].w;
if(v!=fa){
sum[v]=sum[x]^w;
dfs(v,x);
}
}
}
struct trie{int ch[2];}t[oo];
int tot;
void build(int val,int x){
for(int i=(1<<30);i;i>>=1){
bool c=val&i;
if(!t[x].ch[c]){
t[x].ch[c]=++tot;
}
x=t[x].ch[c];
}
}
int query(int val,int x){
int ans=0;
for(int i=(1<<30);i;i>>=1){
bool c=val&i;
if(t[x].ch[!c]){
ans+=i;
x=t[x].ch[!c];
}
else x=t[x].ch[c];
}
return ans;
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
memset(head,-1,sizeof(head));
int n;
cin >> n;
for(int i=1;i> u >> v >> w;
add(u,v,w);
add(v,u,w);
}
dfs(1,-1);
for(int i=1;i<=n;++i)
build(sum[i],0);
int ans=0;
for(int i=1;i<=n;++i)
ans=max(ans,query(sum[i],0));
cout << ans;
return 0;
}
```
学习了一下AC自动机和SA
```cpp
//2024.7.16
//by white_ice
//P5357 【模板】AC 自动机
#include
using namespace std;
#define itn int
constexpr int oo = 2000006;
constexpr int op = 200005;
char st[oo],sp[oo];
int n,cnt,is[200051];
itn in[oo];
itn ton[oo];
struct nod{int vis[26],fail,flag,ans;}trie[oo];
void insert(char* s,int num){
int u=1,len=strlen(s);
for(int i=0;i q;
for(int i=0;i<26;i++)
trie[0].vis[i]=1;
q.push(1);
while(!q.empty()){
int now=q.front();
q.pop();
for(int i=0;i<26;i++){
int v=trie[now].vis[i];
if(!v){
trie[now].vis[i]=trie[trie[now].fail].vis[i];
continue;
}
trie[v].fail=trie[trie[now].fail].vis[i];
in[trie[v].fail]++;
q.push(v);
}
}
}
void topu(){
queue q;
for(int i=1;i<=cnt;i++)
if(in[i]==0)
q.push(i);
while(!q.empty()){
int u=q.front();
q.pop();
is[trie[u].flag]=trie[u].ans;
int v=trie[u].fail;
in[v]--;
trie[v].ans+=trie[u].ans;
if(in[v]==0)
q.push(v);
}
}
void query(char* s){
int now=1;
itn len=strlen(s);
for(int i=0;i> n;
cnt=1;
for(int i=1;i<=n;i++){
cin >> st;
insert(st,i);
}
getfail();
cin >> sp;
query(sp);
topu();
for(int i=1;i<=n;i++)
cout << is[ton[i]] << '\n';
return 0;
}
```