KMP

void get_nt(){
    int j=0;
    for(int i=2;i<=tl;++i){
        while(j&&t[i]!=t[j+1])j=nt[j];
        if(t[j+1]==t[i])j+=1;
        nt[i]=j;
    }
    
}
void KMP(){
    int j=0;
    F(i,1,sl){
        while(j&&s[i]!=t[j+1])j=nt[j];
        if(s[i]==t[j+1])j+=1;
        if(j==tl){
            cout<<i-tl+1<<'\n';
            j=nt[j];
        }
    }
}

错一位求nt和j+1来匹配

manacher

void prew(){
    s[++sl]='@';
    s[++sl]='#';
    F(i,1,tl){
        s[++sl]=t[i];
        s[++sl]='#';
    }
    s[++sl]='%';
}
int p[N];
int manacher(){
    int ans=0;
    for(int i=1,r=0,mid=0;i<=sl;++i){
        if(i<=r)p[i]=min(r-i+1,p[(mid<<1)-i]);
        else p[i]=1;
        while(s[i-p[i]]==s[i+p[i]])++p[i];
        if(i+p[i]>r){
            r=i+p[i]-1;
            mid=i;
        }
        ans=max(ans,p[i]);
    }
    return ans;
}
signed main(){
    scanf("%s",t+1);
    tl=strlen(t+1);
    prew();
//  F(i,1,sl)cout<<s[i]<<' ';cout<<'\n';
    cout<<manacher()-1<<'\n';
    return 0;
}

第一位是"@",最后一位是"%",中间是"#",用以区分
求出来的回文半径是变化后的,具体的要具体分析

点双

#include<bits/stdc++.h>
#define int long long
#define F(i,i0,n) for(int i=(i0);i<=(n);i++)
#define D(i,n,i0) for(int i=(n);i>=i0;--i)
#define pii pair<int,int>
#define fr first
#define sc second
#define pb push_back
using namespace std;
inline int rd(){
    int f=0,x=0;char ch=getchar();
    while(!isdigit(ch)){if(ch=='-')f=1;ch=getchar();}
    while(isdigit(ch)){x=(x<<3)+(x<<1)+ch-48;ch=getchar();}
    return f?-x:x;
}
const int N=2e6+5,mod=1e9+7;
int n,m;
struct Id{
    int v,nt;
}e[N<<1];
int p[N],id=1;
void add(int x,int y){
    e[++id]={y,p[x]};p[x]=id;
} 
int dfn[N],low[N],Tim;
int st[N],top;
vector<int>dcc[N];
int tot;
void Tarjan(int x,int ffa){
    dfn[x]=low[x]=++Tim;
    
    int cnt=0;
    if(!p[x]&&ffa==0){
        dcc[++tot].pb(x);
        return ;
    }
    st[++top]=x;
    for(int i=p[x];i;i=e[i].nt){
        int v=e[i].v;
        if(!dfn[v]){
            cnt++;
            Tarjan(v,x);
            low[x]=min(low[x],low[v]);
            if(low[v]>=dfn[x]){
                tot++;
                int y;
                dcc[tot].pb(x);
                do{
                    y=st[top--];
                    dcc[tot].pb(y);
                }while(y!=v);
            }
        }
        else low[x]=min(low[x],dfn[v]);
    }
}
signed main(){
    n=rd(),m=rd();
    F(i,1,m){
        int x=rd(),y=rd();
        if(x==y)continue;
        add(x,y);add(y,x);
    }
    F(i,1,n)if(!dfn[i]){
        Tarjan(i,0);
    }
    cout<<tot<<'\n';
    F(i,1,tot){
        cout<<dcc[i].size()<<' ';
        for(auto v:dcc[i])cout<<v<<" ";cout<<'\n';
    }
    return 0;
}

注意出栈方式,以及点双不用判父亲

欧拉路径

#include <bits/stdc++.h>
#define F(i,i0,n) for(int i=i0;i<=n;i++)
#define mod 23333
#define ll long long
#define MAXN 100005
using namespace std;
inline int rd(){
    int x=0,f=1;char ch=getchar();
    while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
    while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
    return x*f;
}
int n,m,du[MAXN][2],del[MAXN],cnt[MAXN]; //0 rudu 1 chudu
int vis[MAXN];
vector<int >p[MAXN];
stack<int >s;
void dfs(int x){
    for(int i=del[x];i<p[x].size();i=del[x]){
        del[x]=i+1;
        dfs(p[x][i]);
    }
    s.push(x);
}
int main() {
    n=rd(),m=rd(); 
    F(i,1,m){
        int a=rd(),b=rd();
        p[a].push_back(b);
        du[a][1]++;
        du[b][0]++;
    }
    F(i,1,n)sort(p[i].begin(),p[i].end());
    int flag=1;
    int st=1;
    F(i,1,n){
        if(du[i][0]!=du[i][1]){
            flag=0;
            if(du[i][1]-du[i][0]==1)cnt[1]++,st=i;
            else if(du[i][0]-du[i][1]==1)cnt[0]++;
            else {
                cout<<"No"<<endl;
                return 0;
            }
        }
    }
    if(!flag&&!(cnt[0]==cnt[1]&&cnt[0]==1)){
        cout<<"No"<<endl;
        return 0;
    }
    dfs(st);
    while(!s.empty()){
        cout<<s.top()<<' ';s.pop();
    }
    return 0;
}

