代码仓库培训资料全.docx

《代码仓库培训资料全.docx》由会员分享，可在线阅读，更多相关《代码仓库培训资料全.docx（32页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、代码仓库目录：01.数学方法矩阵快速幂02.数学方法高斯消元（nave版）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，多重，完全矩阵模板#include #include#includeu

2、singnamespace std;typedeflonglong ll;constint P =9973;constint N=13;ll n,m;struct matrix ll aNN;int row,col; matrix():row(N),col(N)memset(a,0,sizeof(a);/？ matrix(int x,int y):row(x),col(y)memset(a,0,sizeof(a); ll*operator(int x)return ax; matrix operator*(matrix x) matrix tmp ;for(int i=0;i=n+1;i+)f

3、or(int j=0;j=n+1;j+) tmpij=0;for(int k=0;k=n+1;k+) tmpij=(tmpij+aik*xkj)%P;return tmp;voidoperator*=(matrix x)*this=*this* x; matrix operator(ll x) matrix ret;for(int i=0;i=1,tmp*=tmp)if(x&1)ret *=tmp;return ret;void print()for(int i=0;i=n+1;i+)for(int j=0;j=n+1;j+) printf(%d ,aij); puts();高斯消元，判断有无

4、解的#include#include#include#include#includeusingnamespace std;typedeflonglong LL;constdouble EPS=1e-6;constint N=55;struct matrixint aNN;int row,col; matrix():row(N),col(N)memset(a,0,sizeof(a); matrix(int x,int y):row(x),col(y) memset(a,0,sizeof(a);int*operator(int x)return ax;void print()for(int i=0

5、;irow;i+)for(int j=0;jcol;j+) printf(%d ,aij); puts(); puts();int Gauss(matrix a,int m,int n)int x_cnt =0;int col, k;/col为列号,k为行号for(k=0,col=0;km&coln;+k,+col)int r = k;/r为第col列的一个1for(int i=k;im;+i)if(aicol)r=i;if(!arcol) k-;continue;if(r!=k)for(int i=col;i=n;+i) swap( ari, aki);for(int i=k+1;im;+i

6、)if(aicol)/消元for(int j=col;j=n;+j)aij=akj;for(int i=k;im;+i)if(ain)return-1;if(k=n)return n-k;/返回自由元个数高斯消元，求出一组解的#include #include #include #include #include usingnamespace std;constint N =1010;constdouble EPS=1e-7;int m,n;double aNN,xN;int Gauss(int m,int n)int col=0, k=0;/col为列号,k为行号for(;km&coln;+

7、k,+col)int r = k;for(int i=k+1;ifabs(arcol)r=i;if(fabs(arcol)EPS)k-;continue;/列全为0if(r!=k)for(int i=col;i=n;+i) swap(aki,ari);for(int i=k+1;iEPS)double t = aicol/akcol;for(int j=col;j=n;j+)aij-=akj*t; aicol=0;for(int i=k ;iEPS)return-1;if(k =0; i-)/回带求解double temp = ain;for(int j=i+1; jn;+j) temp -=

8、 xj* aij; xi=(temp / aii);return0;Manacher算法#include#include#include#include#includeusingnamespace std;constint N=233333;/20W/在o(n)时间算出以每个点为中心的最大回文串长度int Manacher(string st)int len=st.size();int*p=newintlen+1; memset(p,0,sizeof(p);int mx=0,id=0;for(int i=1;ii)pi=min(p2*id-i,mx-i);else pi=1;while(sti

9、+pi=sti-pi)pi+;if(i+pimx)mx=i+pi;id=i;int ma=0;for(int i=1;ilen;i+)ma=max(ma,pi);delete(p);return ma-1;int main()/freopen(fuck.in,r,stdin);char stN;while(scanf(%s,st) string st0=$#;for(int i=0;sti!=0;i+) st0+=sti; st0+=#; printf(%dn,Manacher(st0);return0;KMP 字符串匹配#include#includeusingnamespace std;t

10、ypedeflonglong ll;constint N=100007;constint P=1000000007;char aN,bN;bool matN;int nextN;ll fN;void getNext(int m)int i=0,j=-1; next0=-1;while(im)if(j=-1|bi=bj)if(b+i!=b+j)nexti=j;else nexti=nextj;else j=nextj;void KMP(int n,int m) memset(mat,0,sizeof(mat);int i=0,j=0; getNext(m);while(in&jm)if(j=-1

11、|ai=bj)i+,j+;else j=nextj;if(!i&!j)break;if(j=m) mati=1;/printf(mat%dgetn,i); j=nextj;线段树(ZKW大法)#include#include#include#includeusingnamespace std;constint INF=0x3f3f3f3f;constint N=3000100;struct linetree#define lc (t1)#define rc (t11)int miN,M;inlinevoid build(int n) M=1;while(Mn)M=1; M-; memset(m

12、i,INF,sizeof(mi);for(int i=1+M;i=1;t-)mit=min(milc,mirc);void change(int t,int x)for(mit+=M=x,t=1;t;t=1) mit=min(milc,mirc);int query(int l,int r)int ans = INF;for(l+=M-1,r+=M+1;lr1;l=1,r=1)if(l&1)ans=min(ans,mil1);if( r&1)ans=min(ans,mir1);return ans;T;int main()int n,q,ord,x,y;for(;scanf(%d,&n);)

13、T.build(n);for(scanf(%d,&q);q-;) scanf(%d%d%d,&ord,&x,&y);if(ord)T.change(x,y);else printf(%dn,T.query(x,y);return0;线段树（RMQ）#include#include#include#includeusingnamespace std;constint INF=0x3f3f3f3f;constint N=600100;int n,ans,m,aN;struct node int l,r,id; node () node(int x,int y,int z)l=x;r=y;id=z;

14、bN,cN;inlinebool cmp1(node a,node b)return a.lb.l;inlinebool cmp2(node a,node b)return a.rb.r;struct linetree#define lc (t1)#define rc (t1)int lN,rN,maN,miN,M,taN,tiN;inlinevoid build(int n) M=1;while(Mn)M=1; M-; memset(ma,0,sizeof(ma); memset(mi,INF,sizeof(mi); memset(ta,0,sizeof(ta); memset(ti,INF

15、,sizeof(ti);for(int i=1+M;i=1;t-)lt=llc,rt=rrc;inlinevoid down(int t)if(tM)return;/leaf node malc=max(malc,tat); marc=max(marc,tat); talc=max(talc,tat); tarc=max(tarc,tat); tat=0; milc=min(milc,tit); mirc=min(mirc,tit); tilc=min(tilc,tit); tirc=min(tirc,tit); tit= INF;inlinevoid maintain(int t) mat=

16、max(malc,marc); mit=min(milc,mirc);inlinevoid tag(int t,int x) mat=max(mat,x); mit=min(mit,x); tat=max(tat,x); tit=min(tit,x);void change(int t,int L,int R,int x)if(L=lt&rt=R)tag(t,x);return;/in down(t);if(L=mid)change(lc,L,R,x);if(midM)/leaf node bt-M=ct-M=node(mit,mat,t-M);return; down(t); query(l

17、c); query(rc); maintain(t);T;线段树（区间加+赋值）#include#include#include#includeusingnamespace std;constint N =260000;int n,m;struct linetree#define lc (t1)#define rc (t1)int lN,rN,M,tagN,sumN,lenN,SetN;inlinevoid build(int n) M=1;while(Mn)M=1; M-;/get M memset(sum,0,sizeof(sum); memset(tag,0,sizeof(tag); m

18、emset(Set,0,sizeof(Set);for(int i=1+M;i=M*2+1;i+)/leafif(i=1;t-)/fathers sumt=sumlc+sumrc; lt=llc, rt=rrc; lent=lenlc+lenrc;inlinevoid down(int t)if(tM)Sett=tagt=0;return;/leaf nodeif(Sett) sumlc=Sett*lenlc; sumrc=Sett*lenrc; Setlc=Sett; Setrc=Sett; Sett=0; taglc=tagrc=0;if(tagt) sumlc+=tagt*lenlc;

19、sumrc+=tagt*lenrc; taglc+=tagt; tagrc+=tagt; tagt=0;inlinevoid _tag(int t,int x) sumt+=x*lent; tagt+=x;inlinevoid _set(int t,int x) sumt=x*lent; Sett=x; tagt=0;void change(int t,int L,int R,int x)if(L=lt&rt=R)_tag(t,x);return; down(t);if(L=mid)change(lc,L,R,x);if(mid R)change(rc,L,R,x); sumt=sumlc+s

20、umrc;void set(int t,int L,int R,int x)if(L=lt&rt=R)_set(t,x);return;/in down(t);if(L=mid)set(lc,L,R,x);if(mid R)set(rc,L,R,x); sumt=sumlc+sumrc;int query(int t,int L,int R)if(L=lt&rt=R)return sumt; down(t);int ans =0;if(L=mid)ans+=query(lc,L,R);if(mid R)ans+=query(rc,L,R);return ans;T;Splay-Tree#inc

21、lude#includeusingnamespace std;struct Nodeint key;/size Node *l,*r,*f;/left,right,father;class SplayTreepublic:void Init()rt=NULL;void Zag(Node *x)/left rotate Node *y=x-f;/y is the father of x y-r = x-l;if(x-l)x-l-f = y;/if x has left child x-f =y-f;if(y-f)/y is not rootif(y=y-f-l)y-f-l=x;/y if lef

22、t childelse y-f-r=x;/y is right child y-f=x;x-l=y;void Zig(Node *x)/right rotate Node *y=x-f;/y is the father of x y-l = x-r;if(x-r)x-r-f=y; x-f = y-f;if(y-f)if(y=y-f-l)y-f-l=x;else y-f-r=x; y-f=x; x-r=y;void Splay(Node *x)while(x-f) Node *p=x-f;if(!p-f)if(x=p-l)Zig(x);else Zag(x);elseif(x=p-l)if(p=

23、p-f-l)Zig(p);Zig(x);elseZig(x);Zag(x);else/x=p-rif(p=p-f-r)Zag(p);Zag(x);elseZag(x);Zig(x); rt=x; Node *Find(int x) Node *T=rt;while(T)if(T-key=x)Splay(T);return T;elseif(xkey)T=T-l;else T=T-r;return T;void Insert(int x) Node *T=rt,*fa=NULL;while(T) fa=T;if(xkey)T=T-l;elseif(xT-key)T=T-r;elsereturn;

24、/two the same keys T=(Node*)malloc(sizeof(Node); T-key=x; T-l=T-r=NULL; T-f=fa;if(fa)if(fa-keyx)fa-l=T;else fa-r=T; Splay(T);void Delete(int x) Node *T=Find(x);if(NULL=T)return;/error rt=Join(T-l,T-r); Node *Maxnum(Node *t) Node *T=t;while(T-r)T=T-r; Splay(T);return T; Node *Minnum(Node *t) Node *T=

25、t;while(T-l)T=T-l; Splay(T);return T; Node *Last(int x) Node *T=Find(x); T=T-l;return(Maxnum(T); Node *Next(int x) Node *T=Find(x); T=T-r;return(Minnum(T); Node *Join(Node *t1,Node *t2)if(NULL=t1)return t2;if(NULL=t2)return t1; Node *T=Maxnum(t1); T-l=t2;return T;void Split(int x,Node *&t1,Node *&t2

26、) Node *T=Find(x); t1=T-l;t2=T-r;void Inorder(Node *T)if(NULL=T)return; Inorder(T-l); printf(%d-,T-key); Inorder(T-r);void _Delete()Delete(rt);void Delete(Node *T)if(NULL=T)return; Delete(T-l); Delete(T-r); free(T);private: Node *rt;/root;AVL树/codevs1285 莯/by cww97#include#include#include#define INF

27、 0xfffffff#define BASE 1000000usingnamespace std;int ans=0;struct Nodeint x,bf,h;/bf=balance factor,h=height Node *l,*r;class AVLTreepublic:void Init() rt =NULL;int H(Node *T)return(T=NULL)?0:T-h;int BF(Node *l,Node *r)/get balance factorif(NULL=l &NULL=r)return0;elseif(NULL= l)return-r-h;elseif(NUL

28、L= r)return l-h;return l-h - r-h; Node *Lrorate(Node *a)/left rorate Node *b; b=a-r; a-r=b-l; b-l=a; a-h=max(H(a-l),H(a-r)+1; b-h=max(H(b-l),H(b-r)+1; a-bf=BF(a-l,a-r); b-bf=BF(b-l,b-r);return b; Node *Rrorate(Node *a)/right rorate Node *b; b=a-l; a-l=b-r; b-r=a; a-h=max(H(a-l),H(a-r)+1; b-h=max(H(b

29、-l),H(b-r)+1; a-bf=BF(a-l,a-r); b-bf=BF(b-l,b-r);return b; Node *LRrorate(Node *a)/left then right a-l = Lrorate(a-l); Node *c; c=Rrorate(a);return c; Node *RLrorate(Node *a)/right then left a-r=Rrorate(a-r); Node *c; c=Lrorate(a);return c;void Insert(int x)_Insert(rt,x);void _Insert (Node *&T,int x

30、)if(NULL=T) T=(Node*)malloc(sizeof(Node); T-x=x; T-bf=0;T-h=1; T-l=T-r=NULL;return;if(x x) _Insert(T-l,x);elseif(x T-x) _Insert(T-r,x);elsereturn;/error :the same y T-h=max(H(T-l),H(T-r)+1;/maintain T-bf=BF(T-l,T-r);if(T-bf 1| T-bf bf 0& T-l-bf 0)T=Rrorate(T);elseif(T-bf r-bf bf 0& T-l-bf bf r-bf 0)

31、T=RLrorate(T);void GetPet(int x)/get pet or personif(NULL=rt)return;int small=0,large=INF;/printf(x=%dn,x);int flag;if(Find(rt,x,small,large) printf(find %dn,x); _Delete(rt,x);elseif(small=0)flag=1;elseif(large=INF)flag=0;elseif(large-xx)return1;if(xx) large=min(large,T-x);return Find(T-l,x,small,la

32、rge);else small=max(small,T-x);return Find(T-r,x,small,large);void _Delete(Node *&T,int x)if(NULL=T)return;if(x x)/y at left _Delete(T-l,x); T-bf=BF(T-l,T-r);if(T-bfr-bf)T=RLrorate(T);else T=Lrorate(T);/bf=0 or -1elseif(x T-x)/y at right _Delete(T-r,x); T-bf=BF(T-l,T-r);if(T-bf1)if(-1=T-l-bf)T=LRrorate(T);else T=Rrorate(T);/bf=0 or 1else/here is xif(T-l&T-