代码仓库

代码仓库1代码仓库目录：01.【数学方法】矩阵快速幂02.【数学方法】高斯消元（naïve版）03.【数学方法】高斯消元（mid版）04.【字符串啊】Manacher算法（回文串）05.【字符串啊】KMP（字符串匹配）06.【数据结构】线段树（ZKW单点修改）07.【数据结构】线段树（RMQ）08.【数据结构】线段树（区间加+赋值）09.【数据结构】Splay树（未完全测试）////！！！！10.【数据结构】AVL树（平衡树）11.【图论图论】最小生成树（prim）12.【图论图论】次小生成树13.【图论图论】最大流（Dinic）14.【图论图论】LCA+最大生成树（truck）15.【动态规划】背包01，多重，完全代码仓库2矩阵模板#includecstdio#includecstring#includeiostreamusingnamespacestd;typedeflonglongll;constintP=9973;constintN=13;lln,m;structmatrix{lla[N][N];introw,col;matrix():row(N),col(N){memset(a,0,sizeof(a));}//？？？matrix(intx,inty):row(x),col(y){memset(a,0,sizeof(a));}ll*operator[](intx){returna[x];}matrixoperator*(matrixx){matrixtmp;for(inti=0;i=n+1;i++)for(intj=0;j=n+1;j++){tmp[i][j]=0;for(intk=0;k=n+1;k++)tmp[i][j]=(tmp[i][j]+a[i][k]*x[k][j])%P;}returntmp;}voidoperator*=(matrixx){*this=*this*x;}matrixoperator^(llx){matrixret;for(inti=0;i=n+1;i++)ret[i][i]=1;matrixtmp=*this;for(;x;x=1,tmp*=tmp){if(x&1)ret*=tmp;}returnret;}voidprint(){for(inti=0;i=n+1;i++){for(intj=0;j=n+1;j++)printf(%d,a[i][j]);puts();}代码仓库3}};高斯消元，判断有无解的#includecstdio#includecmath#includecstring#includeiostream#includevectorusingnamespacestd;typedeflonglongLL;constdoubleEPS=1e-6;constintN=55;structmatrix{inta[N][N];introw,col;matrix():row(N),col(N){memset(a,0,sizeof(a));}matrix(intx,inty):row(x),col(y){memset(a,0,sizeof(a));}int*operator[](intx){returna[x];}voidprint(){for(inti=0;irow;i++){for(intj=0;jcol;j++)printf(%d,a[i][j]);puts();}puts();}};intGauss(matrixa,intm,intn){intx_cnt=0;intcol,k;//col为列号,k为行号for(k=0,col=0;km&&coln;++k,++col){intr=k;//r为第col列的一个1for(inti=k;im;++i)if(a[i][col])r=i;if(!a[r][col]){k--;continue;}if(r!=k)for(inti=col;i=n;++i)swap(a[r][i],a[k][i]);代码仓库4for(inti=k+1;im;++i)if(a[i][col])//消元for(intj=col;j=n;++j)a[i][j]^=a[k][j];}for(inti=k;im;++i)if(a[i][n])return-1;if(k=n)returnn-k;//返回自由元个数}高斯消元，求出一组解的#includeiostream#includealgorithm#includecstdio#includecstring#includecmathusingnamespacestd;constintN=1010;constdoubleEPS=1e-7;intm,n;doublea[N][N],x[N];intGauss(intm,intn){intcol=0,k=0;//col为列号,k为行号for(;km&&coln;++k,++col){intr=k;for(inti=k+1;im;++i)if(fabs(a[i][col])fabs(a[r][col]))r=i;if(fabs(a[r][col])EPS){k--;continue;}//列全为0if(r!=k)for(inti=col;i=n;++i)swap(a[k][i],a[r][i]);for(inti=k+1;im;++i)//消元if(fabs(a[i][col])EPS){doublet=a[i][col]/a[k][col];for(intj=col;j=n;j++)a[i][j]-=a[k][j]*t;a[i][col]=0;}}for(inti=k;im;++i)//无解if(fabs(a[i][n])EPS)return-1;if(kn)returnn-k;//自由元个数for(inti=n-1;i=0;i--){//回带求解代码仓库5doubletemp=a[i][n];for(intj=i+1;jn;++j)temp-=x[j]*a[i][j];x[i]=(temp/a[i][i]);}return0;}Manacher算法#includecstdio#includestring#includecstring#includeiostream#includealgorithmusingnamespacestd;constintN=233333;//20W//在o(n)时间内算出以每个点为中心的最大回文串长度intManacher(stringst){intlen=st.size();int*p=newint[len+1];memset(p,0,sizeof(p));intmx=0,id=0;for(inti=1;i=len;i++){if(mxi)p[i]=min(p[2*id-i],mx-i);elsep[i]=1;while(st[i+p[i]]==st[i-p[i]])p[i]++;if(i+p[i]mx){mx=i+p[i];id=i;}}intma=0;for(inti=1;ilen;i++)ma=max(ma,p[i]);delete(p);returnma-1;}intmain(){//freopen(fuck.in,r,stdin);代码仓库6charst[N];while(~scanf(%s,st)){stringst0=$#;for(inti=0;st[i]!='\0';i++){st0+=st[i];st0+=#;}printf(%d\n,Manacher(st0));}return0;}KMP字符串匹配#includecstdio#includecstringusingnamespacestd;typedeflonglongll;constintN=100007;constintP=1000000007;chara[N],b[N];boolmat[N];intnext[N];llf[N];voidgetNext(intm){inti=0,j=-1;next[0]=-1;while(im){if(j==-1||b[i]==b[j]){if(b[++i]!=b[++j])next[i]=j;elsenext[i]=next[j];}elsej=next[j];}}voidKMP(intn,intm){memset(mat,0,sizeof(mat));inti=0,j=0;getNext(m);while(in&&jm){if(j==-1||a[i]==b[j])i++,j++;elsej=next[j];if(!i&&!j)break;代码仓库7if(j==m){mat[i]=1;//printf(mat[%d]get\n,i);j=next[j];}}}线段树(ZKW大法)#includecstdio#includecstring#includeiostream#includealgorithmusingnamespacestd;constintINF=0x3f3f3f3f;constintN=3000100;structlinetree{#definelc(t1)#definerc(t1^1)intmi[N],M;inlinevoidbuild(intn){M=1;while(Mn)M=1;M--;memset(mi,INF,sizeof(mi));for(inti=1+M;i=n+M;i++)scanf(%d,&mi[i]);for(intt=M;t=1;t--)mi[t]=min(mi[lc],mi[rc]);}voidchange(intt,intx){for(mi[t+=M]=x,t=1;t;t=1)mi[t]=min(mi[lc],mi[rc]);}intquery(intl,intr){intans=INF;for(l+=M-1,r+=M+1;l^r^1;l=1,r=1){if(~l&1)ans=min(ans,mi[l^1]);if(r&1)ans=min(ans,mi[r^1]);}returnans;}代码仓库8}T;intmain(){intn,q,ord,x,y;for(;~scanf(%d,&n);){T.build(n);for(scanf(%d,&q);q--;){scanf(%d%d%d,&ord,&x,&y);if(ord)T.change(x,y);elseprintf(%d\n,T.query(x,y));}}return0;}线段树（RMQ）#includecstdio#includecstring#includeiostream#includealgorithmusingnamespacestd;constintINF=0x3f3f3f3f;constintN=600100;intn,ans,m,a[N];structnode{intl,r,id;node(){}node(intx,inty,intz){l=x;r=y;id=z;}}b[N],c[N];inlineboolcmp1(nodea,nodeb){returna.lb.l;}inlineboolcmp2(nodea,nodeb){returna.rb.r;}structlinetree{#definelc(t1)#definerc(t1^1)#definemid(l[t]+r[t]1)intl[N],r[N],ma[N],mi[N],M,ta[N],ti[N];inlinevoidbuild(intn){M=1;while(Mn)M=1;M--;memset(ma,0,sizeof(ma));memset(mi,INF,sizeof(mi));memset(ta,0,siz