首页 > 其他分享 >模板库

模板库

时间：2022-08-30 17:58:12浏览次数：47  
标签：int nd num Complex BINT c11 模板

完整版代码

#include<bits/stdc++.h>
#define ll long long
#define pb push_back
#define mp std::make_pair
#define pii std::pair<int,int>
#define chkmin(_A,_B) (_A=std::min(_A,_B))
#define chkmax(_A,_B) (_A=std::max(_A,_B))
//--------------------FastInOut--------------------//
struct IO{
    inline char read(){
        static const int IN_LEN =1<<18|1;
        static char buf[IN_LEN],*s,*t;
        return (s==t)&&(t=(s=buf)+fread(buf, 1, IN_LEN, stdin)),(s==t)?-1:*s++;
    }
    template<typename _Tp>inline IO &operator >>(_Tp &x){
        static char c11, boo;
        for (c11=read(),boo=0;!isdigit(c11);c11=read()) {
            if (c11==-1)
                return *this;
            boo|=(c11=='-');
        }
        for(x=0;isdigit(c11);c11=read())
            x=x*10+(c11^'0');
        if(boo)
            x=-x;
        return *this;
    }
    inline void push(const char &c) {
        putchar(c);
    }
    template<typename _Tp>inline IO &operator <<( _Tp x){
        if (x<0)
            x=-x,push('-');
        static _Tp sta[35];
        _Tp top=0;
        do{
            sta[top++]=x%10,x/=10;
        }while(x);
        while(top)
            push(sta[--top]+'0');
        return *this;
    }
    inline IO &operator <<(char lastChar){
        push(lastChar);
        return *this; 
    }
}FIO;
//--------------------High-Precision--------------------//
struct BINT{
    int num[100005];
    int f;
    BINT(){
        memset(num,0,sizeof(num));
        f=0;
    }
    BINT(char *s){
        memset(num,0,sizeof(num));
        f=(s[0]=='-')?1:0;
        num[0]=strlen(s);
        for(int i=num[0]-1,j=1;i>=f;--i,++j){
            num[j]=s[i]-'0';
        }
        num[0]-=f;
    }
    BINT(ll x){
        memset(num,0,sizeof(num));
        if(x<0)
            f=1,x=-x;
        while(x){
            num[++num[0]]=x%10;
            x/=10;
        }
    }
    friend BINT BABS(const BINT &A){
        BINT ret=A;
        ret.f=0;
        return ret;
    }
    friend bool operator <(const BINT &A,const BINT &B){
        if(A.f!=B.f)
            return (A.f==1);
        int fx=A.f;
        if(A.num[0]<B.num[0])
            return 1^fx;
        if(A.num[0]>B.num[0])
            return 0^fx;
        for(int i=A.num[0];i>=1;--i){
            if(A.num[i]!=B.num[i])
                return (A.num[i]<B.num[i])^fx;
        }
        return 0;
    }
    friend BINT operator +(const BINT &A,const BINT &B){
        BINT ret;
        if(A.f==B.f){
            ret.f=A.f;
            ll jw=0;
            ret.num[0]=std::max(A.num[0],B.num[0]);
            for(int i=1;i<=ret.num[0];++i){
                jw+=A.num[i]+B.num[i];
                ret.num[i]=jw%10;
                jw/=10;
            }
            while(jw){
                ret.num[++ret.num[0]]=jw%10;
                jw/=10;
            }
            return ret;
        }
        else{
            if(A.f==0){
                return A-BABS(B);
            }
            else{
                return B-BABS(A);
            }
        }
    }
    friend BINT operator -(const BINT &A,const BINT &B){
        BINT ret;
        if(A.f==B.f){
            int fx=A.f;
            if(BABS(A)<BABS(B)){
                ret=B-A;
                ret.f^=(fx^1);
                return ret;
            }
            ll jw=0;
            ret.num[0]=std::max(A.num[0],B.num[0]);
            for(int i=1;i<=ret.num[0];++i){
                ret.num[i]=A.num[i]-B.num[i]-jw;
                if(ret.num[i]<0){
                    ret.num[i]+=10;
                    jw=1;
                }
                else
                    jw=0;
            }
            while(ret.num[ret.num[0]]==0 && ret.num[0])
                ret.num[0]--;
            ret.f=fx;
            return ret;
        }
        else{
            if(A.f==0){
                return A+BABS(B);
            }
            else{
                ret=B+BABS(A);
                ret.f^=1;
                return ret;
            }
        }
    }
    friend BINT operator *(const BINT &A,ll B){
        BINT ret;
        ret.f=A.f^((B<0)?1:0);
        if(B<0)
            B=-1*B;
        ll jw=0;
        for(int i=1;i<=A.num[0];++i){
            jw+=A.num[i]*B;
            ret.num[i]=jw%10;
            jw/=10;
        }
        ret.num[0]=A.num[0];
        while(jw){
            ret.num[++ret.num[0]]=jw%10;
            jw/=10;
        }
        while(ret.num[ret.num[0]]==0 && ret.num[0])
            ret.num[0]--;
        return ret;
    }
    void print(){
        if(num[0]==0){
            FIO<<0;
            return ;
        }
        if(f)
            FIO<<'-';
        for(int i=num[0];i>=1;--i)
            FIO<<num[i];
        return ;
    }
};
//--------------------BinaryIndexedTree--------------------//
struct BIT{
    ll c[10005],maxn;
    BIT(int _maxn){
        maxn=_maxn;
        memset(c,0,sizeof(c));
    }
    void AddNum(int x,ll y){
        for(;x<=maxn;x+=x&(-x))
            c[x]+=y;
    }
    ll GetSum(int x){
        ll ret=0;
        for(;x;x-=x&(-x))
            ret+=c[x];
        return ret;
    }
};
//--------------------DSU--------------------//
struct DSU{
    int f[10005],sz[10005];
    DSU(int _maxn=0){
        for(int i=1;i<=_maxn;++i)
            f[i]=i,sz[i]=1; 
    }
    int GetFa(int x){
        return (f[x]==x)?x:f[x]=GetFa(f[x]);
    }
    void Union(int x,int y){
        int fx=GetFa(x),fy=GetFa(y);
        if(fx==fy)
            return;
        if(sz[fx]<sz[fy])
            std::swap(fx,fy);
        f[fy]=fx;
        sz[fx]+=sz[fy];
    }
};

