acm競賽題知識點總結

1、滾動數(shù)組（轉）版權聲明：轉載時請以超鏈接形式標明文章原始出處和作者信息及本聲明利用在數(shù)組長度N很大的情況下能達到壓縮存儲的作用。一般還是用在DP題目中，因為DP題目是一個自下而上的擴展過程，我們常常用到是連續(xù)的解，而每次用到的只是解集中的最后幾個解，所以以滾動數(shù)組形式能大大減少內存開支。用法：#include<iostream>usingnamespacestd;intd3;intmain()d0=1;d1=1;for(inti=2;i<100;i+)di%3=d(i-1)%3+d(i-2%3;cout<<d99%3<<endl;/Fibonacci.

2、return0;inti,j,d2100;/比d100100省多了for(i=1;i<100;i+)for(j=0;j<100;j+)di%2j=d(i-1)%2j+di%2j-1;/DP.滾動數(shù)組舉個簡單的例子:inti,d100;d0=1;d1=1;for(i=2;i<100;i+)di=di-1+di-2;printf("%d",d99);上面這個循環(huán)di只需要解集中的前2個解di-1和di-2;為了節(jié)約空間用滾動數(shù)組的方法intd3;d0=1；d1=1;for(i=2;i<100;i+)di%3=d(i-1)%3+d(i-2)%3;print

3、f("%d",d99%3);注意上面的運算，我們只留了最近的3個解，數(shù)組好象在“滾動？一樣，所以叫滾動數(shù)組對于二維數(shù)組也可以用這種方法例如：inti,j,d100100;for(i=1;i<100;i+)for(j=0;j<100;j+)dij=di-1j+dij-1;上？的dij恢便賴于di-1j,dij-1;迥用滾動數(shù)組inti,j,d2100;for(i=1;i<100;i+)for(j=0;j<100;j+)di%2j=d(i-1)%2j+di%2j-1;滾動數(shù)組實際是一種節(jié)約空間的辦法，時間上沒什么優(yōu)勢，多用于DP中，舉個例子先：一個DR平

4、常如果需要1000X1000的空間，其實根據(jù)DP的特點，能以2X1000的空間解決問題，并且通過滾動，獲得和1000X1000一樣的效果。背包問題這是最基礎的背包問題，特點是：每種物品僅有一件，可以選擇放或不放。用子問題定義狀態(tài)：即fiv表示前i件物品恰放入一個容量為v的背包可以獲得的最大價值。則其狀態(tài)轉移方程便是：fiv=maxfi-1v,fi-1v-ci+wi這個方程非常重要，基本上所有跟背包相關的問題的方程都是由它衍生出來的。所以有必要將它詳細解釋一下：“將前i件物品放入容量為v的背包中”這個子問題，若只考慮第i件物品的策略（放或不放），那么就可以轉化為一個只牽扯前i-1件物品的問題。如

5、果不放第i件物品，那么問題就轉化為“前i-1件物品放入容量為v的背包中”，價值為fi-1v;如果放第i件物品，那么問題就轉化為“前i-1件物品放入剩下的容量為v-ci的背包中”，此時能獲得的最大價值就是fi-1v-ci再加上通過放入第i件物品獲得的價值wi。優(yōu)化空間復雜度以上方法的時間和空間復雜度均為O（VN）,其中時間復雜度應該已經(jīng)不能再優(yōu)化了，但空間復雜度卻可以優(yōu)化到Q先考慮上面講的基本思路如何實現(xiàn)，肯定是有一個主循環(huán)i=1.N,每次算出來二維數(shù)組fi0.V的所有值。那么，如果只用一個數(shù)組f0.V，能不能保證第i次循環(huán)結束后fv中表示的就是我們定義的狀態(tài)fiv呢？fiv是由fi-1v和fi

6、-1v-ci兩個子問題遞推而來，能否保證在推fiv時（也即在第i次主循環(huán)中推fv時）能夠得到fi-1v和fi-1v-ci的值呢？事實上，這要求在每次主循環(huán)中我們以v=V.0的順序推fv，這樣才能保證推fv時fv-ci保存的是狀態(tài)fi-1v-ci的值。偽代碼如下：fori=1.Nforv=V.0fv=maxfv,fv-ci+wi;其中的fv=maxfv,fv-ci一句恰就相當丁我們的轉移方程fiv=maxfi-1v,fi-1v-ci，因為現(xiàn)在的fv-ci就相當丁原來的fi-1v-ci。如果將v的循環(huán)順序從上面的逆序改成順序的話，那么則成了fiv由fiv-ci推知，與本題意不符，但它卻是另一個重要

