Cptraser/ 十一月 8, 2018/ 2018.11/ 0 comments

NOIP前模板知识总结

字符串哈希

namespace Hash{
    #define max_size 10005
    #define Mod 2333333
    string s[max_size];
    int Hash_table[2333335],nxt[max_size],Cnt;
    #undef max_size
    #define Add(x,c) (nxt[++Cnt]=Hash_table[x],s[Cnt]=c,Hash_table[x]=Cnt)
    #define Get(x,c) (x=(x*107%Mod+(c-'0')*233%Mod)%Mod)
    void insert(string S){
        int res=0;for(int i=0;i<S.size();++i)Get(res,S[i]);
        Add(res,S);
    }
    #undef Add
    int Query(string S){
        int res=0;for(int i=0;i<S.size();++i)Get(res,S[i]);
        for(int i=Hash_table[res];i;i=nxt[i])if(s[i]==S)return true;
        return false;
    }
    #undef Mod
    #undef Get
}

Kruskal生成树

namespace Kruskal{
    #define MaxN 5005
    #define MaxE 200005
    int N,M,Fa[MaxN],Ans;
    struct Edge{int x,y,c;bool operator<(Edge P)const{return c<P.c;}}E[MaxE];
    int get(int x){return x==Fa[x]?x:Fa[x]=get(Fa[x]);}
    int Make_tree(void){
        scanf("%d%d",&N,&M),Ans=0;
        for(int i=1;i<=N;i++)Fa[i]=i;
        for(int i=1;i<=M;i++)scanf("%d%d%d",&E[i].x,&E[i].y,&E[i].c);
        sort(E+1,E+M+1);
        for(int i=1;i<=M;i++){
            int x=get(E[i].x),y=get(E[i].y);
            if(x^y)Ans+=E[i].c,Fa[x]=y;
        }return Ans;
    }
    #undef MaxN
    #undef MaxE
}

由于Prim生成树没有什么性质,NOIp应该不考这里就不给出了。


Dijkstra堆优化

namespace Dijkstra_Heap{
    #define MaxN 10005
    #define MaxE 500005
    int N,M,S,x,y,c,dis[MaxN],done[MaxN];
    struct Node{int x,dis;bool operator<(Node x)const{return dis>x.dis;}}front;
    priority_queue<Node>Q;
    int head[MaxN],nxt[MaxE],to[MaxE],w[MaxE],Cnt;
    #undef MaxN
    #undef MaxE
    #define Add(x,y,c) (nxt[++Cnt]=head[x],to[Cnt]=y,w[Cnt]=c,head[x]=Cnt)
    void Solve(void){
        memset(dis,63,sizeof dis);
        scanf("%d%d%d",&N,&M,&S),Q.push((Node){S,0}),dis[S]=0;
        for(int i=1;i<=M;++i)scanf("%d%d%d",&x,&y,&c),Add(x,y,c);
        for(;!Q.empty();){
            front=Q.top(),Q.pop();
            if(done[front.x])continue;
            done[front.x]=1;
            for(int i=head[front.x];i;i=nxt[i])
                if(dis[front.x]+w[i]<dis[to[i]]){
                    dis[to[i]]=dis[front.x]+w[i];
                    Q.push(Node{to[i],dis[to[i]]});
                }
        }
    }
    #undef Add
}

SPFA

namespace SPFA{
    #define MaxN 10005
    #define MaxE 500005
    queue<int>Q;
    int N,M,S,front,dis[MaxN],vis[MaxN],x,y,c;
    int head[MaxN],to[MaxE],nxt[MaxE],w[MaxE],Cnt;
    #undef MaxN
    #undef MaxE
    #define Add(x,y,c) (nxt[++Cnt]=head[x],to[Cnt]=y,w[Cnt]=c,head[x]=Cnt)
    void Solve(void){
        memset(dis,63,sizeof dis);
        scanf("%d%d%d",&N,&M,&S),dis[S]=0,Q.push(S);
        for(int i=1;i<=M;i++)scanf("%d%d%d",&x,&y,&c),Add(x,y,c);
        for(;!Q.empty();Q.pop(),vis[front]=0){
            for(int i=head[front=Q.front()];i;i=nxt[i])
                if(dis[to[i]]>dis[front]+w[i]){
                    dis[to[i]]=dis[front]+w[i];
                    if(!vis[to[i]])Q.push(to[i]),vis[to[i]]=1;
                }
        }
    }
    #undef Add
}

树状数组

//change one,query section
namespace BIT1{
    #define MaxSize 500005
    int Seg[MaxSize];
    void Add(int x,int v){for(;x<=MaxSize;x+=x&-x)Seg[x]+=v;}
    int Query(int x){int res=0;for(;x;x-=x&-x)res+=Seg[x];return res;}
    #undef MaxSize
}

//change section,query one,needs difference
namespace BIT2{
    #define MaxSize 500005
    int Seg[MaxSize];
    void Add(int x,int v){for(;x;x-=x&-x)Seg[x]+=v;}
    int Query(int x){int res=0;for(;x<=MaxSize;x+=x&-x)res+=Seg[x];return res;}
    #undef MaxSize
}

三分

namespace trisection{
    int N;
    double L,R,LMid,RMid,Mid,A[15],Ans,k;
    double f(double x){Ans=0,k=1;for(int i=N;~i;--i)Ans+=k*A[i],k*=x;return Ans;}
    #define eps 1e-12
    double Solve(void){
        cin>>N>>L>>R;
        for(int i=0;i<=N;++i)cin>>A[i];
        for(;R-L>eps;){
            LMid=L+(R-L)/3,RMid=R-(R-L)/3;
            f(LMid)<=f(RMid)?L=LMid:R=RMid;
        }return L;
    }
    #undef eps
}