//--------------------Complex--------------------//
struct Complex{
    double a,b;
    Complex(double _a=0,double _b=0){
        a=_a,b=_b;
    }
    friend Complex operator +(const Complex &A,const Complex &B){
        return Complex(A.a+B.a,A.b+B.b);
    }
    friend Complex operator -(const Complex &A,const Complex &B){
        return Complex(A.a-B.a,A.b-B.b);
    }
    friend Complex operator *(const Complex &A,const Complex &B){
        return Complex(A.a*B.a-A.b*B.b,A.a*B.b+A.b*B.a);
    }
};
//--------------------FastFourierTransform--------------------//
struct FFT{
    int limit,l;
    int r[4000005];
    Complex f[4000005],g[4000005];
    double Pi;
    int F,G;
    void init(){
        limit=1;
        while(limit<=F+G)
            limit<<=1,l++;
        for(int i=0;i<limit;++i)
            r[i]=(r[i>>1]>>1)|((i&1)<<(l-1));
        Pi=acos(-1.0);
    }
    void fft(Complex *A,int op){
        for(int i=0;i<limit;++i)
            if(i<r[i])
                std::swap(A[i],A[r[i]]);
        for(int mid=1;mid<limit;mid<<=1){
            Complex Wn(cos(Pi/mid),op*sin(Pi/mid));
            for(int R=mid<<1,j=0;j<limit;j+=R){
                Complex w(1,0);
                for(int k=0;k<mid;k++,w=w*Wn){
                    Complex x=A[j+k],y=w*A[j+mid+k];
                    A[j+k]=x+y;
                    A[j+mid+k]=x-y;
                }
            }
        }
    }
    void getmul(){
        fft(f,1);
        fft(g,1);
        for(int i=0;i<=limit;++i)
            f[i]=f[i]*g[i];
        fft(f,-1);
    }
};
//--------------------SuffixAutomaton--------------------//
struct SAM{
    char s[1000005];
    struct node{
        int fa,son[26];
        int len;
    }nd[2000005];
    int lst,ncnt;
    SAM(){
        lst=ncnt=1;
    }
    void insert(int x){
        int nw=++ncnt;
        nd[nw].len=nd[lst].len+1;
        int p=lst;
        lst=nw;
        for(;p && nd[p].son[x]==0;p=nd[p].fa)
            nd[p].son[x]=nw;
        if(p==0)
            nd[nw].fa=1;
        else{
            int q=nd[p].son[x];
            if(nd[q].len+1==nd[nw].len)
                nd[nw].fa=q;
            else{
                int nq=++ncnt;
                nd[nq].len=nd[q].len+1;
                memcpy(nd[nq].son,nd[q].son,sizeof nd[nq].son);
                nd[nq].fa=nd[q].fa;
                nd[q].fa=nd[nw].fa=nq;
                for(;nd[p].son[x]==q;p=nd[p].fa)
                    nd[p].son[x]=nq;
            }
        }
    }
    void build(){
        scanf("%s",s+1);
        int slen=strlen(s);
        for(int i=1;i<=slen;++i)
            insert(s[i]-'a');
    }
};

