ACM数据结构部分模版.docx

1、ACM数据结构部分模版数据结构：增加栈#pragma comment(linker,/STACK:1024000000,1024000000)二维树状数组#include#include#include#define maxn 130 using namespace std ;int xtmaxnmaxnmaxn ;int add , z , n ;int low( int x ) return x &(-x) ;/ 二维树状数组，第三维枚举void up( int x , int y ) int i , j ; for( i = x ; i = maxn ;i+= low(i) for( j

2、 = y ; j = maxn ; j+=low(j) xtzij += add ; if( xtzij 0 ;i -= low(i) ) for( int j = y ; j 0 ;j -= low(j) ) ans += xtzij ; return ans ;int main() int x , y , a ; int x1 , y1 , z1 , z2 ; int x2 , y2 , ans ; while( cin n ) memset( xt , 0 , sizeof(xt) ; while( scanf( %d , &a ) & a != 3 ) ans = 0 ; if( a

3、= 1 ) scanf( %d%d%d%d , &x , &y , &z , &add ) ; x+=2 ; y+=2 ; z+=2 ; up( x , y ) ; else if( a = 2) scanf( %d%d%d , &x1 , &y1 , &z1 ) ; scanf( %d%d%d , &x2 , &y2 , &z2 ) ;/ 树状数组必须大于0，而且是整数 x1+=2;x2+=2;y1+=2;y2+=2;z1+=2;z2+=2; for( z = z1 ; z = ql & qr = R ) addo += v ; sumo += v*(R-L+1) ; return ; in

4、t mid = (L+R)1 ; if( ql = mid ) update(L,mid,o mid ) update(mid+1,R,o1|1) ; sumo = sumo1+sumo= ql & qr = R ) v += sumo ; v += _add*(R-L+1) ; return ; int mid = (L+R)1 ; if( ql = mid ) find(L,mid,o mid ) find(mid+1,R,o=0 ) / 往下更新 setlc = setrc = seto ; seto = -1 ;/ 记得标记 void update( int o , int L ,in

5、t R ) int lc = o*2 , rc = o*2+1 ; if(x1 = R ) seto = v ; else push(o) ; /把之前没有更新的一起带下去更新 int mid = ( L + R )/2 ; if( x1 mid )update( rc , mid + 1 , R ) ; / 求居间不同数个数void find ( int o , int L , int R ) if ( seto != -1 ) if( seto 0 & !viseto ) viseto = 1; mun+; / 如果当前有标记则不再往下找 return; if ( L = R ) retu

