0x10基本数据结构
0x11 棧
棧是一種后進先出的線性數(shù)據(jù)結(jié)構(gòu)
AcWing 41.包含min函數(shù)的棧
維護兩個棧，一個記錄棧的值，另一個單調(diào)棧，記錄下當(dāng)前的最小值即可
coding
AcWing 128. 編輯器
開兩個棧維護，類似對頂堆的操作，我們把他叫做對頂棧好了
令\(P\)為光標(biāo)位置，分別開兩個棧\(a,b\)
棧\(a\)存\(P\)之前的數(shù)，棧\(b存\)P$之后的數(shù)
\(sum\)是前綴和，\(f\)是前綴和的最大值
對于操作\(L\)，把\(x\)壓入棧\(a\)并更新\(sum\)和\(f\)
對于操作\(D\) ，棧\(a\)棧頂彈出
對于操作\(L\)，把棧頂\(a\)彈出并壓入棧\(b\)
對于操作\(R\)，把棧頂\(b\)彈出并壓入棧\(a\)同時更新\(sum\)和\(f\)
對于操作\(Q\)，返回\(f[x]\)
#include <bits/stdc++.h> using namespace std;const int N = 1e6 + 5 , INF = 0x7ffffff; int T , opt , a[N] , b[N] , sum[N] , f[N] , ta = 0 , tb = 0;inline int read( bool _ ) {register int x = 0 , f_ = 1;register char ch = getchar();if( _ ){while( ch < '0' || ch > '9' ){if( ch == '-' ) f_ = -1;ch = getchar();}while( ch >= '0' && ch <= '9'){x = ( x << 3 ) + ( x << 1 ) + ch - '0';ch = getchar();}return x * f_;}else{while( ch != 'L' && ch != 'R' && ch != 'I' && ch != 'D' && ch != 'Q' ) ch = getchar();return int(ch);} }inline void work_1() {a[ ++ ta ] = read(1);sum[ta] = sum[ ta - 1 ] + a[ta];f[ta] = max( sum[ta] , f[ ta - 1] );return ; }inline void work_2() {if( ta > 0 ) ta --;return ; }inline void work_3() {if( ta > 0 )b[ ++ tb] = a[ ta ] , ta --;return ; }inline void work_4() {if( !tb ) return ;a[ ++ ta ] = b[tb];tb --;sum[ta] = sum[ta - 1] + a[ta];f[ta] = max( sum[ta] , f[ ta - 1] );return ; }inline void work_5() {printf("%d\n",f[ read(1) ] );return ; }int main() {f[0] = -INF;T = read(1);while( T -- ){opt = read(0);if(opt == 'I' ) work_1();else if(opt == 'D' ) work_2();else if(opt == 'L' ) work_3();else if(opt == 'R' ) work_4();else work_5();}return 0; }AcWing 131. 直方圖中最大的矩形
畫圖手玩樣例就能發(fā)現(xiàn)規(guī)律
單調(diào)棧的經(jīng)典應(yīng)用，不過我比較懶，STL+O2直接水過去
#include <bits/stdc++.h> #pragma GCC optimize(2) #define LL long long using namespace std;const int N = 100005; int n , now , width ; LL res; struct node {int w , h; }_; stack< node > s;inline int read() {register int x = 0;register char ch = getchar();while( ch < '0' || ch > '9' ) ch = getchar();while( ch >= '0' && ch <= '9' ){x = ( x << 3 ) + ( x << 1 ) + ch - '0';ch = getchar();}return x; }inline node make( int x , int y ) {_.h = x , _.w = y;return _; }int main() {while( 1 ){n = read();if( !n ) return 0;res = 0;for( register int i = 1; i <= n ; i ++ ){now = read();if( s.empty() || now > s.top().h ) s.push( make( now , 1 ) );else{width = 0;while( !s.empty() && s.top().h > now ){width += s.top().w;res = max( res , (LL)width * s.top().h );s.pop();}s.push( make( now , width + 1 ) );}}width = 0;while( !s.empty() ){width += s.top().w;res = max( res , (LL)width * s.top().h );s.pop();}printf( "%lld\n" , res );}return 0; }0x12 隊列
隊列是一種“先進先出”的線性數(shù)據(jù)結(jié)構(gòu)，手寫隊列時可以用循環(huán)隊列來優(yōu)化空間
隊列還有一些變形體，優(yōu)先隊列，單調(diào)隊列，雙端隊列，這些在\(STL\)中都是有的，不過常數(shù)比較大普通隊列手寫即可
另外優(yōu)先隊列在pbds中也有
AcWing 132. 小組隊
這道題本身并不難，只是數(shù)據(jù)的處理比較惡心
首先開一個隊列為維護小組，再開\(n\)個隊列維護每個小組的成員
每次壓入一個元素，就把這個元素加入這個小組的隊列，如果這個小組的隊列是空的就把他加入總的隊列
每次彈出一個元素，就把總隊列隊頭的小組彈出一個，如果隊頭小組的隊列此時為空，就把隊頭小組從總隊列總彈出
這道題并不是十分的卡常數(shù)，不開\(O2\)貌似能過，
另外插隊不是好習(xí)慣，小心被打
#include <bits/stdc++.h> #pragma GCC optimize(2) using namespace std;const int N = 1e6 + 5 , M = 1005; int n , t , m , num , cub[N]; string opt; map< int , queue<int> > member; queue< int > team;inline int read() {register int x = 0;register char ch = getchar();while( ch < '0' || ch > '9' ) ch = getchar();while( ch >= '0' && ch <= '9' ){x = ( x << 1 ) + ( x << 3 ) + ch - '0';ch = getchar();}return x; }inline void push() {num = read();if( member[ cub[num] ].empty() ) team.push( cub[num] );member[ cub[num] ].push( num );return ; }inline void pop() {num = team.front();printf( "%d\n" , member[ num ].front() );member[ num ].pop();if( member[ num ].empty() ) team.pop(); }inline void work( int k ) {n = read();if( !n ) exit(0);printf( "Scenario #%d\n" , k );while( !team.empty() ){num = team.front();while( !member[ num ].empty() ) member[ num ].pop();team.pop();}memset( cub , 0 , sizeof(cub) );for( register int i = 1 ; i <= n ; i ++ ){t = read();while( t -- ) cub[ read() ] = i;}while( 1 ){cin >> opt;if( opt == "ENQUEUE" ) push();else if( opt == "DEQUEUE" ) pop();else break;}puts("");return ; }int main() {for( register int k = 1 ; 1 ; k ++ ) work(k);return 0; }AcWing 135. 最大子序和
單調(diào)隊列的基操
首先對于區(qū)間和的問題一般情況下都是轉(zhuǎn)發(fā)乘前綴和數(shù)組，做差即可
然后就是找左右端點的問題
令前綴和數(shù)組為\(s\)
已經(jīng)枚舉的右端點\(i\)和當(dāng)前的左端點\(j\)
此時再任意一個\(k\)如果滿足\(k<j<i\)且\(s[k]>s[j]\)，著\(k\)無論如何也不可能成為最有解，因為對于任意的\(i\)如果可以選\(j\)則\(j\)一定\(k\)更優(yōu)
所以我們發(fā)現(xiàn)需要維護一個單調(diào)遞增的序列，并且隨著\(i\)的有移，將會有部分的\(j\)不能使用
符合單調(diào)隊列的性質(zhì)所以用單調(diào)隊列來維護，隊列儲存的元素是前綴和數(shù)組的下標(biāo)，隊頭為\(l\)，隊尾為\(r\)
對于每次枚舉的\(i\)有以下幾個操作
0x13鏈表與鄰接表
數(shù)組是一種支持隨機訪問，但不支持在任意位置插入或刪除元素的數(shù)據(jù)結(jié)構(gòu)
鏈表支持在任意位置插入或刪除，但只能按順序訪問其中的元素
鏈表的正規(guī)形式一般是通過動態(tài)分配內(nèi)存、指針實現(xiàn)，為了避免內(nèi)存泄漏、方便調(diào)試使用數(shù)組模擬鏈表、下標(biāo)模擬指針也是常見的做法
指針版
struct Node {int value; // dataNode *prev, *next; // pointers }; Node *head, *tail;void initialize() { // create an empty listhead = new Node();tail = new Node();head->next = tail;tail->prev = head; }void insert(Node *p, int value) { // insert data after pq = new Node();q->value = value;p->next->prev = q; q->next = p->next;p->next = q; q->prev = p; }void remove(Node *p) { // remove pp->prev->next = p->next;p->next->prev = p->prev;delete p; }void recycle() { // release memorywhile (head != tail) {head = head->next;delete head->prev;}delete tail; }數(shù)組模擬
struct Node {int value;int prev, next; } node[SIZE]; int head, tail, tot;int initialize() {tot = 2;head = 1, tail = 2;node[head].next = tail;node[tail].prev = head; }int insert(int p, int value) {q = ++tot;node[q].value = value;node[node[p].next].prev = q;node[q].next = node[p].next;node[p].next = q; node[q].prev = p; }void remove(int p) {node[node[p].prev].next = node[p].next;node[node[p].next].prev = node[p].prev; }// 鄰接表：加入有向邊(x, y)，權(quán)值為z void add(int x, int y, int z) {ver[++tot] = y, edge[tot] = z; // 真實數(shù)據(jù)next[tot] = head[x], head[x] = tot; // 在表頭x處插入 }// 鄰接表：訪問從x出發(fā)的所有邊 for (int i = head[x]; i; i = next[i]) {int y = ver[i], z = edge[i];// 一條有向邊(x, y)，權(quán)值為z }AcWing 136. 鄰值查找
首先我們開一個pair記錄\(A_i\)和對應(yīng)的\(i\)
然后排序，并用一個鏈表維護這個序列，鏈表的值是每個數(shù)字排序后的位置
所以每個鏈表的前驅(qū)就是小于等于這個數(shù)中最大的，后繼就是大于等于這個數(shù)中最小的
然后我們倒著訪問從\(n\)開始，因為這樣不管是前驅(qū)還是后繼在原序列中的位置一定比當(dāng)前數(shù)在原序列中的位置跟靠前
做差比較、記錄結(jié)果
然后刪掉當(dāng)前這個數(shù)字，因為剩下的數(shù)字在原序列中都比他靠前，所以這個數(shù)字一定不會是其他數(shù)字的結(jié)果
#include <bits/stdc++.h> #define LL long long using namespace std;const int N = 1e5 + 5 , INF = 0x7f7f7f7f; int n , l[N] , r[N] , p[N]; pair< int ,int > a[N] , res[N];inline int read() {register int x = 0,f = 1;register char ch = getchar();while(ch < '0' || ch > '9'){if( ch == '-' ) f = -1;ch = getchar();}while( ch >= '0' && ch <= '9' ){x = ( x << 3 ) + ( x << 1 ) + ch - '0';ch = getchar();}return x * f; }int main() {n = read();for( register int i = 1 ; i <= n ; i ++ ){a[i].first = read();a[i].second = i;}sort( a + 1 , a + 1 + n );a[0].first = -INF , a[ n + 1 ].first = INF;for( register int i = 1 ; i <= n ; i ++ ) l[i] = i - 1 , r[i] = i + 1 , p[ a[i].second ] = i;for( register int i = n ; i > 1 ; i -- ){register int j = p[i] , L = l[j] , R = r[j] ;register LL l_val = abs( a[L].first - a[j].first ) , r_val = abs( a[R].first - a[j].first );if( l_val <= r_val ) res[i].first = l_val , res[i].second = a[L].second;else res[i].first = r_val , res[i].second = a[R].second;l[R] = L , r[L] = R;}for( register int i = 2 ; i <= n ; i ++ ) printf( "%d %d\n" , res[i].first , res[i].second );return 0; }0x14 Hash
Hash 表
Hash表 又稱散列表，一般有Hash函數(shù)與鏈表結(jié)構(gòu)共同構(gòu)成
Hash表主要包括兩個基本操作
常用的的Hash函數(shù)是\(H(x) = (x\mod \ p)+ 1\)
這樣顯然可以把所有的數(shù)分成\(p\)個，如果遇到?jīng)_突情況，用鏈表維護即可
AcWing 137. 雪花雪花雪花
設(shè)計Hash函數(shù)為\(H(a_1,a_2,\cdots,a_6) = (\sum^{6}_{i=1}a_i + \Pi^{6}_{i=1}a_i)\ mod\ p\),其中\(p\)是一個我們自己選擇的一個大質(zhì)數(shù)
然后我們依次把每個雪花插入Hash表中，在對應(yīng)的鏈表中查找是否已經(jīng)有相同的雪花
判斷是否有相同雪花的方式就是直接暴力枚舉就好
#include <bits/stdc++.h> using namespace std;const int N = 100010,p = 9991; int n ,head[N] , nxt[N] ,snow[N][6], tot;inline int H( int *a ) {int sum = 0 , mul = 1 ;for( register int i = 0 ; i < 6 ; i ++ ) sum = ( sum + a[i] ) % p , mul = ( ( long long )mul * a[i] ) % p;return ( sum + mul ) % p; }inline int read() {register int x = 0;register char ch = getchar();while( ch < '0' || ch > '9' ) ch = getchar();while( ch >= '0' && ch <= '9' ){x = ( x << 3 ) + ( x << 1 ) + ch - '0';ch = getchar();}return x; }inline bool equal( int *a, int *b) {for( register int i = 0 ; i < 6 ; i ++ ){for( register int j = 0 ; j < 6 ; j ++ ){bool eq = 1;for( register int k = 0 ; k < 6 && eq; k ++ ){if( a[ ( i + k ) % 6 ] != b[ ( j + k ) % 6 ] ) eq = 0; }if( eq ) return 1;eq = 1;for( register int k = 0 ; k < 6 && eq; k ++ ){if( a[ ( i + k ) % 6 ] != b[ ( j - k + 6 ) % 6 ] ) eq = 0;}if ( eq ) return 1;}}return 0; } inline bool insert( int *a ) {register int val = H( a );for( register int i = head[val] ; i ; i = nxt[i] ){if(equal(snow[i] , a ) ) return 1;}++ tot;memcpy( snow[tot] , a , 6 * sizeof( int ) );nxt[ tot ] = head[val];head[val] = tot;return 0; }int main() {n = read();int a[10];for( register int j = 1 ; j <= n ; j ++ ){for( register int i = 0 ; i < 6 ; i ++ ) a[i] = read();if( !insert( a ) ) continue;puts( "Twin snowflakes found." );exit(0); }puts( "No two snowflakes are alike." );return 0; }字符串Hash
下面介紹的字符串\(Hash\)函數(shù)把任意一個長度的支付串映射成一個非負整數(shù)，并且沖突的概率近乎為\(0\)
取一固定值\(P\)，把字符串看成是\(P\)進制數(shù)并且分配一個大于\(0\)的數(shù)值，代表每種字符。一般說，我們分配的數(shù)值都遠小于\(P\)。例如，對于小寫字母構(gòu)成的字符串，可以令\(a=1,b=2,\dots ,z = 26\)。取一固定值M,求出該P進制數(shù)對M取的余數(shù)，作為該字符的\(Hash\)值。
一般來說，我們?nèi)?span id="ze8trgl8bvbq" class="math inline">\(P=131\)或\(P=13331\)，此時\(Hash\)值產(chǎn)生的沖突概率極低，通常我們?nèi)?span id="ze8trgl8bvbq" class="math inline">\(M=2^{26}\)，即直接使用\(unsigned\ long\ long\)的自然溢出來代替低效率的取模運算。
但是在極端構(gòu)造的數(shù)據(jù)中取模會導(dǎo)致\(Hash\)沖突，所以可以采用鏈表來存下每個字符串，也可以通過多次\(Hash\)來解決
AcWing 140. 后綴數(shù)組
這道題是字符串Hash，首先把原字符串的前綴進行Hash
然后用一個數(shù)組來代表后綴，通過\(O(1)\)計算得到后綴的Hash
然后在比較時，我們通過二分，二分出兩個后綴的最大公共前綴，我們只需比較公共前綴的下一位就可以比較兩個后綴的字典序
#include <bits/stdc++.h> #define ULL unsigned long long #define H( l , r ) ( h[r] - h[ l - 1 ] * p[ r - l + 1 ] ) using namespace std;const int N = 300010 , base = 131; int n ,sa[N]; ULL h[N] , p[N]; char str[N];inline ULL get_max_common_prefix( int a , int b ) {int l = 0 , r = min( n - a + 1 , n - b + 1 );while( l < r ){int mid = l + r + 1 >> 1;if( H( a , a + mid - 1 ) != H( b , b + mid - 1 ) ) r = mid - 1;else l = mid;}return l; }inline bool cmp( int a , int b) {register int l = get_max_common_prefix( a , b );register int av = a + l > n ? INT_MIN : str[ a + l ];register int bv = b + l > n ? INT_MIN : str[ b + l ]; return av < bv; }int main() {scanf( "%s" , str + 1 );n = strlen( str + 1 );p[0] = 1 ;for( register int i = 1 ; i <= n ; i ++ ){p[i] = p[ i - 1 ] * base;h[i] = h[ i - 1 ] * base + str[i] - 'a' + 1 ;sa[i] = i;}sort( sa + 1 , sa + 1 + n , cmp );for( register int i = 1 ;i <= n ; i ++ ) printf("%d " , sa[i] - 1 );puts("");for( register int i = 1; i <= n ;i ++ ){if( i == 1 ) printf( "0 " );else printf( "%d " , get_max_common_prefix( sa[ i - 1 ] , sa[i] ) ); }puts("");return 0; }0x15 字符串
KMP模式匹配
\(KMP\)算法，又稱模式匹配算法，能夠在線性時間內(nèi)判定字符串\(A[1\dots N]\)是否是字符串\(B[1\dots M]\)的子串，并求出字符串\(A\)在字符串\(B\)中出現(xiàn)的位置
KMP算法分為兩步
對字符串A進行自我匹配，求出一個數(shù)組\(next\)，其中\(next[i]\)表示“\(A\)中以\(i\)結(jié)尾的非前綴子串”與“\(A\)的前綴”能夠匹配的最長長度，即：
\(next[i] = max\{ j \}\),其中\(j<i\)且\(A[i-j+1\dots i] = A[1\dots j]\)
特別地，當(dāng)不存在這樣的\(j\)時\(next[i] = 0\)
對于字符串\(A\)與\(B\)進行匹配，求出一個數(shù)組\(f\),其中\(f[i]\)表示“\(B\)中以\(i\)結(jié)尾的子串”與“\(A\)的前綴”能夠匹配的最長長度，即：
\(f[i] = max\{ j \}\),其中\(j\le i\)且\(B[i-j+1\dots i] = A[1\dots j]\)
\(KMP\)算法\(next\)數(shù)組的求法
next[1] = 0; for( register int i = 2 , j = 0 ; j <= n ; i ++ ) {while( j && a[i] != a[ j + 1 ] ) j = next[j];if( a[i] == a[ j + 1 ] ) j ++ ;next[i] = j; }\(KMP\)算法\(f\)數(shù)組的求法
for( register int i = 1 , j = 0 ; i <= m ; i ++ ) {while( j && ( j == n || b[i] != a[ j + 1 ] ) ) j = next[j];if( b[i] == a[ j + 1 ] ) j ++;f[i] = j;if( f[i] == n ) //此時就是A在B中間出現(xiàn)一次 }CF1029A
這道題實際上就是一道啊很簡單的\(KMP\)模板題，理解下\(KMP\)里\(next\)數(shù)組的作用就明白了
先輸出原序列，在把\(t[next[n]\cdots n]\)輸出\(k-1\)次就好
#include <bits/stdc++.h> using namespace std;const int N = 60; int n , k , nxt[N]; char t[N];int main() {cin >> n >> k;scanf( "%s" , t + 1 );nxt[1] = 0;for( register int i = 2 , j = 0 ;i <= n ; i ++ ){while( j && t[i] != t[ j + 1 ] ) j = nxt[j];if( t[i] == t[j + 1] ) j ++ ;nxt[i] = j ;} printf( "%s" , t + 1 );for( ; k > 1 ; k -- ) {for( register int i = nxt[n] + 1 ; i <= n ; i ++ ) printf( "%c" , t[i] );}puts("");return 0; }最小表示法
給定一個字符串\(S[1\dots n]\),如果我們不斷的把它的最后一個字符放到開頭，最終會得到\(n\)個字符串，稱這\(n\)個字符串是循環(huán)同構(gòu)的。這些字符串中字典序最小的一個稱為字符串\(S\)的最小表示法
算法流程
- 如果掃描了n個字符后仍然相等，說明s有更小的循環(huán)元（例如catcat有循環(huán)元cat）,并且該循環(huán)元以掃描完成，B[min(i,j)]即為最小表示，算法結(jié)束
- 如果在i+k與j+k處發(fā)現(xiàn)不想等：
- 若ss[i+k]>ss[j+k],令i=i+k+1。若此時i=j，再令i=i+1
- 若ss[i+k]<ss[j+k]，令j=j+k+1。若此時i=j，再令j=j+1
Luogu P1368
看題目，簡單分析就知道是落得最小表示法
#include <bits/stdc++.h> #define LL long long using namespace std;const int N = 300005 * 2 ; int n , ans; LL a[N];inline LL read() {register LL x = 0;register char ch = getchar();while( ch < '0' || ch > '9' ) ch = getchar();while( ch >= '0' && ch <= '9' ){x = ( x << 3 ) + ( x << 1 ) + ch - '0';ch = getchar();}return x; }inline void mini_notation() {register int i = 1 , j = 2 , k;while( i <= n && j <= n ){for( k = 0 ; k < n && a[ i + k ] == a[ j + k ] ; k ++ );if( k == n ) break;if( a[ i + k ] <= a[ j + k ] ){j += k + 1;if( i == j ) j ++;}else{i += k + 1;if( i == j ) i ++;}}ans = min( i , j ); }int main() {n = read();for( register int i = 1 ; i <= n ; i ++ ) a[ i + n ] = a[i] = read();mini_notation();for( register int i = ans , j = 1 ; j <= n ; i ++ , j ++ ) printf( "%lld " , a[i] );puts("");return 0;}0x16 Trie
Trie，又稱字典樹，是一種用于實現(xiàn)字符串快速檢索的多叉樹結(jié)構(gòu)。Trie的每個節(jié)點都擁有若干個字符指針，若在插入或檢索字符串時掃描到一個字符c,就沿著當(dāng)前節(jié)點的這個字符指針，走向該指針指向的節(jié)點。
Trie的節(jié)點可以使用一個結(jié)構(gòu)體進行儲存，如下代碼中，trans[i]表示這個節(jié)點邊上的之父為i的邊到達兒子節(jié)點的編號，若為0則表示沒有這個兒子節(jié)點
struct node {int trans[z];// z為字符集的大小bool bo;// 若bo = true 則表示這個頂點代表的字符串是集合中的元素 }tr[N];現(xiàn)在要對一個字符集的Trie插入一個字符串s
inline void insert(string s) {register int len = s.size(),u = 1;for(register int i = 0;i < len;i ++){if(!tr[u].trans[s[i] - 'a']) tr[u].trans[s[i] - 'a'] = ++ tot;//若不存在這條邊則要建立一個新的節(jié)點 tot為總的點數(shù) u = tr[u].trans[s[i] - 'a']; }tr[u].bo = 1; //在結(jié)尾表示它代表的字符串是集合中的一個元素 return ; }查詢一個字符串s是否在集合中某個串的前綴
inline bool search(string s) {register int len = s.size(),u = 1;for(register int i = 0;i < len; i ++){if(!tr[u].trans[s[i] - 'a']) return 0;u = tr[u].trans[s[i] - 'a'];}return 1; }查詢一個字符串s是否是集合中的一個元素
inline bool query(string s) {register int len = s.size(),u = 1;for(register int i = 0;i < len; i ++){if(!tr[u].trans[s[i] - 'a']) return 0;u = tr[u].trans[s[i] - 'a'];}return tr[u].bo; }AcWing 142. 前綴統(tǒng)計
構(gòu)建一顆\(tire\)樹在每個結(jié)點存一個\(cn\)t記錄以當(dāng)前節(jié)點為結(jié)尾的字符串有多少個
然后在遍歷\(tire\)樹將\(cnt\)求和即可
#include <bits/stdc++.h> #define I( x ) ( x - 'a' ) using namespace std;const int N = 1e6 + 5 , Z = 30; int n , m , tot = 1 , len , u , ans ; string s;struct node {int cnt , trans[Z]; }tr[N];inline void insert() {len = s.size() , u = 1;for( register int i = 0 ; i < len ; i ++ ){if( !tr[u].trans[ I( s[i] ) ] ) tr[u].trans[ I( s[i] ) ] = ++ tot;u = tr[u].trans[ I( s[i] ) ];}tr[u].cnt ++;return ; }inline int search() {len = s.size() , u = 1 ,ans = 0;for( register int i = 0 ; i < len ; i ++ ){if(!tr[u].trans[ I( s[i] ) ] ) return ans;u = tr[u].trans[ I( s[i] ) ];ans += tr[u].cnt;}return ans; }int main() {cin >> n >> m;for( register int i = 1 ; i <= n ; i ++ ) {cin >> s;insert();}for( register int i = 1 ; i <= m ; i ++ ){cin >> s;cout << search() << endl; }return 0; }\(01tire\)，把所有的數(shù)字轉(zhuǎn)化成二進制插入
然后我們枚舉一下每一個數(shù)字，然后去\(01tire\)中查找，查找每一位時，首先查找是否有和當(dāng)前位相反的，如果有就選擇
這樣查找完后，得到二進制數(shù)就是所有數(shù)字中和當(dāng)前數(shù)異或值最大的，對所有的最大值取\(max\)即可
觀察發(fā)現(xiàn)，我們可以一遍建樹，一邊查找，效果是一樣的
#include <bits/stdc++.h> using namespace std;const int N = 1e5 + 5; int n , a[N] , tot = 1 , res = -1;struct Trie {int to[2]; }t[ N * 32 ];inline int read() {register int x = 0;register char ch = getchar();while( ch < '0' || ch > '9' ) ch = getchar();while( ch >= '0' && ch <= '9' ){x = ( x << 1 ) + ( x << 3 ) + ch - '0';ch = getchar();}return x; }inline void insert( int x ) {register int u = 1 , s;for( register int i = 30 ; i >= 0 ; i -- ){s = x >> i & 1 ;if( !t[u].to[s] ) t[u].to[s] = ++ tot;u = t[u].to[s];} }inline int search( int x ) {register int u = 1 , ans = 0 , s;for( register int i = 30 ; i >= 0 ; i -- ){s = x >> i & 1;if( t[u].to[ s ^ 1 ] ) u = t[u].to[ s ^ 1 ] , ans |= 1 << i;else u = t[u].to[s];}return ans; }int main() {n = read();for( register int i = 1 ; i <= n ; i ++ ) a[i] = read() , insert( a[i] ) , res = max( res , search( a[i] ) );cout << res << endl;return 0; }0x17 二叉堆
二叉堆是一種支持插入、刪除、查詢最值的數(shù)據(jù)結(jié)構(gòu)。它其實是一顆滿足“堆性質(zhì)”的完全二叉樹
二叉樹的實現(xiàn)可以手寫，當(dāng)然我自己跟推薦使用STL，當(dāng)然pbds也可以
priority_queue
構(gòu)造
priority_queue< int > q;//大根堆 priority_queue< int , vector< int > , greater< int > > q;//小根堆注意priority_queue中儲存的元素類型必須定義“小于號”，較大的元素會被放在堆頂。內(nèi)置的int、string等類型已經(jīng)定義過“小于號”，若使用結(jié)構(gòu)體則必須重載運算符
由于priority_queue是按照從大到小排序所以重載運算符時也要反過來
struct node {int value ;friend bool operator < (node a , node b){return a.value > b.value;} };成員函數(shù)
q.top();\\訪問堆頂元素 q.empty();\\檢查是否為空 q.size();\\返回容納的元素數(shù) q.push();\\插入元素，并排序 q.pop();\\刪除棧頂元素懶惰刪除法
如果是手寫的堆是支持刪除任意一個元素，而\(STL\)卻不支持這種操作所以我們可以用懶惰刪除法
懶惰刪除法又稱延遲刪除法，是一種應(yīng)對策略。當(dāng)遇到刪除操作時，僅在優(yōu)先隊列之外做一些特殊的記錄，用于辨別是否堆中的元素被刪除。當(dāng)從堆頂取出元素時判斷是否已經(jīng)被刪除，若是，我們重新取一個最值。換言之，元素的“刪除”推遲到堆頂執(zhí)行
比如“堆優(yōu)化的\(Dijkstra\)算法”中當(dāng)某個元素首次被取出時就達到了最短路，當(dāng)我們再次取出這個元素時我們不會重新進行擴展，而是使用一個\(bool\)數(shù)組判斷“是否進行過擴展”，其本質(zhì)還是懶惰刪除法的應(yīng)用
AcWing 146. 序列
首先這道題目,我們可以先考慮\(m=2\)的這種特殊情況
我們發(fā)現(xiàn),當(dāng)\(A\)序列和\(B\)序列從小到大排序后,最小和肯定是\(A[1]+B[1]\),而次小和必然是\(min(A[2]+B[1],A[1]+B[2])\),也就是說當(dāng)我們確定好\(A[i][j]\)為\(K\)小和的話,那么第\(k+1\)小的和,必然是\(min(A[k+1]+B[k],A[k]+B[k+1])\),既然如此的話,我們還要注意一點,\(A[1]+B[2]\)和\(A[2]+B[1]\)都可以推導(dǎo)出\(A[2]+B[2]\),所以說我們要記得,如果說\(j+1\)了,那么i就不要\(+1\)了,避免出現(xiàn)重疊,導(dǎo)致答案錯誤.至于\(min\)函數(shù),可以使用小根堆來維護當(dāng)前最小值.
數(shù)學(xué)的歸納法,我們就可以從\(2\),推到\(N\)的情況,也就是先求出前兩個序列的值,然后推出前\(N\)小的和的序列,然后用這個退出來的序列,再和第三個序列求值,然后同理,再得出來的值與第四個序列進行同樣的操作
#include <bits/stdc++.h> using namespace std;const int N = 2010; int t , n , m , a[N] , b[N] , c[N] , tot;struct node {int i , j;bool f;friend bool operator < ( node x , node y ){return a[ x.i ] + b[ x.j ] > a[ y.i ] + b[ y.j ];}}cur , temp ;inline int read() {register int x = 0;register char ch = getchar();while( ch < '0' || ch > '9' ) ch = getchar();while( ch >= '0' && ch <= '9' ){x = ( x << 1 ) + ( x << 3) + ch - '0';ch = getchar();}return x; }inline node make_node( int i , int j , bool f ) {cur.i = i , cur.j = j , cur.f = f;return cur; }inline void work() {sort( b + 1 , b + 1 + m );priority_queue< node > q;tot = 0;q.push( make_node( 1 , 1 , 0 ) );for( register int i = 1 ; i <= m ; i ++){temp = q.top() , q.pop();c[i] = a[ temp.i ] + b[ temp.j ];q.push( make_node( temp.i , temp.j + 1 , 1 ) );if( !temp.f ) q.push( make_node( temp.i + 1 , temp.j , 0 ) );}memcpy( a , c , sizeof( a ) );return ; }int main() {t = read();while(t--){n = read() , m = read();for( register int i = 1 ; i <= m ; i ++ ) a[i] = read();sort( a + 1 , a + 1 + m ); for( register int i = 2 ; i <= n ; i ++ ){for( register int j = 1 ; j <= m ; j ++ ) b[j] = read();work();}for( register int i = 1 ; i <= m ; i ++ ) printf( "%d " , a[i] );puts(""); }return 0; }AcWing 147. 數(shù)據(jù)備份
Luogo P3620 數(shù)據(jù)備份
這是一道貪心+鏈表+堆的題
對于題面其實很好理解，就是有\(n\)個點，\(n-1\)條邊，從中選\(k\)個但是每個節(jié)點只能選一次，求邊權(quán)最小和
首先我們求\(k = 1\)時的情況，即所有邊中最小的一個
再看\(k=2\)的情況，首先我們選擇的所有中最小的一個即為\(i\)
呢么第二條選的不是\(i-1\)，或\(i+1\)則無影響
若第二條邊選的時\(i-1\)則\(i+1\)必選，也就是放棄\(i\)
因為如果選\(i-1\)，不選\(i+1\)選\(j\)的情況下，此時對\(i\)時沒有限制的則必有\(v[i]+v[k]\le v[i-1]+v[k]\)
如果\(k=3\)，舉下面這個例子
假設(shè)已經(jīng)選擇的\(2\)和\(4\)
此時我們要選擇\(1\)則必選\(3\)和\(5\)
如果不選\(3,5\)，選\(3,6\)的話
則必有\(1,4,6\)比\(1,3,6\)更優(yōu)
根據(jù)數(shù)學(xué)歸納法我們可以推出，如果我們已經(jīng)選擇一串連續(xù)的點構(gòu)成的邊，假如我們因為要選擇某一條邊來破壞某一條邊已經(jīng)被選擇的邊，呢么這些連續(xù)的點構(gòu)成的邊一定要全部都破壞不然不可能更優(yōu)
知道這個結(jié)論后在結(jié)合貪心的策略就可以解決這個問題
首先我們用一個堆來維護所以的邊首先取出一個邊\(i\)，把\(v[i]\)累加的答案中，并且在堆中加入條權(quán)值為\(v[i-1]+v[i+1]-v[i]\)，左端點為\(i-1\)的左端點，右端點為\(i+1\)的右端點的邊，并且刪除\(i-1\)和\(i+1\)這兩條邊
這樣當(dāng)我們選擇的到\(i-1\)或\(i+1\)時都會選擇到這條新加入邊，對位邊的信息我們用雙向鏈表來維護即可
對于堆的刪除操作可以使用懶惰標(biāo)記法，這里給出一個\(set\)解決的方法，并會在下一小節(jié)給出set的基本用法
#include <bits/stdc++.h> #define LL long long #define PLI pair< LL , int > using namespace std;const int N = 100010; int n , k , l[N] , r[N]; LL d[N] , res; set< PLI > s;inline int read() {register int x = 0;register char ch = getchar();while( ch < '0' || ch > '9' ) ch = getchar();while( ch >= '0' && ch <= '9' ){x = ( x << 3 ) + ( x << 1 ) + ch - '0';ch = getchar();}return x; }inline void delete_node( int p ) {r[ l[p] ] = r[p] , l[ r[p] ] = l[p]; }int main() {n = read() , k = read();for( register int i = 1 ; i <= n ; i ++ ) d[i] = read();for( register int i = n ; i > 0 ; i -- ) d[i] -= d[ i - 1 ];d[1] = d[ n + 1 ] = 1e15;for( register int i = 1 ; i <= n ; i ++ ){l[i] = i - 1;r[i] = i + 1;s.insert( { d[i] , i } );}while( k -- ){set< PLI >::iterator it = s.begin();register LL v = it -> first;register int p = it -> second , left = l[p] , right = r[p];s.erase(it) , s.erase( { d[left] , left } ) , s.erase( { d[right] , right } );delete_node(left) , delete_node(right);res += v;d[p] = d[left] + d[right] - d[p];s.insert( { d[p] , p } ) ;}cout << res << endl;return 0; }set
set< int > s;//構(gòu)造函數(shù),元素不可重復(fù) multiset<int>s;//構(gòu)造函數(shù)，元素可以重復(fù) s.size();//返回s中有多少元素 s.empty();//返回s是否為空 s.clear();//清空s s.begin();//返回指向s中第一個元素的迭代器 s.end();//返回指向s中最后一個元素下一個位置的迭代器 s.insert(x);//向s中插入一個元素x s.find(x);//返回s中指向x的迭代器，如果s中沒有x則返回s.end() s.erase(x);//刪除x s.count(x)//返回s中x元素的個數(shù)（這個只適用于multiset）Huffman 樹
考慮這樣一個問題：構(gòu)造一顆包含\(n\)個節(jié)點的\(k\)叉樹，其中第\(i\)個葉子節(jié)點的權(quán)值為\(w_i\)，要求最小化\(\sum w_i \times l_i\)其中\(l_i\)表示第\(i\)個葉子節(jié)點到根節(jié)點的距離
該問題被稱為Huffman樹（哈夫曼樹）
為了最小化\(\sum w_i \times l_i\)，應(yīng)該讓權(quán)值打的葉子節(jié)點的深度盡量的小。當(dāng)\(k=2\)時，我們很容易想到用下面這個貪心思路求\(Huffman\)樹
對于\(k>2\)的\(Huffman\)樹，正常的想法就是在上述算法上每次取出\(k\)的節(jié)點
但加入最后一次取不出\(k\)個時，也就是第一層未滿，此時從下方任意取出一個子樹接在根節(jié)點的下面都會更優(yōu)
所以我們要進行一些操作
我們插入一些額外的權(quán)值為\(0\)的葉子節(jié)點，滿足\((n-1)mod(k-1) = 0\)
這是在根據(jù)上述思路做即可，因為補\(0\)后只有最下面的一次是不滿的
AcWing 148. 合并果子
\(2\)叉\(Huffman\)樹模板題，直接做即可
#include <bits/stdc++.h> using namespace std;int n , ans , a , b; priority_queue< int , vector<int> , greater<int> > q; inline int read() {register int x = 0;register char ch = getchar();while( ch < '0' || ch > '9' ) ch = getchar();while( ch >= '0' && ch <= '9' ){x = ( x << 1 ) + ( x << 3 ) + ch - '0';ch = getchar();}return x; } int main() {n = read();for( register int i = 1 ; i <= n ; i ++ ) q.push( read() );while( q.size() > 1 ){a = q.top() , q.pop() , b = q.top() , q.pop();ans += a + b;q.push( a + b );}cout << ans << endl;return 0; }AcWing 149. 荷馬史詩
這道題目背景比多，有考閱讀的成分
簡化版的提議就是求\(Huffman\)樹，并且求出\(Huffman\)樹的深度
所以只需稍作更改即可
#include <bits/stdc++.h> using namespace std; typedef long long LL; typedef pair< LL, int> PLI;int n , m ; LL res; priority_queue< PLI , vector<PLI> , greater<PLI> > heap;inline LL read() {register LL x = 0 , f = 1;register char ch = getchar();while( ch < '0' || ch > '9' ){if( ch == '-' ) f = -1;ch = getchar();}while( ch >= '0' && ch <= '9' ){x = ( x << 3 ) + ( x << 1 ) + ch - '0';ch = getchar();}return x * f; }int main() {n = read() , m = read();for( register int i = 1 ; i <= n ; i ++ ) heap.push( { read() , 0 } );while( ( n - 1 ) % ( m - 1 ) ) heap.push( { 0ll , 0 } ) , n ++;while( heap.size() > 1 ){register LL sum = 0;register int depth = 0;for( register int i = 0 ; i < m ; i ++ ) sum += heap.top().first , depth = max( depth , heap.top().second ) , heap.pop();res += sum;heap.push( { sum , depth + 1 } );}cout << res << '\n' << heap.top().second << '\n';return 0; }轉(zhuǎn)載于:https://www.cnblogs.com/Mark-X/p/11257423.html
總結(jié)
以上是生活随笔為你收集整理的0x10基本数据结构的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 【自定义注解使用】增加service层方
- 下一篇： mybatis整合spring下的的各种