struct KMP{
	char s[1000005],t[1000005];
	int nxt[1000005];
	void getnxt(){
		int tlen=strlen(t+1);
		for(int i=2,j=0;i<=tlen;++i){
			while(j && t[j+1]!=t[i])
				j=nxt[j];
			if(t[j+1]==t[i])
				++j;
			nxt[i]=j;
		}
	}
	int getans(){
		int slen=strlen(s+1);
		int tlen=strlen(t+1);
		int ret=0;
		for(int i=1,j=0;i<=slen;++i){
			while(j && s[i]!=t[j+1])
				j=nxt[j];
			if(s[i]==t[j+1])
				j++;
			if(j==tlen){
				++ret;
				j=nxt[j];
				printf("%d\n",i-tlen+1);
			}
		}
		return ret;
	}
};

头文件

程序

#include<bits/stdc++.h>
#define ll long long
#define pb push_back
#define mp std::make_pair
#define pii std::pair<int,int>
#define chkmin(_A,_B) (_A=std::min(_A,_B))
#define chkmax(_A,_B) (_A=std::max(_A,_B))

快读快写

程序

struct IO{
    inline char read(){
        static const int IN_LEN =1<<18|1;
        static char buf[IN_LEN],*s,*t;
        return (s==t)&&(t=(s=buf)+fread(buf, 1, IN_LEN, stdin)),(s==t)?-1:*s++;
    }
    template<typename _Tp>inline IO &operator >>(_Tp &x){
        static char c11, boo;
        for (c11=read(),boo=0;!isdigit(c11);c11=read()) {
            if (c11==-1)
                return *this;
            boo|=(c11=='-');
        }
        for(x=0;isdigit(c11);c11=read())
            x=x*10+(c11^'0');
        if(boo)
            x=-x;
        return *this;
    }
    inline void push(const char &c) {
        putchar(c);
    }
    template<typename _Tp>inline IO &operator <<( _Tp x){
        if (x<0)
            x=-x,push('-');
        static _Tp sta[35];
        _Tp top=0;
        do{
            sta[top++]=x%10,x/=10;
        }while(x);
        while(top)
            push(sta[--top]+'0');
        return *this;
    }
    inline IO &operator <<(char lastChar){
        push(lastChar);
        return *this; 
    }
}FIO;

使用方法

FIO<<n<<m 用来输出， FIO>>n>>m 用来读入（仅限整型和单个字符，用法与 cin 和 cout 相同）。

高精度

程序