6、rn; int mid = ( L + R ) 1 ; find ( o*2 , L , mid ); find ( o*2+1 , mid+1,R ); KMP：void get( ) int i , j = -1 ; f0 = -1 ; for( i = 1 ;i = 0 & pj+1 != pi ) j = fj ; if( pj+1 = pi) j+ ; fi = j ; void find() int i , j = -1; get() ; for( i = 0 ;i = 0 & pj+1 != Ti) j = fj ; if( pj+1 = Ti ) j+ ; if( j = m

7、- 1 ) mun+ ; j = -1 ; int main() while( scanf( %s , T ) != EOF ) if( T0 = # & strlen(T) = 1 ) break ; n = strlen(T) ; scanf( %s , p ) ; m = strlen(p) ; mun = 0 ; find() ; cout mun = c,也就是distt+1 = dists + c,/这是求最长路的形式,所以要求最长路 / 看形势void spfa( int Max , int Min ) int i , j , now ; int u , w ; memset(

8、vi , 0 , sizeof(vi) ) ; queueq ; for( i = Min ; i = Max ;i+ ) di = -INF ;/ 因为求最长路 dMin = 0 ; q.push( Min ) ; vi1 = Min ; while( !q.empty() now = q.front( ) ; q.pop( ) ; for( i = 0 ; i qenow.size() ; i+) pii a = qenowi ; u = a.first ; w = a.second ; if( du w + dnow ) du = w + dnow ; if(!viu) q.push(

9、u ) ; viu= 1 ; vinow = 0 ; int main() int i , j , n ,m ; int u , v , w , len, Max = MAX , Min ; while( scanf( %d , &n ) != EOF ) for( i = 0 ; i = Max ; i+) qei.clear() ; Max = 0 ;Min = INF ; for( i = 1 ; i Max ) Max = v + 1 ; if( u Min ) Min = u ; for( i = Min ; i Max ; i+) qei+1.push_back(pii( i ,

10、-1 ) ; qei.push_back( pii( i + 1 , 0 ) ) ; spfa( Max , Min ) ; cout dMax dMin endl ; printf( %dn ,dMax - dMin ) ; LCA 离线算法typedef pair pii ;vector mapM , queryM ;int faM , disM , ansM ;bool viM ;int n , m ; void in( ) int a , b ,c , i ; char qq ; cin m ; for( i = 0 ; i m ; for( i = 0; i m ;i+) scanf

11、( %d%d , &a , &b ) ; querya.push_back( pii ( b , i ) ) ;/ 这就是离线 queryb.push_back( pii( a , i ) ) ; memset( vi , 0 , sizeof(vi) ) ;int find( int x ) if( fax != x) fax = find( fax ) ; return fax ;void dfs( int u , int len ) fau = u ;/ 往下找防止找到最后父亲 disu = len ; viu = 1 ; int i , j ; for( i = 0 ; i mapu.

12、size() ; i+ ) int v = mapui.first ; int w = mapui.second ; if( ! viv ) dfs( v , len + w ) ; fav = u ; / 延后处理 for( i = 0 ; i n ) in( ) ; dfs( 1 , 0 ) ; for( int i = 0 ; i m ; i+) printf( %dn , ansi ) ; AC自动机struct trie int chmaxn4 , cnt ,endmaxn ,root ,failmaxn ; int newnode() memset(chcnt,-1,sizeof(

13、chcnt) ; endcnt = 0 ;failcnt+ = -1 ; return cnt-1 ; void init() cnt = 0 ; root = newnode(); void insert( char ss) int c , u = root , n = strlen(ss); for( int i = 0 ; i n ;i+ ) c = id(ssi); if(chuc = -1 ) chuc = newnode() ; u = chuc ; endu = 1 ; queueQ ; void getfail() int i , u = root ; failroot = r

14、oot ; for( i = 0 ; i 4 ;i+ ) if(chrooti = -1 ) chrooti = root ; else failchrooti = root ; Q.push(chrooti) ; while(!Q.empty() int pos = Q.front() ;Q.pop() ; if(endfailpos = 1 ) endpos=1; for( i = 0 ; i 4 ;i+ ) if(chposi = -1 ) chposi = chfailposi ; else failchposi = chfailposi ; Q.push(chposi) ; int

15、query( char s) int n = strlen(s) ,pos = root,ans = 0 , tmp ; for( int i = 0 ; i n ;i+ ) tmp = chpossi-a ; pos = tmp ; while( tmp != root ) ans += endtmp ; endtmp = 0 ; tmp = failtmp ; return ans ; node get() node ans ; n = cnt ; ans.Clear() ; for( int i = 0 ; i cnt ;i+ ) for( int j = 0 ; j 4 ;j+ ) i

16、f(endchij = 0 ) ans.matichij+ ; return ans ; int solve( char ss) int tmp , u , i , j ,pos ; int n = strlen(ss) ; for( i = 0 ; i = n ;i+ ) for( j = 0 ; j cnt ;j+ ) dpij = INF ; dp0root = 0 ; for( i = 0 ; i n ;i+ ) for( j = 0 ; j cnt ;j+ ) if(dpij INF ) for( u = 0 ; u 4 ;u+ ) pos = chju ; if(endpos =

17、1 ) continue ; if( u = id(ssi) tmp = dpij ; else tmp = dpij+1 ; dpi+1pos = min(dpi+1pos,tmp) ; pos = INF ; for( i = 0 ; i cnt ;i+ ) pos = min(pos,dpni) ; if(pos = INF) return -1 ; return pos; AC;int main() int i , m , nn ; LL ans ; char ss12 ; / freopen(in.txt,r,stdin) ; while( scanf(%d%d,&m,&nn) !=

18、 EOF ) AC.init() ; while(m-) scanf(%s,ss) ; AC.insert(ss) ; AC.getfail() ; node a = AC.get() ; init() ; a = pow(a,nn) ; ans = 0 ; for( i = 0 ; i n ;i+ ) ans = (ans+a.mat0i)%mod ; cout ans endl ; return 0 ;2-SATbool dfs( int x ) if(markx1) return 0 ; if( markx) return 1 ; markx = 1 ; smun+ = x ; for(

19、 int i = 0 ; i qex.size() ;i+ ) if( !dfs(qexi ) return 0 ; return 1 ;bool solve() int i , j ; for( i = 0 ; i 0 ) marks-mun = 0 ; if( !dfs(i+1) return 0 ; return 1; void Get_map( int x , int a , int y , int b ) x = (x1)+a ; y = (y1)+a ; qex1.push_back(y) ; qey1.push_back(x) ;bool find( int mid ) int

20、i , j , a , b ; for( i = 1 ; i = m ;i+ )for( a = 0 ; a 2 ; a+ ) for( j = i+1 ; j = m ;j+ )for( b = 0 ; b 2 ;b+ ) if( abs(mapia-mapjb) mid ) Get_map( i , a , j , b ) ; if( solve() return 0 ; return 1 ;int main() int i , Min ; int s , e ,Max , mid ; int L , R ; while( scanf(%d,&m) != EOF ) Max = 0 ;Mi

21、n = INF ; for( i = 1 ; i = m ;i+ ) scanf(%d%d , &s , &e ) ; mapi0 = s ; mapi1 = e ; Max = max( Max , e ) ; Min = min( Min , s ) ; R = ( Max - Min + 1 ) / m ;L = 0 ; while( L 1 ; if(find(mid) R = mid-1; else L = mid+1 ; printf( %dn ,mid ) ; for( i = 0 ; i = Max ; i+ ) qei.clear() ; 后缀数组#include#include#includeusing namespace std ;#define maxn 1010010int smaxn , tmaxn , t2maxn ;int cmaxn , samaxn ;void build_sa( int n ,int m ) int i , *x = t , *y = t2 , p ,j ;