代碼倉庫培訓資料(doc 33頁)

1、33代碼倉庫代碼倉庫目錄：01.【數(shù)學方法】矩陣快速冪02.【數(shù)學方法】高斯消元（nave版）03.【數(shù)學方法】高斯消元（mid版）04.【字符串啊】Manacher算法（回文串）05.【字符串啊】KMP（字符串匹配）06.【數(shù)據(jù)結構】線段樹（ZKW單點修改）07.【數(shù)據(jù)結構】線段樹（RMQ）08.【數(shù)據(jù)結構】線段樹（區(qū)間加+賦值）09.【數(shù)據(jù)結構】Splay樹（未完全測試）/！10.【數(shù)據(jù)結構】AVL樹（平衡樹）11.【圖論圖論】最小生成樹（prim）12.【圖論圖論】次小生成樹13.【圖論圖論】最大流（Dinic）14.【圖論圖論】LCA+最大生成樹（truck）15.【動態(tài)規(guī)劃】背包01

2、，多重，完全矩陣模板#include #include#includeusing namespace std;typedef long long ll;const int P = 9973;const int 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

3、* (matrix x) matrix tmp ; for (int i=0;i=n+1;i+) for (int j=0;j=n+1;j+) tmpij=0; for (int k=0;k=n+1;k+) tmpij=(tmpij+aik*xkj)%P; return tmp; void operator *= (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

4、i=0;i=n+1;i+) for (int j=0;j=n+1;j+) printf(%d ,aij); puts(); ;高斯消元，判斷有無解的#include#include#include#include#includeusing namespace std;typedef long long LL;const double EPS=1e-6;const int N=55;struct matrix int aNN; int row,col; matrix():row(N),col(N)memset(a,0,sizeof(a); matrix(int x,int y):row(x),c

5、ol(y) memset(a,0,sizeof(a); int* operator (int x)return ax; void print() for (int i=0;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列的一個1 for (int i=k;im;+i)

6、 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)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; /返回自由元個數(shù)高斯消元，求出一組解的#include #include #include #include #include using namespace std

7、;const int N = 1010;const double 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;+k,+col) int r = k; for (int i=k+1;ifabs(arcol)r=i; if (fabs(arcol)EPS)k-;continue;/列全為0 if (r!=k)for(int i=col;i=n;+i) swap(aki,ari); for (int i=k+1;iEPS) double t = aico

8、l/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 -= xj * aij; xi = (temp / aii); return 0;Manacher算法#include#include#include#include#includeusing namespace std;const int N=233333;/20W/在o(n)時間內算出以每個點

9、為中心的最大回文串長度int Manacher(string st) int len=st.size(); int *p=new intlen+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+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(

10、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); return 0;KMP 字符串匹配#include#includeusing namespace std;typedef long long ll;const int N=100007;const int P=1000000007;char aN,bN;bool matN;int nextN;ll fN;void getNext(in

11、t 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|ai=bj)i+,j+; else j=nextj; if (!i&!j)break; if (j=m) mati=1; /printf(mat%dgetn,i); j=nextj; 線段

12、樹(ZKW大法)#include#include#include#includeusing namespace std;const int INF=0x3f3f3f3f;const int N=3000100;struct linetree #define lc (t1) #define rc (t11) int miN,M; inline void build(int n) M=1; while(Mn)M=1; M-; memset(mi,INF,sizeof(mi); for (int i=1+M;i=1;t-)mit=min(milc,mirc); void change(int t,i

13、nt 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);) T.build(n); for (scanf(%d,&q);q-;) scanf(%d%d%d,&ord,&x,&y);

14、if (ord)T.change(x,y); else printf(%dn,T.query(x,y); return 0;線段樹（RMQ）#include#include#include#includeusing namespace std;const int INF=0x3f3f3f3f;const int 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;bN,cN;inline bool cmp1(node a,node b)return a.lb.l;

15、inline bool 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; inline void 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,sizeof(ti); for (int i=1+M;i=1;t-)lt=l

16、lc,rt=rrc; inline void 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; inline void maintain(int t) mat=max(malc,marc); mit=min(mil

17、c,mirc); inline void 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(lc); query(rc); m

18、aintain(t); T;線段樹（區(qū)間加+賦值）#include#include#include#includeusing namespace std;const int N =260000;int n,m;struct linetree #define lc (t1) #define rc (t1) int lN,rN,M,tagN,sumN,lenN,SetN; inline void build(int n) M=1; while(Mn)M=1; M-;/get M memset(sum,0,sizeof(sum); memset(tag,0,sizeof(tag); memset(S

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

20、lenlc; sumrc+=tagt*lenrc; taglc+=tagt; tagrc+=tagt; tagt = 0; inline void _tag(int t,int x) sumt+=x*lent; tagt+=x; inline void _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,

21、L,R,x); sumt=sumlc+sumrc; 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

22、(rc,L,R); return ans; T;Splay-Tree#include#includeusing namespace std;struct Node int 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 (

23、y-f)/y is not root if (y=y-f-l)y-f-l=x;/y if left child else 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

24、*p=x-f; if (!p-f) if (x=p-l)Zig(x); else Zag(x); else if (x=p-l) if (p=p-f-l)Zig(p);Zig(x); else Zig(x);Zag(x); else /x=p-r if (p=p-f-r)Zag(p);Zag(x); else Zag(x);Zig(x); rt=x; Node *Find(int x) Node *T=rt; while (T) if (T-key=x)Splay(T);return T; else if (xkey)T=T-l; else T=T-r; return T; void Inse

25、rt(int x) Node *T=rt,*fa=NULL; while (T) fa=T; if (xkey)T=T-l; else if(xT-key)T=T-r; else return ;/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

26、-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=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 *t

27、2) 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) 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 (NU

28、LL=T)return ; Delete(T-l); Delete(T-r); free(T); private: Node *rt;/root;AVL樹/codevs1285 莯/by cww97#include#include#include#define INF 0xfffffff#define BASE 1000000using namespace std;int ans=0;struct Node int x,bf,h;/bf=balance factor,h=height Node *l,*r;class AVLTreepublic: void Init() rt = NULL;

29、int H(Node *T)return (T=NULL)?0:T-h; int BF(Node *l,Node *r)/get balance factor if (NULL=l & NULL=r) return 0; else if (NULL = l) return -r-h; else if (NULL = 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)

30、,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-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=Rr

31、orate(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) 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); else if (x T-x)

32、 _Insert(T-r,x); else return ; /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); else if (T-bf r-bf bf 0 & T-l-bf bf r-bf 0)T=RLrorate(T); void GetPet(int x)/get pet or person if (NULL=rt)return ; int small=0,large=INF; /printf(x=%

33、dn,x); int flag; if (Find(rt,x,small,large) printf(find %dn,x); _Delete(rt,x); else if (small=0)flag=1; else if (large=INF)flag=0; else if (large-xx)return 1; if (xx) large=min(large,T-x); return Find(T-l,x,small,large); else small=max(small,T-x); return Find(T-r,x,small,large); void _Delete(Node *&

34、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 -1 else if (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 1 else /here is x if (T-l&T-r)/left &right Node *t=T-l; while (t-r)t=t-r; T-x=t-x; _Delete(T-l,t-x); T-bf=BF(T-l,T-r); if (T-bfr-bf)T=RLrorate(T); else T=Lrorate(T);/bf=0 or -1 else /left | right Node *