struct BINT{
    int num[100005];
    int f;
    BINT(){
        memset(num,0,sizeof(num));
        f=0;
    }
    BINT(char *s){
        memset(num,0,sizeof(num));
        f=(s[0]=='-')?1:0;
        num[0]=strlen(s);
        for(int i=num[0]-1,j=1;i>=f;--i,++j){
            num[j]=s[i]-'0';
        }
        num[0]-=f;
    }
    BINT(ll x){
        memset(num,0,sizeof(num));
        if(x<0)
            f=1,x=-x;
        while(x){
            num[++num[0]]=x%10;
            x/=10;
        }
    }
    friend BINT BABS(const BINT &A){
        BINT ret=A;
        ret.f=0;
        return ret;
    }
    friend bool operator <(const BINT &A,const BINT &B){
        if(A.f!=B.f)
            return (A.f==1);
        int fx=A.f;
        if(A.num[0]<B.num[0])
            return 1^fx;
        if(A.num[0]>B.num[0])
            return 0^fx;
        for(int i=A.num[0];i>=1;--i){
            if(A.num[i]!=B.num[i])
                return (A.num[i]<B.num[i])^fx;
        }
        return 0;
    }
    friend BINT operator +(const BINT &A,const BINT &B){
        BINT ret;
        if(A.f==B.f){
            ret.f=A.f;
            ll jw=0;
            ret.num[0]=std::max(A.num[0],B.num[0]);
            for(int i=1;i<=ret.num[0];++i){
                jw+=A.num[i]+B.num[i];
                ret.num[i]=jw%10;
                jw/=10;
            }
            while(jw){
                ret.num[++ret.num[0]]=jw%10;
                jw/=10;
            }
            return ret;
        }
        else{
            if(A.f==0){
                return A-BABS(B);
            }
            else{
                return B-BABS(A);
            }
        }
    }
    friend BINT operator -(const BINT &A,const BINT &B){
        BINT ret;
        if(A.f==B.f){
            int fx=A.f;
            if(BABS(A)<BABS(B)){
                ret=B-A;
                ret.f^=(fx^1);
                return ret;
            }
            ll jw=0;
            ret.num[0]=std::max(A.num[0],B.num[0]);
            for(int i=1;i<=ret.num[0];++i){
                ret.num[i]=A.num[i]-B.num[i]-jw;
                if(ret.num[i]<0){
                    ret.num[i]+=10;
                    jw=1;
                }
                else
                    jw=0;
            }
            while(ret.num[ret.num[0]]==0 && ret.num[0])
                ret.num[0]--;
            ret.f=fx;
            return ret;
        }
        else{
            if(A.f==0){
                return A+BABS(B);
            }
            else{
                ret=B+BABS(A);
                ret.f^=1;
                return ret;
            }
        }
    }
    friend BINT operator *(const BINT &A,ll B){
        BINT ret;
        ret.f=A.f^((B<0)?1:0);
        if(B<0)
            B=-1*B;
        ll jw=0;
        for(int i=1;i<=A.num[0];++i){
            jw+=A.num[i]*B;
            ret.num[i]=jw%10;
            jw/=10;
        }
        ret.num[0]=A.num[0];
        while(jw){
            ret.num[++ret.num[0]]=jw%10;
            jw/=10;
        }
        while(ret.num[ret.num[0]]==0 && ret.num[0])
            ret.num[0]--;
        return ret;
    }
    void print(){
        if(num[0]==0){
            FIO<<0;
            return ;
        }
        if(f)
            FIO<<'-';
        for(int i=num[0];i>=1;--i)
            FIO<<num[i];
        return ;
    }
};

使用方法

初始化

可以用 BINT() 来初始化一个为 \(0\) 的高精度，用 BINT(long long) 来初始化一个可以用 \(64\) 位整数表示的高精度数，用 BINT(char[]) 来初始化一个字符串高精度（后 \(2\) 种初始化方法可以为负数）

运算

暂时只支持 BINT+BINT ， BINT-BINT ， BINT*(long long) 以及 BINT<BINT 运算，也自带 BANS(BINT) 函数取绝对值，若需要 BINT*BINT 请移步FFT章节。

输出

自带 print 函数用于输出，支持输出负数。

树状数组

代码

struct BIT{
    ll c[10005],maxn;
    BIT(int _maxn){
        maxn=_maxn;
        memset(c,0,sizeof(c));
    }
    void AddNum(int x,ll y){
        for(;x<=maxn;x+=x&(-x))
            c[x]+=y;
    }
    ll GetSum(int x){
        ll ret=0;
        for(;x;x-=x&(-x))
            ret+=c[x];
        return ret;
    }
};

使用方法

初始化