7、的背包問題P02最簡捷的解決方案，故學習只用一維數(shù)組解01背包問題是十分必要的。AC自動機首先簡要介紹一下AC自動機：Aho-Corasickautomation，該算法在1975年產(chǎn)生于貝爾實驗室，是著名的多模匹配算法之一。一個常見的例子就是給出n個單詞，再給出一段包含m個字符的文章，讓你找出有多少個單詞在文章里出現(xiàn)過。要搞懂AC自動機，先得有模式樹（字典樹）Trie和KMP模式匹配算法的基礎知識。AC自動機算法分為3步：構造一棵Trie樹，構造失敗指針和模式匹配過程。如果你對KMP算法和了解的話，應該知道KMP算法中的next函數(shù)（shift函數(shù)或者fail函數(shù)）是干什么用的。KMP中我們

8、用兩個指針i和j分別表示，Ai-j+1.i與B1.j完全相等。也就是說，i是不斷增加的，隨著i的增加j相應地變化，且j滿足以Ai結尾的長度為j的字符串正好匹配B串的前j個字符，當Ai+1豐Bj+1,KMP的策略是調整j的位置（減小j值）使得Ai-j+1.i與B1.j保持匹配且新的Bj+1恰好與Ai+1匹配，而next函數(shù)恰恰記錄了這個j應該調整到的位置。同樣AC自動機的失敗指針具有同樣的功能，也就是說當我們的模式串在Tire上進行匹配時，如果與當前節(jié)點的關鍵字不能繼續(xù)匹配的時候，就應該去當前節(jié)點的失敗指針所指向的節(jié)點繼續(xù)進行匹配?？聪旅孢@個例子：給定5個單詞：saysheshrheher,然后

