526互联

12.19闲话

发布时间 2023-12-19 20:06:59作者: Vsinger_洛天依
  • 本文\(latex\)纯属滥用

我们班上数学课，数学老师：用这个\(15\)比上\(\text {HE}\)，\(\text {HE}\)等于几？等于\(7\)对吧

世界上最遥远的距离，不是生与死，而是\(2\)机房没洛谷\(1\)机房有,\(4\)机房甚至黑名单

  • \(update\)

    今天那屋在讲Tarjan我就混进去了，看了会AC自动机的讲解博客，赢吗了

今天在写\(\text{Trie}\)

\(Phone\ List\)

\(\text{Trie}\)板子题

但是因为一些弱智错误调了好久我恼了

$My\ Code$

\({namespace}\) 里写的\(Tire\)是为了好区分不要D我呜呜

#include<bits/stdc++.h>
#define int long long
namespace IO{
    inline void close(){
        std::ios::sync_with_stdio(0);
        std::cin.tie(0);
        std::cout.tie(0);
    }
    inline void Fire(){
        freopen("data.in","r",stdin);
        freopen("data.out","w",stdout);
    }
    inline int read(){
        int s=0,w=1;char ch=getchar();
        while(!isdigit(ch)){ if(ch == '-') w=-1;ch=getchar();}
        while(isdigit(ch)){ s=(s<<3)+(s<<1)+(ch^48);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;
const int N=100005;
namespace Tire{
    
    class Trie{
    public:
        int NEX[20];
        bool END;
    }Tr[N];
    
    int cnt=1;
    inline void clear(){
        cnt=1;
        memset(Tr,0,sizeof(Tr));
    }
    inline bool ADD(char *S){
        int p(1),len=strlen(S+1);
        int q1(0),q2(0);
        for(int j(1);j<=len;j++){
            if(!Tr[p].NEX[S[j]-'0']) q1=1,Tr[p].NEX[S[j]-'0']=++cnt;
            p=Tr[p].NEX[S[j]-'0'];
			q2|=Tr[p].END;
        }
        Tr[p].END=1;
        return (!q1)||(q2);
    }
    inline bool FIND(char *S){
        int p=0,len=strlen(S+1);
        bool q1,q2;
        for(int j=1;j<=len;++j){
            if(!Tr[p].NEX[S[j]-'0'+1])return 0;
            p=Tr[p].NEX[S[j]-'0'+1];
        }
        return Tr[p].END;
    }
}
signed main(){
    Fire();
    int n=read();
    while(n--){
        int m=read();int q=0;
        char S[10001];
        for(int i=1;i<=m;i++){
            scanf("%s",S+1);
            q|=Tire::ADD(S);
        }
        puts(q?"NO":"YES");
        Tire::clear();
    }
}

\(The\ XOR\ Largest\ Pair\)

\(01\!\!-\!\text{Trie}\)板子题

大概就是把数的二进制插入\(\text{Trie}\)维护然后讨论该数的位数是\(0\)还是\(1\)，并尽量向与之相反的数求异或值即可

$My\ Code$ 
#include<bits/stdc++.h>
#define int long long
const int maxn=0x66CCFF;
class IO{
public:
    inline void close(){
        std::ios::sync_with_stdio(0);
        std::cin.tie(0);
        std::cout.tie(0);
    }
    inline void Fire(){
        freopen("data.in","r",stdin);
        freopen("data.out","w",stdout);
    }
    inline int read(){
        int s=0,w=1;char ch=getchar();
        while(!isdigit(ch)){if(ch=='-') w=-1;ch=getchar();}
        while(isdigit(ch)){s=(s<<3)+(s<<1)+(ch^48);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(' ');
    }
}IO;
using namespace std;
int cnt=0,rt,n;
class Trie{
public:
    class Tire{
    public:
        int NEX[2];
    }s[maxn];
    inline void insert(int u,int t,int x){
        if(t<0) return;
        int f((x>>t)&1);
        if(!s[u].NEX[f]) s[u].NEX[f]=++cnt;
        insert(s[u].NEX[f],t-1,x);
    }
    inline int ask(int u,int t,int x){
        if(t<0)return 0;
        int f((x>>t)&1);
        if(s[u].NEX[!f])return ask(s[u].NEX[!f],t-1, x)+(1<<t);   
        return ask(s[u].NEX[f],t-1,x);
    }
}Tr;
signed main(){
    IO.Fire();
    n=(IO.read());
    int ans(0);
    rt=++cnt;
    for(int i=0;i<n;i++){
        int x=IO.read();
        Tr.insert(rt,30,x);
        if(i) ans=max(ans,Tr.ask(rt,30,x));
    }
	IO.write(ans);
}

\(The\ XOR-longest\ Path\)

\(01\!\!-\!\text{Trie}\)板子题

首先要知道\(a\oplus b\oplus b=a\)

根据这个就可以通过本题

思路上大概就是先维护所有节点到根节点的异或和然后将这些异或和进行一个和上一题相同的操作即可求解本题

打的好像有点问题因为貌似可以不用树剖维护但是我忘了别的怎么打了，不过其实也没写多少毕竟只查询到根节点的异或和不用打查询子树和修改

$My\ Code$ 
#include<bits/stdc++.h>
#define int long long
const int maxn=0x66CCFF,MAXM=0x66CCFF;
namespace IO{
    inline void close(){
        std::ios::sync_with_stdio(0);
        std::cin.tie(0);
        std::cout.tie(0);
    }
    inline void Fire(){
        freopen("data.in","r",stdin);
        freopen("data.out","w",stdout);
    }
    inline int read(){
        int s=0,w=1;char ch=getchar();
        while(!isdigit(ch)){if(ch=='-') w=-1;ch=getchar();}
        while(isdigit(ch)){s=(s<<3)+(s<<1)+(ch^48);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;
int head[MAXM],NEXT[MAXM],edge[MAXM],TO[MAXM],cnt,tot,a[MAXM];
struct node{
    int fa,dep,siz,son,top;
    int dfn,rnk;
}T[MAXM];
namespace Grape{
    inline void add(int u,int v,int w){
        NEXT[++tot]=head[u];
        edge[tot]=w;
        TO[tot]=v;
        head[u]=tot;
    }
}
namespace ST{
    #define mid (l+r)/2
    #define lC q<<1
    #define rC q<<1|1
    struct St{
        long long l,r,siz;
        long long lazy,dat;
    }t[0x66ccff];
    void build(int q,int l,int r){
        t[q].l=l;
        t[q].r=r;
        t[q].siz=r-l+1;
        if(l==r){
            t[q].dat=a[T[l].rnk];
            return;
        }
        build(lC,l,mid);
        build(rC,mid+1,r);
        t[q].dat=t[lC].dat^t[rC].dat;
    }
    long long asksum(int q,int l,int r){
        if(t[q].l>r || t[q].r<l) 
            return 0;
        if(t[q].l>=l && t[q].r<=r) 
            return t[q].dat;
        return asksum(lC,l,r)^asksum(rC,l,r); 
    }
}
namespace killTree{
    inline void Dfs1(int q){
        T[q].son=-1;
        T[q].siz=1;
        for(int j=head[q];j;j=NEXT[j]){
            if(T[TO[j]].dep) continue;
            a[TO[j]]=edge[j];
            T[TO[j]].dep=T[q].dep+1;
            T[TO[j]].fa=q;
            Dfs1(TO[j]);
            T[q].siz+=T[TO[j]].siz;
            if((T[q].son==-1) || (T[TO[j]].siz>T[T[q].son].siz)) T[q].son=TO[j];
        }
    }
    inline void Dfs2(int q,int v){
        T[q].top=v;
        T[q].dfn=++cnt;
        T[cnt].rnk=q;
        if(T[q].son==-1)
            return;
        Dfs2(T[q].son,v);
        for(int j=head[q];j;j=NEXT[j]){
            if((TO[j]!=T[q].fa)&&(TO[j]!=T[q].son))
                Dfs2(TO[j],TO[j]);
        }
    }
    inline int TreeAsk(int x,int y){
        int ans=0;
        while(T[x].top!=T[y].top){
            if(T[T[x].top].dep<T[T[y].top].dep) std::swap(x,y);
            ans=ans^ST::asksum(1,T[T[x].top].dfn,T[x].dfn);
            x=T[T[x].top].fa;
        }
        if(T[x].dep>T[y].dep) std::swap(x,y);
        return ans^ST::asksum(1,T[x].dfn,T[y].dfn);
    }
}
using namespace ST;
using namespace killTree;
using namespace std;
int qwq,n,sum[maxn];
class Trie{
public:
    class Tire{
    public:
        int NEX[2];
    }s[maxn];
    inline void insert(int u,int t,int x){
        if(t<0) return;
        int f((x>>t)&1);
        if(!s[u].NEX[f]) s[u].NEX[f]=++qwq;
        insert(s[u].NEX[f],t-1,x);
    }
    inline int ask(int u,int t,int x){
        if(t<0)return 0;
        int f((x>>t)&1);
        if(s[u].NEX[!f])return ask(s[u].NEX[!f],t-1, x)+(1<<t);   
        return ask(s[u].NEX[f],t-1,x);
    }
}Tr;
signed main(){
    Fire();
    n=(read());int ans=0;
    for(int i=0;i<n-1;i++){
        int x=read(),y=read(),z=read();
        Grape::add(x,y,z);
        Grape::add(y,x,z);
    }
    T[1].dep=1;
    Dfs1(1);Dfs2(1,1);
    build(1,1,n);
    for(int i=1;i<=n;i++){
        sum[i]=TreeAsk(1,i);
    }
    int rt=++qwq;
    for(int i=1;i<=n;i++){
        int x=sum[i];
        Tr.insert(rt,30,x);
        if(i) ans=max(ans,Tr.ask(rt,30,x));
    }
	write(ans);
}

\(Nikitosh\) 和异或

数据好像有点水???

这个代码过了但是其实可以随便\(\text{Hack}\)掉

#include <bits/stdc++.h>
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;}while(cnt>0)putchar(F[--cnt]);}
}
using namespace IO;
int n(read()),ans;
int main(){
    while(n--) ans|=read();
    write(ans<<1);
}

正解先咕咕咕了

普及组\(OJ\)上的image
终于写完了,终于能看看\(AC\)自动机是什么东西了虽然我感觉我\(KMP\)学的不太好但是至少先看看是啥

听说只要学了AC自动机就可以从入门级选手进阶到普及组选手

在洛谷上看见的存一下

//AC自动机讲解博客
//https://www.cnblogs.com/cjyyb/p/7196308.html
//https://www.cnblogs.com/hyfhaha/p/10802604.html
//https://blog.csdn.net/weixin_45740176/article/details/104865655
//https://www.cnblogs.com/yifusuyi/p/10713937.html
//https://blog.csdn.net/no1_terminator/article/details/77725530（VIP）
//AC自动机优化:拓扑排序优化建图,指针,unordered_map优化输入重复串