必须传参 ， BIT(int) 表示该数状数组的大小。

修改与查询

AddNum(int,long long) 函数用于在指定位置添加一个数。 GetSum(int) 用于查询前缀和。

并查集

代码

struct DSU{
    int f[10005],sz[10005];
    DSU(int _maxn=0){
        for(int i=1;i<=_maxn;++i)
            f[i]=i,sz[i]=1; 
    }
    int GetFa(int x){
        return (f[x]==x)?x:f[x]=GetFa(f[x]);
    }
    void Union(int x,int y){
        int fx=GetFa(x),fy=GetFa(y);
        if(fx==fy)
            return;
        if(sz[fx]<sz[fy])
            std::swap(fx,fy);
        f[fy]=fx;
        sz[fx]+=sz[fy];
    }
};

使用方法

初始化

必须传参 ， DSU(int) 表示并查集大小。

查询与合并

复杂度 \(O(\alpha(n))\) 放心使用。 Union(int,int) 将 \(2\) 个并查集合并， GetFa(int) 字面意思。

虚数

代码

struct Complex{
    double a,b;
    Complex(double _a=0,double _b=0){
        a=_a,b=_b;
    }
    friend Complex operator +(const Complex &A,const Complex &B){
        return Complex(A.a+B.a,A.b+B.b);
    }
    friend Complex operator -(const Complex &A,const Complex &B){
        return Complex(A.a-B.a,A.b-B.b);
    }
    friend Complex operator *(const Complex &A,const Complex &B){
        return Complex(A.a*B.a-A.b*B.b,A.a*B.b+A.b*B.a);
    }
};

使用方法

可以 Complex(int,int) 初始化，支持 +-* 操作。

FastFastTle

代码

struct FFT{
    int limit,l;
    int r[4000005];
    Complex f[4000005],g[4000005];
    double Pi;
    int F,G;
    void init(){
        limit=1;
        while(limit<=F+G)
            limit<<=1,l++;
        for(int i=0;i<limit;++i)
            r[i]=(r[i>>1]>>1)|((i&1)<<(l-1));
        Pi=acos(-1.0);
    }
    void fft(Complex *A,int op){
        for(int i=0;i<limit;++i)
            if(i<r[i])
                std::swap(A[i],A[r[i]]);
        for(int mid=1;mid<limit;mid<<=1){
            Complex Wn(cos(Pi/mid),op*sin(Pi/mid));
            for(int R=mid<<1,j=0;j<limit;j+=R){
                Complex w(1,0);
                for(int k=0;k<mid;k++,w=w*Wn){
                    Complex x=A[j+k],y=w*A[j+mid+k];
                    A[j+k]=x+y;
                    A[j+mid+k]=x-y;
                }
            }
        }
    }
    void getmul(){
        init();
        fft(f,1);
        fft(g,1);
        for(int i=0;i<=limit;++i)
            f[i]=f[i]*g[i];
        fft(f,-1);
    }
};

使用方法

首先输入两个函数的最高次 \(F,G\) 并手动输入 \(f[i],g[i]\) ，再使用函数 getmul() 函数，得到的 \(f\) 数组即为所求。

（读入方法，只读实数部分，不要管虚部）。

SAM

代码

struct SAM{
    char s[1000005];
    struct node{
        int fa,son[26];
        int len;
    }nd[2000005];
    int lst,ncnt;
    SAM(){
        lst=ncnt=1;
    }
    void insert(int x){
        int nw=++ncnt;
        nd[nw].len=nd[lst].len+1;
        int p=lst;
        lst=nw;
        for(;p && nd[p].son[x]==0;p=nd[p].fa)
            nd[p].son[x]=nw;
        if(p==0)
            nd[nw].fa=1;
        else{
            int q=nd[p].son[x];
            if(nd[q].len+1==nd[nw].len)
                nd[nw].fa=q;
            else{
                int nq=++ncnt;
                nd[nq].len=nd[q].len+1;
                memcpy(nd[nq].son,nd[q].son,sizeof nd[nq].son);
                nd[nq].fa=nd[q].fa;
                nd[q].fa=nd[nw].fa=nq;
                for(;nd[p].son[x]==q;p=nd[p].fa)
                    nd[p].son[x]=nq;
            }
        }
    }
    void build(){
        scanf("%s",s+1);
        int slen=strlen(s);
        for(int i=1;i<=slen;++i)
            insert(s[i]-'a');
    }
};

