代码仓库培训资料(doc33页)

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. 【图论图论】 LC

2、A+ 最大生成树（ truck15. 【动态规划】背包 01 ，多重，完全矩阵模板#in clude<cstdio>#in clude<cstri ng>#in clude<iostream>usi ngn amespace stdtypedeflong long llcon stintp = 9973；con stintN =13 ;ll n ,mstructmatrix ll aN N;introw , col ;matrix():row (N), col ( N) memset (a, 0,sizeof(a);/?matrix(i ntx ,int y

3、 ): row (x), col ( y)memset(a, 0, sizeof ( a);ll*operator(int x ) return a x;matrixoperator* ( matrix x)matrix tmpJfor ( int i=0; i <= n + 1; i +)for (int j =0; j < =n + 1;j+)tmpi j = 0;for(int k =0; k<= n + 1; k+) voidtmpreturn tmpi j =( tmp i j +Jai k* x kj )% P;operator*=( matrix x)* thi

4、s=* this* x ;matrixoperatorA (ll x )matrix retJfor ( int i=0; i <= n + 1; i +) ret i i = 1;matrix tmp=* this ;for (; x; x>>= 1, tmp *= tmp ) if (x&1)ret *=tmp ; voidreturn retJpri nt()for ( int i=0; i <= n + 1; i +)for (int j =0; j < =n + 1; j +)printf( "%d " , a i j );p

5、uts("");高斯消元，判断有无解的#in clude<cstdio> #in clude<cmath>#in clude<cstri ng>#in clude<iostream>#in clude<vector>usingn amespacestd ;typedef long long LL con stdouble EPS =1e-6const int N =55 ;structmatrixint a N N;intmatrixmatrixrow , col ;():row ( N), col ( N) me

6、mset (a, 0, sizeof(int x , int y ):row(x), col (y)(a);memset(a, 0, sizeof(a);int * operator ()i =0;(int jvoidpri ntfor ( intforprintfintx ) return a x;i <row ; i +)=0; j <col ; j +)("%d ",a i j );puts ;("");int Gauss(matrix a,int m , int n )int x_cnt= 0;int col,k ;/col为列号,k

7、为行号for ( k = 0, col =0; k<m&&col<n;+ k, + col )intr = k ;/r 为第col列的一个1for(int i =ki <m;+i ) if (a i col )r =i ;if(! a r col) k -;con ti nue ;if(r != k) for(int i= col ; i <= n;+ i )swap(a ri , ak i );for(int i =k + 1; i <m+ i ) if ( a i col)/消元for (int j= col ; j<=n;+ j ) a

8、 i j A=ak j;(int i =k; i-1; forputs("");<m;+ i ) if ( a i n) return/返回自由元个数if高斯消元，求岀一组解的#in elude <iostream>#ineludealgorithm#in elude <estdio>#in elude <estri ng>#in elude <emath>usingn amespaee std ;constint N = 1010 ;eon stdouble EPS =1e-7int m , n;double a N

9、N, x N;int Gaussinteol=0, k =0; /eol为列号,k为行号for(；k<m&&col <n;+ 1k，+ eol )intr = k ;for(int i =k + 1; i<m+ i )if (fabs ( a i eol )> fabs ( a r eolif(fabs ( a r eol)< EPS) k-; eontinueif(r != k) for (inti =eol ; i <= n;+ i )swap(ak i ,ar i);for(int i =k + 1; i<m+ i ) / 消元i

10、f (fabs ( a i eol )> EPS)double t = a i eol / a k eol ;for (int j =eol ; j <= n; j +) a i j -=ai eol = C); for(inti =k ; i <m ;+i ) /无解if(fabs ( a i n)> EPS) return-1;if(k< n ) return n-k ; II自由元个数for(int i =n-1; i >= 0; i -)/ 回带求解double temp = a i n;for(int j =i +1; j<n; +j )te

11、mp-=x j * a i j ;xi=(temp / ai i);(int； /)r=ia km , i ntn )列全为0j * t；Man acher 算法#in clude<cstdio>#in clude<stri ng>#in clude<cstri ng>#in clude<iostream>#i nclude<algorithm>using n amespace std ;const int N =233333 ; 20W/在o(n)时间内算岀以每个点为中心的最大回文串长度 int Manacher ( string

12、st )int len =st . size ();int *p = new int len +1 ;memset ( p, 0, sizeof ( p);int mx =0, id =0;for ( inti =1; i <= len ; i +)if ( mx>i ) p i = min ( p 2* id - i , mx- i );else p i = 1;while (st i +p i = st i - p i ) p i +; if (i +p i > mx) mx=i +p i ; id =i ;int ma =0;for ( int i =1; i <

13、len ; i +) ma= max( ma, p i ); delete ( p);return ma - 1 ;int main ()/freope n(""fuck.i n","r",stdi n);char st N;while ( scanf ("%s" , st ) str ing st0="$#"for ( int i =0; st i != '0' i +)st0+=st i ; st0 +="#"printf("%dn", Mana

14、cher ( st0 );KMP字符串匹配#in clude<cstdio>#in clude<cstri ng>usingn amespacestd ;typedef long long ll con stint N =100007 ;constint P =1000000007char a N, b N;bool mat N;int next N;ll f N;void getNext ( int m)int i =0, j =- 1;next 0=- 1;while ( i <m)if (j =- 1|bi = bj )if ( b+i != b+ j )

15、next i = jelse n exti = next j ; else j = nextj ;voidKMP (int n , intm)memset ( mat , 0, sizeof ( mat);int i =0, j =0;getNext ( m);while ( i <n&&j <m)if (j =- 11| ai = bj ) i +, j +; else j =next j ;if (! i &&! j ) break ;if (j = m)mat i = 1;/prin tf("mat%dgetn",i);j=

16、next j ;线段树(ZKW大法)#in clude<cstdio> #in clude<cstri ng>#in clude<iostream>#i nclude<algorithm>using n amespace std ;con stint INF =0x3f3f3f3f;constint N =3000100 ;struct lin etree #define lc (t<<1)#define rc (t<<1A1)int mi N, M;inlinevoid build (int n )M = 1 ; whi

17、le ( M<n) M<<= 1 ; M -; memset ( mi , INF , sizeof ( mi );&mi i ); mi rc );for( int i =1 +M; i <=n + M i +) scanf ("%d",for( int t =M; t >= 1 ; t -) mi t = min ( mi lc ,void change (int t , int x )for ( mi t += M= x, t >>= 1; t ; t >>= 1)mi t = min ( mi lc ,

18、mi rc );int query ( int l , int r )int ans = INF ;for(l+= MM , r +=M+1; l a r a1; l >>= 1, r>>= 1)if( l &1) ans=min ( ans, mi l a 1 );if( r &1) ans=min ( ans, mi r a 1 );return ans ;T;int mai n ()int n , q, ord , x, y;for (; scanf ("%d"，& n);)T . build ( n);for ( sc

19、anf ("%d"，& q); q-;)scanf( "%d%d%d"，& ord，& x,& y);if (ord ) T. cha nge ( x, y);else printf ("%dn", T. query ( x, y);线段树（RMQ#in clude<cstdio>#in clude<cstri ng>#in clude<iostream>#i nclude<algorithm> usi ngn amespace stdcon stint

20、N =600100 ;int n ,ans , m, a N;structnodeintl , r ,id ;node() node(intx , int y , intz ) l =x;r =y; id=z;bN,c N;inlineboolcmp1 (node a,node b)returnainlineboolcmp2 ( node a,node b)returna .structlin etreeconstl <b.r < INF =0x3f3f3f3fl ;r;#defi ne lc (t<<1)#define rc (t<<1A1)#d

21、efi ne mid (lt+rt>>1) int l N, r N, ma N, inlinemi N,void build (int n )M ta N,tiN；M =1memsetmemsetwhile ( M<n) M«= 1 ; M -;(ma, 0 , sizeof(mi , INF , sizeof(ma);(mi );memsetmemsetforfor(ti(int(int(ta ,0 , sizeof,INF , sizeofi =1 +M; i <= M* 2+1 ; i +) l i t =M; t >= 1 ; t -) l t

22、 = l lc(ta );(ti );=,r i = rt=i - M ; r rc ; inlinevoidif(t >M)down ( int t ) return;/leaf nodemamatalcrclc=max( ma max( ma max (ta lcrclc,tatatat);t);t);tatarc=tmax (ta 0;rc,tat);mimitititit=min ( mi lc ,tit);=min ( mi rc ,tit);=min (ti lc ,tit);=min (ti rc ,tit);=INF ;lcrclcrcinlinevoid mai nta

23、in(int t )mat = max( ma Ic ,ma rc );mit = min ( mi Ic ,mi rc );inlinevoid tag ( int t,int x )mat = max( ma t , x);mit = min ( mi t , x);tat = max( ta t , x);tit = min (ti t , x);voidchange (int t , intL , i nt R , i nt x )if(L<= l t && r t <= R) tag (t , x); return ; /indow n(t);if(L&l

24、t;= mid ) change(lc , L, R, x);if(mid < R ) change(rc , L, R, x);maintan(t);voidquery ( int t )if(t >M) /leaf nodebt - M= c t - M=node ( mi t , ma t , t - M);return;dow n(t);query(lc );query(rc );maintan(t);T；线段树（区间加+赋值）#in clude<cstdio>#in clude<cstri ng>#in clude<iostream>

25、#i nclude<algorithm>usingn amespace std;constint N =260000 ;int n , m;structlin etree#define lc (t<<1)#define rc (t<<1A1)#define mid (lt+rt>>1)Set N;int l N, r N, M tag N, sum N, len N,inline void build (int n )M = 1 ; while ( M<n) M«= 1 ; M -; /get M memset( sum,0,si

26、zeof(sum);memset(tag ,0,sizeof(tag );memset( Set ,0,sizeof(Set );for ( int i =1 +M; i <=M* 2+1 ; i +) /leafif ( i <= n + M) scanf ("%d"，& sum i );li = r i :=i-M ;leni = 1;for(int t =M; t >=1;t-)/fatherssumt = sum lc+sum rc ;lt = l lc , rt=r rc ;lent = len lc+len rc ;inlinevoid

27、 down ( intt)if(t >M) Set t =tagt=:0; returnif ( Set t );/leaf nodesumlc = Set t * len lc ;sumrc = Set t * len rc ;Setlc = Set t;Setrc = Set t ;Sett = 0;taglc = tag rc = 0;if(tag t)sumlc += tag t * len lc ;sumrc += tag t * len rc ;taglc += tag t ;tagrc += tag t ;tagt = 0；inlinevoid _tag (int t ,

28、int x )sumt += x* len t ;tagt += x;inlinevoid _set (int t , int x )sumt = x* len t ;Sett = x;tagt= 0；void change(int t , int L , int R , int x)if(L<=l t&& r t <= R) _tag (t , x);returndow n(t)；if(L<= mid ) change (lc , L, R, x);if(mid < R ) change (rc , L, R, x);sumt = sum lc + s

29、um rc ;void set (int t , int L , int R , int x )if(L<=l t&& r t <= R) _set (t , x);returndow n(t);if(L<= mid ) set ( lc , L, R, x);if(mid < R ) set ( rc , L, R, x);sumt = sum lc + sum rc ;int query ( int t , intL , intR )if(L<= l t && r t <= R) return sumt;dow n(t);

30、intans = 0;if(L<= mid ) ans += query ( lc , L, R);if(mid < R ) ans += query ( rc , L, R);； inreturnansT;Splay-Tree #in clude<cstdio>#i nclude<algorithm> using n amespace std struct Node intkey;/sizeNode;*,*r ,* f;left,right,fatherclass SplayTree public :voidInit() rt= NULL ;voidZag

31、(Node*x) /left rotateNode* y = x-> f ; /y is the father of xy->r=x ->l ；if(x-> l ) x-> l -> f = y ; /if x has left childx->f=y-> fJif(y-> f)/y is not rootif(y=y -> f -> l ) y-> f -> l=x; /y if left childelse y-> f -> r =x; /y is right childy->f =x; x -

32、> l =y ；voidZig(Node*x) /right rotateNode* y = x-> f ; /y is the father of xy->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;voidSplay(Node * x)whihe(x->f)Nc)de*p=x-&g

33、t; f ;if(! p-> f )if(x= p-> l ) Zig ( x);elseZag ( x); elsef (x = p-> l )if(p= p-> f -> l ) Zig(p); Zig (x);else Zig ( x); Zag (x); elsex=p->rif ( 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

34、); return T ;else if ( x<T-> key ) T=T-> l ;else T =T-> r ;return T ;voidInsert(int x )Node*T=rt ,* fa =NULL;while (T)fa=T;if ( x<T-> key ) T=T-> l>else if ( x>T-> key ) T=T-> r ;elsereturn; /two the same keysT=(Node *) malloc ( sizeof(Node);T-> key =x;T-> l =T

35、-> r =NULL;T-> f =fa ;if(fa )if (fa -> key >x) fa -> l=T;else fa -> r =T;Splay(T);voidDelete (int x )Node*T=Find (x);if(NULL =T) return;/errorrt= Join ( T-> l , T-> r);Node* Max num ( Node * t )Node*T=t ;while( T-> r) T=T-> r;Splay(T)；return T ;Node * Minnum ( Node * t

36、)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 * t2 )if ( NULL =t1 ) returnt2 ;if ( NULL =t2 ) returnt1 ;Node* T=Maxnu

37、m (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 In order( Node * T)if ( NULL=T) return ;Inorder( T-> l );printf("%d->" , T-> key );Inorder( T-> r);void _Delete () Delete ( rt );void Delete

38、(Node *T)if(NULL=T) returnDelete(T-> l );Delete(T-> r);free(T);private :Node;* rt ; /rootAVL树codevs1285莯? ?/by cww97#in clude<cstdio>#in clude<iostream>#i nclude<algorithm>#defi ne INF Oxfffffff#defi ne BASE 1000000using n amespace std ;int ans =0;struct Node int x , bf , h;

39、/bf=balanee factor,h=height Node * l ,* r ;； class AVLTree public :voidInit () rt=NULL; intH ( Node*T)return(T=NULL)? 0: T-> h;intBF ( Node*l ,Node* r) /get balanee factorif (NULL=l && NULL=r) return 0;elseif(NULL = l )returnelseif(NULL = r )returnreturnl-> h - r -> h;-r -> h; l

40、-> h;Node * Lrorate ( Node * a) /left rorateNode * b;b=a-> r ;a->r =b-> lJb->l =a;a->h = max (H( a->l),H( a->r)+ 1b->h = max (H( b->l),H( b->r)+ 1a->bf =BF(a -> l ,a ->r);b->bf =BF(b-> l ,b->r);return bNode * Rrorate ( Node * a) /right rorateNode *

41、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 righta-> l = Lrorate( a-> l )

42、;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 ;voidInsert(int x ) _lnsert( rt , x);void_lnsert( Node *& T, int x )if(NULL=T)T=(Node *) malloc ( sizeof(Node);T-> x = x;T-> bf =0; T-> h =

43、1 ;T-> l =T-> r =NULL; ifreturn;(x < T -> x) _Insert(T-> l , x);elseif ( x > T -> x) _Insert(T-> r , x);elsereturn; /error :the same yT-> h = max ( H( T-> l ), H( T-> r)+ 1; maintainT-> bf =BF( T-> l , T-> r);if (T->bf> 1 II T->bf< -1)/not bala n

44、eedif(T-> bf >0&& T -> l-> bf> 0) T=Rrorate(T);elseif(T-> bf<0&& T ->r -> bf< 0) T=Lrorate(T);elseif(T-> bf>0&& T ->l -> bf< 0) T=LRrorate(T);elseif(T-> bf<0&& T ->r -> bf> 0) T=RLrorate(T);void GetPet (int x

45、 ) /get pet or person if ( NULL = rt ) return ; int small =0, large =INF ;pri ntf("x=%dn",x);int flag if ( FindJ(rt , x, small , large )printf("find %dn", x);_Delete(rt , x); elseif(small = 0) flag =1;elseif(large = INF ) flag =0;elseif(large - x<x- small ) flagelseflag=0;if (

46、!flag) /choose large_Delete(rt , small );ans=(ans +x- small )% BASE; else_Delete(rt , large );ans=(ans +large - x)% BASE;bool Findif(Node *T, int(NULL=T) returnx , int &small , int &large )0；ififlarge(x =T-> x) return (x<T-> x)= min (largeFind ( T->return else smallreturn= max( s

47、mallFind ( T->1；,T-> x);l , x, small , large,T-> x);r, x, small , large）；）；(Node *& T,int x )void Deleteif ( NULL=T) return(x < T -> x)(T-> l , x);bf =BF( T-> l , T-> r);(T-> bf <- 1)if ( 1 = T-> r -> bf ) T = RLrorate else T = Lrorate ( T); bf=O or -1ifDelete

48、->ify at left(T); else if (x > T -> x) y at right_Delete(T-> r , x);T->bf =BF( T-> l , T-> r);if(T-> bf >1)if(-1 =T-> l -> bf ) T=LRrorate ( T)elseT = Rrorate ( T); bf=O or 1 else/here is xif(T-> l &&T-> r) /left &&rightNode* t =T-> l ;while(

49、t -> r) t =t -> r ;T->x =t -> x ;_Delete(T-> l , t -> x);T->bf =BF( T-> l , T-> r);if(T-> bf <- 1)if ( 1 = T-> r -> bf ) T=RLrorate ielse T = Lrorate ( T); bf=O or -1 else/left | rightNode*t =T;if(T-> l ) T=T-> l ;elseif (T-> r) T=T-> r;else free ( T); T=NULL;if(T) free (t );Debug,you will not n eed it at this problemvoid show () In Order ( rt ); puts (&