并查集

#include<iostream>
#include<algorithm>
#define x first
#define y second
using namespace std;
const int N=10010;
typedef pair<int,int> PII;
PII a[N];
int fa[N];
inline bool cmp(PII a,PII b){
    return a.x>b.x;
}
inline int find(int x){
    if(fa[x]!=x)
        fa[x]=find(fa[x]);
    return fa[x];
}
int main(){
    int n;
    while(~scanf("%d",&n)){
        int ans=0,maxy=0;
        for(int i=1;i<=n;i++){
            scanf("%d%d",&a[i].x,&a[i].y);
            maxy=max(maxy,a[i].y);
        }
        sort(a+1,a+1+n,cmp);
        for(int i=0;i<=maxy;i++)
            fa[i]=i;
        for(int i=1;i<=n;i++){
            int x=a[i].x,y=a[i].y;
            int p=find(y);
            if(p>0){
                ans+=x;
                fa[p]=p-1;
            }
        }
        printf("%d\n",ans);
    }
    return 0;
}

Trie树

#include<iostream>
using namespace std;
const int N=100010,M=200010;
int to[M],ne[M],w[M],h[N],idxe=1;
int d[N];
int son[N*31][2],idx;
inline void add(int a,int b,int c){
    to[idxe]=b,w[idxe]=c,ne[idxe]=h[a],h[a]=idxe++;
}
void dfs(int x,int from){
    for(int i=h[x];i;i=ne[i]){
        int j=to[i];
        if(j==from)
            continue;
        d[j]=d[x]^w[i];
        dfs(j,x);
    }
}
inline void insert(int x){
    int p=0;
    for(int i=30;~i;i--){
        int u=x>>i&1;
        if(!son[p][u])
            son[p][u]=++idx;
        p=son[p][u];
    }
}
inline int search(int x){
    int p=0,res=0;
    for(int i=30;~i;i--){
        int u=x>>i&1;
        res<<=1;
        if(son[p][!u])
            p=son[p][!u],res++;
        else
            p=son[p][u];
    }
    return res;
}
int main(){
    int n;
    scanf("%d",&n);
    for(int i=1;i<n;i++){
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        add(a,b,c);
        add(b,a,c);
    }
    dfs(0,-1);
    int ans=0;
    insert(d[0]);
    for(int i=1;i<n;i++){
        ans=max(ans,search(d[i]));
        insert(d[i]);
    }
    printf("%d",ans);
    return 0;
}

Trie树

#include<iostream>
using namespace std;
const int N=3100010;
int son[N][2],idx;
inline int search(int x){
    int p=0,res=0;
    for(int i=30;i>=0;i--){
        int u=x>>i&1;
        res<<=1;
        if(son[p][!u])
            p=son[p][!u],res++;
        else
            p=son[p][u];
    }
    return res;
}
inline void insert(int x){
    int p=0;
    for(int i=30;i>=0;i--){
        int u=x>>i&1;
        if(!son[p][u])
            son[p][u]=++idx;
        p=son[p][u];
    }
}
int main(){
    int n,ans=0;
    scanf("%d",&n);
    while(n--){
        int x;
        scanf("%d",&x);
        ans=max(ans,search(x));
        insert(x);
    }
    printf("%d",ans);
    return 0;
}

Trie树

#include<iostream>
#include<cstring>
using namespace std;
const int N=1000010;
char s[N];
int son[N][30],cnt[N],idx;
inline void add(char *a){
    int p=0,len=strlen(a);
    for(int i=0;i<len;i++){
        if(!son[p][a[i]-'a'])
            son[p][a[i]-'a']=++idx;
        p=son[p][a[i]-'a'];
    }
    cnt[p]++;
}
inline int count(char *a){
    int p=0,len=strlen(a),res=0;
    for(int i=0;i<len;i++){
        if(!son[p][a[i]-'a'])
            return res;
        p=son[p][a[i]-'a'];
        res+=cnt[p];
    }
    return res;
}
int main(){
    int n,m;
    scanf("%d%d",&n,&m);
    while(n--){
        scanf("%s",s);
        add(s);
    }
    while(m--){
        scanf("%s",s);
        printf("%d\n",count(s));
    }
    return 0;
}

kmp

#include<iostream>
using namespace std;
const int N=1000010;
int ne[N];
char a[N];
int main(){
    int n,t=0;
    while(scanf("%d",&n),n){
        scanf("%s",a+1);
        printf("Test case #%d\n",++t);
        for(int i=2,j=0;i<=n;i++){
            while(j&&a[i]!=a[j+1])
                j=ne[j];
            if(a[i]==a[j+1])
                j++;
            ne[i]=j;
        }
        for(int i=2;i<=n;i++)
            if(i%(i-ne[i])==0&&ne[i])
                printf("%d %d\n",i,i/(i-ne[i]));
        puts("");
    }
    return 0;
}