使用方法

手动在线插入

调用 insert() 函数即可。

离线插入

直接调用 build() 函数，就会自动输入并建好自动机。

KMP

代码

struct KMP{
	char s[1000005],t[1000005];
	int nxt[1000005];
	void getnxt(){
		int tlen=strlen(t+1);
		for(int i=2,j=0;i<=tlen;++i){
			while(j && t[j+1]!=t[i])
				j=nxt[j];
			if(t[j+1]==t[i])
				++j;
			nxt[i]=j;
		}
	}
	int getans(){
		int slen=strlen(s+1);
		int tlen=strlen(t+1);
		int ret=0;
		for(int i=1,j=0;i<=slen;++i){
			while(j && s[i]!=t[j+1])
				j=nxt[j];
			if(s[i]==t[j+1])
				j++;
			if(j==tlen){
				++ret;
				j=nxt[j];
				printf("%d\n",i-tlen+1);
			}
		}
		return ret;
	}
};

使用方法

手动读入 \(s,t\) 并依次调用 getnxt() 和 getans() （当然如果只需要 \(nxt\) 数组则读入字符串到 \(t\) 并只调用 getnxt() ）。

标签：int,nd,num,Complex,BINT,c11,模板
From： https://www.cnblogs.com/zhouzizhe/p/16640274.html

相关文章

  • 模板下载
    packagecom.cango.erp.cs.controller;importlombok.extern.slf4j.Slf4j;importorg.springframework.beans.factory.annotation.Autowired;importorg.springframewo......
  • C# net PDMan/CHINER/元数建模 生成SqlSugar 代码生成器模板
    C#netPDMan/CHINER/元数建模生成SqlSugar代码生成器模板C#netPDManCHINER元数建模生成SqlSugar代码生成器模板 在版本>=4.0.0版本中增加分类 代码生成器......
  • Django模板语法
    一、Python的模板：HTML代码+模板语法二、模板语法需掌握以下几个用法传值过滤器标签继承导入模板三、简要介绍1.模板语法之传值{{}}#一般给变量使用相关......
  • B/S端界面控件DevExtreme JavaScript—全新的UI模板库 (v22.2)
    DevExtreme拥有高性能的HTML5/JavaScript小部件集合，使您可以利用现代Web开发堆栈（包括React，Angular，ASP.NETCore，jQuery，Knockout等）构建交互式的Web应用程序，该套件附带功能......
  • 推荐 10 套个人觉得还不错的网页模板
    原文链接 推荐10套个人觉得还不错的网页模板这里推荐10套从风格，配色，响应式等几方面个人觉得还不错的网页模板，假以时日用来做企业站，还是某种品牌的官网也好，觉得可......
  • 变参模板改进单例模式
    单例模式保证一个类仅有一个实例，并提供一个访问它的全局访问点泛型单例模式需要变参构造函数，构造函数的参数个数需要支持变化下面是不用变参模板，支持0～6个参数的单例模式......
  • 设计模式—模板方法模式（template）
         模板方法模式，我们来看一下定义：定义了一个算法的骨架，而将一些步骤延迟到子类中，模版方法使得子类可以在不改变算法结构的情况下，重新定义算法的步骤。我们来定......
  • 高精度模板
    赌一手今年CSP必考高精。加法：#include<bits/stdc++.h>usingnamespacestd;stringa,b;vector<int>add(vector<int>A,vector<int>B){if(A.size()<......
  • 模板——数据结构
    线段树维护区间最值以及满足最值的个数structSGT{ intmx[N<<2],tg[N<<2],su[N<<2]; #definemid((l+r)>>1) #definelc(u<<1) #definerc((u<<1)|1) voidbld(......
  • 最长上升子序列【模板】
     P1439【模板】最长公共子序列-洛谷|计算机科学教育新生态(luogu.com.cn)n^2的最长上升子序列解法#include<iostream>usingnamespacestd;intdp[1001][100......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99