注意是出的时候加入栈中以及倒序出栈

边双

#include<bits/stdc++.h>
#define int long long
#define F(i,i0,n) for(int i=(i0);i<=(n);i++)
#define D(i,n,i0) for(int i=(n);i>=i0;--i)
#define pii pair<int,int>
#define fr first
#define sc second
#define pb push_back
using namespace std;
inline int rd(){
    int f=0,x=0;char ch=getchar();
    while(!isdigit(ch)){if(ch=='-')f=1;ch=getchar();}
    while(isdigit(ch)){x=(x<<3)+(x<<1)+ch-48;ch=getchar();}
    return f?-x:x;
}
const int N=2e6+5,mod=1e9+7;
int n,m;
struct Id{
    int v,nt;
}e[N<<1];
int p[N],id=1;
void add(int x,int y){
    e[++id]={y,p[x]};p[x]=id;
} 
int dfn[N],low[N],Tim;
vector<int>dcc[N];
int tot;
int cut[N<<1]; 
void Tarjan(int x,int fid){
    dfn[x]=low[x]=++Tim;
    int cnt=0;
    for(int i=p[x];i;i=e[i].nt){
        int v=e[i].v;
        if(!dfn[v]){
            Tarjan(v,i);
            low[x]=min(low[x],low[v]);
            if(low[v]>dfn[x])cut[i]=cut[i^1]=1;
        }
        else if(fid!=(i^1))low[x]=min(low[x],dfn[v]);
    }
}
int vis[N];
void dfs(int x,int ffa){
    vis[x]=1;
    dcc[tot].pb(x);
    for(int i=p[x];i;i=e[i].nt){
        int v=e[i].v;
        if(vis[v]||cut[i])continue;
        dfs(v,x);
    }
}
signed main(){
    n=rd(),m=rd();
    F(i,1,m){
        int x=rd(),y=rd();
        if(x==y)continue;
        add(x,y);add(y,x);
    }
    F(i,1,n)if(!dfn[i]){
        Tarjan(i,0);
    }
    F(i,1,n)if(!vis[i]){
        tot++;
        dfs(i,0);
    }
    cout<<tot<<'\n';
    F(i,1,tot){
        cout<<dcc[i].size()<<' ';
        for(auto v:dcc[i])cout<<v<<" ";cout<<'\n';
    }
    return 0;
}

记录父向边,不能用父向边更新low

线段树

乘法和加法的标记合并时
先pd乘法的标记
因为\((a+b)*c->a*c+b*c\)

void pd(int p,int l,int r){
    tr[ls].s=tr[ls].s*tr[p].tag2;
    tr[ls].tag2*=tr[p].tag2;
    tr[ls].tag1=tr[ls].tag1*tr[p].tag2;
    tr[ls].s+=(mid-l+1)*tr[p].tag1;
    tr[ls].tag1+=tr[p].tag1;
    
    tr[rs].tag2*=tr[p].tag2;
    tr[rs].s=tr[rs].s*tr[p].tag2;
    tr[rs].tag1=tr[rs].tag1*tr[p].tag2;
    tr[rs].s+=(r-mid)*tr[p].tag1;
    tr[rs].tag1+=tr[p].tag1;
    
    tr[p].tag2=1;
    tr[p].tag1=0;
}
void upd_sum(int p,int nl,int nr,int k,int l=1,int r=n){
    pd(p,l,r);
    if(nl<=l&&r<=nr){
        tr[p].s+=(r-l+1)*k;
        tr[p].tag1+=k;
        return ;
    }
}
void upd_mul(int p,int nl,int nr,int k,int l=1,int r=n){
    pd(p,l,r);
    if(nl<=l&&r<=nr){
        tr[p].s*=k;
        tr[p].tag2*=k;
        tr[p].tag1*=k;
        return ;
    }
}

KM

#include<bits/stdc++.h>
#define int long long
#define F(i,i0,n) for(int i=(i0);i<=(n);i++)
#define D(i,n,i0) for(int i=(n);i>=i0;--i)
#define pii pair<int,int>
#define fr first
#define sc second
#define pb push_back
using namespace std;
inline int rd(){
    int f=0,x=0;char ch=getchar();
    while(!isdigit(ch)){if(ch=='-')f=1;ch=getchar();}
    while(isdigit(ch)){x=(x<<3)+(x<<1)+ch-48;ch=getchar();}
    return f?-x:x;
}
const int N=2e6+5,mod=1e9+7;
struct Id{
    int v,nt;
}e[N<<1];
int p[N],id=1;
void add(int x,int y){
    e[++id]={y,p[x]};p[x]=id;
} 
int n,m,E;
int mat[N];
int tim;
int vis[N];
bool km(int u){
    vis[u]=tim;
    for(int i=p[u];i;i=e[i].nt){
        int v=e[i].v;
        if(vis[v]!=tim){
            vis[v]=tim;
            if(!mat[v]||km(mat[v])){
                mat[v]=u;
                return 1;
            }
        }
    }
    return 0;
}
signed main(){
    n=rd(),m=rd(),E=rd();
    F(i,1,E){
        int x=rd(),y=rd();
        add(x,y+n);
    }
    int ans=0;
    F(i,1,n){
        tim++; 
        ans+=km(i);
    }
    cout<<ans<<'\n';
    return 0;
}

总是忘记怎么写?怎么回事呢?