ST

namespace ST{
    #define MaxN 100005
    int F[20][MaxN],N,M,x,y;
    #undef MaxN
    #define max(x,y) ((x)>(y)?(x):(y))
    int Query(int x,int y){
        if(x>y)return 0;
        int k=log2(y-x+1);
        return max(F[k][x],F[k][y-(1<<k)+1]);
    }
    void Solve(void){
        scanf("%d%d",&N,&M);
        for(int i=1;i<=N;++i)scanf("%d",&F[0][i]);
        for(int i=1;(1<<i)<=N;i++)
            for(int j=1;j+(1<<i)-1<=N;j++)
                F[i][j]=max(F[i-1][j],F[i-1][j+(1<<i-1)]);
        for(int i=1;i<=M;i++){
            scanf("%d%d",&x,&y);
            printf("%d\n",Query(x,y));
        }
    }
    #undef max
}


矩阵快速幂

namespace Matrix_Pow{
    #define Max_Size 105
    #define Mod 1000000007
    long long K;
    int N;
    struct Matrix{
        long long A[Max_Size][Max_Size];
        void clear(void){memset(A,0,sizeof A);}
        Matrix operator*(Matrix P)const{
            Matrix C;C.clear();
            for(int i=1;i<=N;i++)
                for(int j=1;j<=N;j++){
                    for(int k=1;k<=N;k++)
                        C.A[i][j]+=A[i][k]*P.A[k][j]%Mod;
                    C.A[i][j]%=Mod;//小优化
                }
            return C;
        }
        void remain(void){
            clear();for(int i=1;i<=N;i++)A[i][i]=1;
        }
    }O,Res;
    void Pow(long long k){
        Res.remain();
        for(;k;k>>=1,O=O*O)if(k&1)Res=Res*O;
    }
    void init(void){
        scanf("%d%lld",&N,&K);
        for(int i=1;i<=N;i++)
            for(int j=1;j<=N;j++)scanf("%lld",&O.A[i][j]);
        Pow(K);
    }
    void write_Ans(void){
        for(int i=1;i<=N;i++,putchar('\n'))
            for(int j=1;j<=N;j++)printf("%lld ",Res.A[i][j]);
    }
}

KMP

namespace KMP{
    #define MaxN 1000005
    string S,P;
    int fail[MaxN],lena,lenb;
    #undef MaxN
    void init(void){cin>>P>>S;lena=P.size(),lenb=S.size();}
    void preSolve(void){
        int j=-1;fail[0]=-1;
        for(int i=1;i<lenb;i++){
            for(;~j&&S[j+1]!=S[i];)j=fail[j];
            fail[i]=(j+=(S[j+1]==S[i]));
        }
    }
    void Solve(void){
        int j=-1;
        for(int i=0;i<lena;i++){
            for(;~j&&S[j+1]!=P[i];)j=fail[j];
            if((j+=(S[j+1]==P[i]))==lenb-1)printf("%d\n",i-lenb+1+1),j=fail[j];
        }
    }
    void write_Ans(void){
        for(int i=0;i<lenb;i++)printf("%d ",fail[i]+1);
    }
}

乘法逆元

namespace inverse{
    #define MaxN 3000005
    int inv[MaxN],N,Mod;
    void Solve(void){
        scanf("%d%d",&N,&Mod),inv[0]=inv[1]=1;
        for(int i=2;i<=N;++i)inv[i]=1ll*(Mod-Mod/i)*inv[Mod%i]%Mod;
    }
    void write_ans(void){
        for(int i=1;i<=N;i++)printf("%d\n",inv[i]);
    }
}//O(N) for O(1)

用费马小定理和扩展欧几里得可以在log_2的时间复杂度下求出一个数的答案。
费马小定理要在模数为质数的的情况下使用,扩展欧几里得只要要求的数和模数互质即可。


LCA

namespace LCA{
    #define MaxN 500005
    int N,M,x,y,Root,F[20][MaxN],Dep[MaxN];
    int head[MaxN],nxt[MaxN<<1],to[MaxN<<1],Cnt;
    #undef MaxN
    #define Add(x,y) (nxt[++Cnt]=head[x],to[Cnt]=y,head[x]=Cnt)
    void predfs(int x,int fa){
        F[0][x]=fa,Dep[x]=Dep[fa]+1;for(int i=head[x];i;i=nxt[i])if(fa^to[i])predfs(to[i],x);
    }
    void init(void){
        read(N),read(M),read(Root);
        for(int i=1;i<N;i++)read(x),read(y),Add(x,y),Add(y,x);
        predfs(Root,0);
        for(int i=1;i<=18;i++)
            for(int j=1;j<=N;j++)F[i][j]=F[i-1][F[i-1][j]];
    }
    #undef Add
    int LCA(int x,int y){
        if(Dep[x]<Dep[y])swap(x,y);
        for(int i=18;~i;--i)if(Dep[F[i][x]]>=Dep[y])x=F[i][x];
        if(x==y)return x;
        for(int i=18;~i;--i)if(F[i][x]^F[i][y])x=F[i][x],y=F[i][y];
        return F[0][x];
    }
    void write_Ans(void){
        for(int i=1;i<=M;i++)read(x),read(y),write(LCA(x,y)),putchar('\n');
    }
}//树上倍增
Share this Post

Leave a Comment

电子邮件地址不会被公开。 必填项已用*标注

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>
*
*