哈希+二分

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
typedef long long LL;
const int N=300010,P=131;
char s[N];
int n;
LL h[N],p[N];
int sa[N];
inline LL get(int l,int r){
    return h[r]-h[l-1]*p[r-l+1];
}
inline int gmcp(int a,int b){
    int l=0,r=min(n-a+1,n-b+1);
    while(l<r){
        int mid=l+r+1>>1;
        if(get(a,a+mid-1)!=get(b,b+mid-1))
            r=mid-1;
        else
            l=mid;
    }
    return l;
}
inline bool cmp(int a,int b){
    int l=gmcp(a,b);
    int av=a+l>n?-0x3f3f3f3f:s[a+l];
    int bv=b+l>n?-0x3f3f3f3f:s[b+l];
    return av<bv;
}
int main(){
    scanf("%s",s+1);
    n=strlen(s+1);
    p[0]=1;
    for(int i=1;i<=n;i++){
        h[i]=h[i-1]*P+s[i]-'a'+1;
        p[i]=p[i-1]*P;
        sa[i]=i;
    }
    sort(sa+1,sa+1+n,cmp);
    for(int i=1;i<=n;i++)
        printf("%d ",sa[i]-1);
    puts("");
    printf("0 ");
    for(int i=2;i<=n;i++)
        printf("%d ",gmcp(sa[i-1],sa[i]));
    return 0;
}

字符串哈希+前缀+后缀

#include<iostream>
#include<cstring>
using namespace std;
typedef long long LL;
const int N=2000010,P=131;
char s[N];
LL h1[N],h2[N],p[N];
inline LL get(LL *h,LL l,LL r){
    return h[r]-h[l-1]*p[r-l+1];
}
int main(){
    int cnt=0;
    while(scanf("%s",s+1),strcmp(s+1,"END")){
        int n=strlen(s+1)<<1;
        for(int i=n;i;i-=2){
            s[i]=s[i>>1];
            s[i-1]='z'+1;
        }
        s[++n]='z'+1;
        p[0]=1;
        for(int i=1,j=n;i<=n;i++,j--){
            h1[i]=h1[i-1]*P+s[i]-'a'+1;
            h2[i]=h2[i-1]*P+s[j]-'a'+1;
            p[i]=p[i-1]*P;
        }
        LL ans=1;
        for(int i=1;i<=n;i++){
            LL r=min(i-1,n-i);
            if(ans>=r||get(h1,i-ans,i-1)!=get(h2,n-i-ans+1,n-i))
                continue;
            while(ans<=r&&get(h1,i-ans,i-1)==get(h2,n-i-ans+1,n-i))
                ans++;
            ans--;
        }
        printf("Case %d: %d\n",++cnt,ans);
    }
    return 0;
}

字符串哈希

#include<iostream>
#include<cstring>
using namespace std;
typedef long long LL;
const int N=1000010,Hash=131;
LL sum[N],p[N];
char s[N];
int main(){
    scanf("%s",s+1);
    int len=strlen(s+1),n;
    p[0]=1;
    for(int i=1;i<=len;i++){
        sum[i]=sum[i-1]*Hash+(s[i]-'a'+1);
        p[i]=p[i-1]*Hash;
    }
    scanf("%d",&n);
    while(n--){
        int l1,r1,l2,r2;
        scanf("%d%d%d%d",&l1,&r1,&l2,&r2);
        if(sum[r1]-sum[l1-1]*p[r1-l1+1]==sum[r2]-sum[l2-1]*p[r2-l2+1])
            puts("Yes");
        else
            puts("No");
    }
    return 0;
}

哈希

#include<iostream>
using namespace std;
typedef long long LL;
const int N=100010,mod=92083;
int tmp[10];
int h[N],ne[N];
int snow[N][10],idx;
inline int geth(int *a){
    int res1=0,res2=1;
    for(int i=0;i<6;i++){
        res1=(res1+a[i])%mod;
        res2=(LL)res2*a[i]%mod;
    }
    return (res1+res2)%mod;
}
inline bool check(int *a,int *b){
    for(int i=0;i<6;i++){
        bool flag=1;
        for(int k=0;k<6;k++)
            if(a[k]!=b[(i+k)%6])
                flag=0;
        if(flag)
            return 1;
        flag=1;
        for(int k=0;k<6;k++)
            if(a[k]!=b[((i-k)%6+6)%6])
                flag=0;
        if(flag)
            return 1;
    }
    return 0;
}
inline bool insert(int *a){
    int hash=geth(a);
    for(int i=h[hash];i;i=ne[i])
        if(check(a,snow[i]))
            return 1;
    idx++;
    for(int i=0;i<6;i++)
        snow[idx][i]=a[i];
    ne[idx]=h[hash];
    h[hash]=idx;
    return 0;
}
int main(){
    int n;
    scanf("%d",&n);
    while(n--){
        for(int i=0;i<6;i++)
            scanf("%d",&tmp[i]);
        if(insert(tmp)){
            puts("Twin snowflakes found.");
            return 0;
        }
    }
    puts("No two snowflakes are alike.");
    return 0;
}

双链表

#include<iostream>
#include<algorithm>
#include<cmath>
#define x first
#define y second
using namespace std;
typedef long long LL;
typedef pair<LL,int> PLI;
const int N=100010;
PLI a[N],ans[N];
int p[N],l[N],r[N];
int main(){
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%lld",&a[i].x);
        a[i].y=i;
    }
    sort(a+1,a+1+n);
    a[0].x=-4e9,a[n+1].x=4e9;
    for(int i=1;i<=n;i++)
        l[i]=i-1,r[i]=i+1,p[a[i].y]=i;
    for(int i=n;i>=2;i--){
        int j=p[i],left=l[j],right=r[j];
        LL lv=a[j].x-a[left].x,rv=a[right].x-a[j].x;
        if(lv<=rv)
            ans[i]={lv,a[left].y};
        else
            ans[i]={rv,a[right].y};
        l[right]=left,r[left]=right;
    }
    for(int i=2;i<=n;i++)
        printf("%lld %d\n",ans[i].x,ans[i].y);
    return 0;
}