9、給定一個字符串yasherhs。問一共有多少單詞在這個字符串中出現(xiàn)過。我們先規(guī)定一下AC自動機所需要的一些數(shù)據(jù)結構，方便接下去的編程。1constintkind=26;2structnode3node*fail;/失敗指針4node*nextkind;/Tire每個節(jié)點的個子節(jié)點（最多個字母）5intcount;/是否為該單詞的取后一個甲點6node()/構造函數(shù)初始化7fail=NULL;8count=0;9memset(next,NULL,sizeof(next);1011*q500001;/隊列，方便用于bfs構造失敗指針12charkeyword51;/輸入的單詞13charstr10

10、00001;/模式串14inthead,tail;/隊列的頭尾指針有了這些數(shù)據(jù)結構之后，就可以開始編程了:首先，將這5個單詞構造成一棵Tire，如圖-1所示。1 voidinsert(char*str,node*root)(node*p=root;inti=0,index;while(stri)(index=stri-'a'if(p->nextindex=NULL)p->nextindex=newnode();p=p->nextindex;i+;p->count+;/在單詞的最后一個節(jié)點count+1,代表一個單詞在構造完這棵Tire之后，接下去的工作就

11、是構造下失敗指針。構造失敗指針的過程概括起來就一句話：設這個節(jié)點上的字母為C,沿著他父親的失敗指針走，直到走到一個節(jié)點，他的兒子中也有字母為C的節(jié)點。然后把當前節(jié)點的失敗指針指向那個字母也為C的兒子。如果一直走到了root都沒找到，那就把失敗指針指向root。具體操作起來只需要：先把root加入隊列(root的失敗指針指向自己或者NULL),這以后我們每處理一個點，就把它的所有兒子加入隊列，隊列為空。voidbuild_ac_automation(node*root)(inti;root->fail=NULL;qhead+=root;while(head!=tail)(node*temp

12、=qtail+;node*p=NULL;for(i=0;i<26;i+)(if(temp->nexti!=NULL)if(temp=root)temp->nexti->fail=root;elsep=temp->fail;while(p!=NULL)if(p->nexti!=NULL)temp->nexti->fail=p->nexti;break;p=p->fail;202122232425if(p=NULL)temp->nexti->fail=root;qhead+=temp->nexti;26從代碼觀察下構造失

13、敗指針的流程：對照圖-2來看，首先root的fail指針指向NULL,然后root入隊，進入循環(huán)。第1次循環(huán)的時候，我們需要處理2個節(jié)點：root->next'Va'節(jié)彌h)和root->next's'-'a'節(jié)點s)。把這2個節(jié)點的失敗指針指向root,并且先后進入隊列，失敗指針的指向對應圖-2中的(1),(2)兩條虛線；第2次進入循環(huán)后，從隊列中先彈出h,接下來p指向h節(jié)點的fail指針指向的節(jié)點，也就是root；進入第13行的循環(huán)后，p=p->fail也就是p=NULL，這時退出循環(huán)，并把節(jié)點e的fail指針指向root,

14、對應圖-2中的，然后節(jié)點e進入隊列；第3次循環(huán)時，彈出的第一個節(jié)點a的操作與上一步操作的節(jié)點e相同，把a的fail指針指向root,對應圖-2中的(4)，并入隊；第4次進入循環(huán)時，彈出節(jié)點h(圖中左邊那個)，這時操作略有不同。在程序運行到14行時，由于p->nexti!=NULL(root有h這個兒子節(jié)點，圖中右邊那個)，這樣便把左邊那個h節(jié)點的失敗指針指向右邊那個root的兒子節(jié)點h,對應圖-2中的(5)，然后h入隊。以此類推：在循環(huán)結束后，所有的失敗指針就是圖-2中的這種形式。當最后，我們便可以在AC自動機上查找模式串中出現(xiàn)過哪些單詞了。匹配過程分兩種情況：前字符匹配，表示從當前節(jié)點

15、沿著樹邊有一條路徑可以到達目標字符，此時只需沿該路徑走向下一個節(jié)點繼續(xù)匹配即可，目標字符串指針移向下個字符繼續(xù)匹配；(2)當前字符不匹配，則去當前節(jié)點失敗指針所指向的字符繼續(xù)匹配，匹配過程隨著指針指向root結束。重復這2個過程中的任意一個，直到模式串走到結尾為止。1 intquery(node*root)(inti=0,cnt=0,index,len=strlen(str);node*p=root;while(stri)(index=stri-'a'while(p->nextindex=NULL&&p!=root)p=p->fail;p=p->

16、;nextindex;p=(p=NULL)?root:p;node*temp=p;while(temp!=root&&temp->count!=-1)cnt+=temp->count;temp->count=-1;temp=temp->fail;i+;returncnt;對照圖-2，看一下模式匹配這個詳細的流程，其中模式串為yasherhs。對于i=0,1。Trie中沒有對應的路徑，故不做任何操作；i=2,3,4時，指針p走到左下節(jié)點e。因為節(jié)點e的count信息為1,所以cnt+1，并且講節(jié)點e的count值設置為-1,表示改單詞已經(jīng)出現(xiàn)過了，防止重復

17、計數(shù)，最后temp指向e節(jié)點的失敗指針所指向的節(jié)點繼續(xù)查找，以此類推，最后temp指向root,退出while循環(huán)，這個過程中count增加了2。表示找到了2個單詞she和he。當i=5時，程序進入第5行，p指向其失敗指針的節(jié)點，也就是右邊那個e節(jié)點，隨后在第6行指向r節(jié)點，r節(jié)點的count值為1，從而count+1，循環(huán)直到temp指向root為止。最后i=6,7時，找不到任何匹配，匹配過程結束。到此為止AC自動機算法的詳細過程已經(jīng)全部介紹結束，看一道例題：Wiskeyalsowantstobringthisfeaturetohisimageretrievalsystem.Everyima

18、gehavealongdescription,whenuserstypesomekeywordstofindtheimage,thesystemwillmatchthekeywordswithdescriptionofimageandshowtheimagewhichthemostkeywordsbematched.Tosimplifytheproblem,givingyouadescriptionofimage,andsomekeywords,youshouldtellmehowmanykeywordswillbematch.InputFirstlinewillcontainoneinteg

19、ermeanshowmanycaseswillfollowby.EachcasewillcontaintwointegersNmeansthenumberofkeywordsandNkeywordsfollow.(N<=10000)Eachkeywordwillonlycontainscharacters'a'-'z',andthelengthwillbenotlongerthan50.Thelastlineisthedescription,andthelengthwillbenotlongerthan1000000.OutputPrinthowmanyk

20、eywordsarecontainedinthedescription.SampleInput15shehesayshrheryasherhsSampleOutput1#include<iostream>2usingnamespacestd;34constintkind=26;5structnode6node*fail;/失敗指針7node*nextkind;/Tire每個節(jié)點的8intcount;/是否為該單詞的最后一9node()/構造函數(shù)初始化10fail=NULL;11count=0;12memset(next,NULL,sizeof(next);1314*q500001;

21、/隊列，方便用于15charkeyword51;/輸入的單詞16charstr1000001;/模式串17inthead,tail;/隊列的頭尾指針1819voidinsert(char*str,node*root)20node*p=root;21inti=0,index;22while(stri)23index=stri-'a'24if(p->nextindex=NULL)p->nextindex25p=p->nextindex;26i+;26個子節(jié)點(最多個節(jié)點bfs構造失敗指針new26個字母)node();28p->count+;29303132

22、333435363738394041424344454647484950515253545556575859606162voidbuild_ac_automation(node*root)inti;root->fail=NULL;qhead+=root;while(head!=tail)node*temp=qtail+;node*p=NULL;for(i=0;i<26;i+)if(temp->nexti!=NULL)if(temp=root)temp->nexti->fail=root;elsep=temp->fail;while(p!=NULL)if(p->nexti!=NULL)temp->nexti->fail=p->nexti;break;p=p->fail;if(p=NULL)temp->nexti->fail=root;qhead+=temp->nexti;intquery(node*root)inti=0,cnt=0,index,len=strlen(str);node*p=root;while(stri)index=stri-'a'while(p-&