ACM集訓(xùn)隊(duì)階段總結(jié)課件

浙江林學(xué)院

ACM集訓(xùn)隊(duì)階段總結(jié)WritebyZhuangli(zjfc3)

浙江林學(xué)院

ACM集訓(xùn)隊(duì)階段總結(jié)1圖論

Whatisthat?圖論

Whatisthat?2什么是圖論?圖論〔GraphTheory〕是數(shù)學(xué)的一個(gè)分支。它以圖為研究對(duì)象。圖論中的圖是由若干給定的點(diǎn)及連接兩點(diǎn)的線所構(gòu)成的圖形，這種圖形通常用來描述某些事物之間的某種特定關(guān)系，用點(diǎn)代表事物，用連接兩點(diǎn)的線表示相應(yīng)兩個(gè)事物間具有這種關(guān)系。圖論本身是應(yīng)用數(shù)學(xué)的一部份，因此，歷史上圖論曾經(jīng)被好多位數(shù)學(xué)家各自獨(dú)立地建立過。關(guān)于圖論的文字記載最早出現(xiàn)在歐拉1736年的論著中，他所考慮的原始問題有很強(qiáng)的實(shí)際背景。

什么是圖論?圖論〔GraphTheory〕是數(shù)學(xué)的一個(gè)分支3并查集及其拓展并查集是一種信息內(nèi)聚很強(qiáng)的數(shù)據(jù)結(jié)構(gòu)，它在判定圖的連通性以及等價(jià)類劃分的時(shí)空效率上有著不可替代的優(yōu)勢(shì)。但并查集的特殊應(yīng)用也應(yīng)該有所了解. 以下兩類是并查集在實(shí)際問題中的特殊拓展，希望大家能夠進(jìn)行快速掌握.1.集合計(jì)數(shù)問題2.二分圖識(shí)別并查集及其拓展并查集是一種信息內(nèi)聚很強(qiáng)的數(shù)據(jù)結(jié)構(gòu)，它在判定圖4集合計(jì)數(shù)問題HDU1856Moreisbetter題意： 若A與B認(rèn)識(shí)，B與C認(rèn)識(shí)，則A與C認(rèn)識(shí)，現(xiàn)給你一組人員的關(guān)系表，求在這樣的不同群組內(nèi)，擁有最多人數(shù)群組的人數(shù)。集合計(jì)數(shù)問題HDU1856Moreisbetter5集合計(jì)數(shù)問題有什么想法？并查后統(tǒng)計(jì)并查數(shù)組?不可行數(shù)據(jù)范圍10000000如果逐個(gè)統(tǒng)計(jì)必定TLE不能如此暴力….思路如何……想3分鐘集合計(jì)數(shù)問題有什么想法？6集合計(jì)數(shù)問題聯(lián)想到并查集的構(gòu)造原理構(gòu)造rank數(shù)組,在并操作中入手??！好,問題解決!!

集合計(jì)數(shù)問題7二分圖識(shí)別HDU1829ABugOfLife題意： 假定兩只飛蟲(Bug)關(guān)系表，如AB表示A仰慕B，問是否存在同性的飛蟲互相仰慕（也就是同性戀問題）.二分圖識(shí)別HDU1829ABugOfLife8二分圖識(shí)別難點(diǎn)：A與B的集合歸屬不定如何解決?思考?。。《謭D識(shí)別9二分圖識(shí)別非此即彼思想的運(yùn)用構(gòu)造數(shù)組opp，初始化為本身編號(hào)，若A與B有關(guān)，首先進(jìn)行find(A),find(B)的操作，若根相同，則說明A與B屬于同一集合，即同性戀，否則執(zhí)行下面的操作，如果A的opp等于本身，說明A的opp未初始化，使之等于B，否則將A的opp與B進(jìn)行Unition操作，類似的如果B的opp等于本身，說明B的opp未初始化，使之等于A，否則將B的opp與A進(jìn)行Unition操作二分圖識(shí)別10二分圖識(shí)別想想為什么？二分圖的性質(zhì)決定更深入的二分識(shí)別……(如統(tǒng)計(jì)最小單元集，如何進(jìn)行>_<課后思考!)二分圖識(shí)別11最短路徑問題在一個(gè)網(wǎng)絡(luò)圖中求解一點(diǎn)到另一點(diǎn)間最短距離及其路徑的算法稱之為最短路徑問題。1、單源正權(quán)最短路徑2、單源帶負(fù)權(quán)最短路徑3、多源最短路徑最短路徑問題在一個(gè)網(wǎng)絡(luò)圖中求解一點(diǎn)到另一點(diǎn)間最短距離及其路徑12單源正權(quán)最短路徑求解單源最短路徑的Dijkstra算法，狀態(tài)轉(zhuǎn)移與貪心準(zhǔn)則的完美結(jié)合。思想：動(dòng)態(tài)規(guī)劃策略：貪心(O(Ve))步驟：

1.構(gòu)造輔助數(shù)組Dis[],Vist[],Dis[i]表示從源點(diǎn)出發(fā)到達(dá)i點(diǎn)的最短距離,Vist[i]表示i點(diǎn)是否已被訪問，算法開始執(zhí)行時(shí)令所有Dis[i]=w(start,i)[不可達(dá)為MAX],Vist[start]=true.

2.每次得到Dis[]數(shù)組中最小且未被訪問過的點(diǎn)i，標(biāo)記Vist[i]=true,遍歷所有與i相關(guān)的邊，若得到Dis[i]+w(i,j)<Dis[j]，則更新Dis[j]=Dis[i]+w(i,j).

3.如此循環(huán)直到所有點(diǎn)均被標(biāo)記.單源正權(quán)最短路徑求解單源最短路徑的Dijkstra算法，狀態(tài)13單源正權(quán)最短路徑Dijkstra的致命弱點(diǎn)：不能處理帶負(fù)權(quán)的邊思考：Why?問題出自貪心策略??！若存在負(fù)權(quán)，則算法將不斷更新負(fù)權(quán)邊相關(guān)頂點(diǎn)的Dis值，從而導(dǎo)致答案錯(cuò)誤!單源正權(quán)最短路徑Dijkstra的致命弱點(diǎn)：不能處理帶負(fù)權(quán)的14單源帶負(fù)權(quán)最短路徑如何處理Dijkstra的遺留問題？擯棄貪心策略執(zhí)行松弛技術(shù)-----Bellman-ford算法單源帶負(fù)權(quán)最短路徑15單源帶負(fù)權(quán)最短路徑什么是松弛技術(shù)？日常生活中的例子~~（1+1猜想）松弛技術(shù)的本質(zhì)是首先給予一個(gè)物體很高的估價(jià)，在每次的迭代中對(duì)估價(jià)進(jìn)行修正，在有限次的迭代后使估價(jià)與實(shí)際值吻合的技術(shù)。單源帶負(fù)權(quán)最短路徑什么是松弛技術(shù)？16單源帶負(fù)權(quán)最短路徑思想：若存在N個(gè)點(diǎn)的網(wǎng)絡(luò)，則對(duì)于起點(diǎn)到終點(diǎn)最多經(jīng)過N-1條邊策略：有限迭代下的松弛技術(shù)單源帶負(fù)權(quán)最短路徑17單源帶負(fù)權(quán)最短路徑步驟：1、開辟輔助數(shù)組Dis[],記錄源點(diǎn)到點(diǎn)i的最小距離，初始時(shí)設(shè)所有Dis[]值為MAX，Dis[start]=0.2、進(jìn)行n-1次迭代，對(duì)于所有邊，若滿足Dis[i]<MAX&&Dis[i]+w(i,j)<Dis[j],更新Dis[j]=Dis[i]+w(i,j).3、執(zhí)行完成后，再執(zhí)行1次迭代，若出現(xiàn)Dis[i]+w(i,j)<Dis[j]的情況，則表明出現(xiàn)了負(fù)環(huán)，此時(shí)不存在最短路徑，否則Dis[end]即所求單源最短路徑.單源帶負(fù)權(quán)最短路徑步驟：18單源帶負(fù)權(quán)最短路徑算法分析：1、迭代v-1次，每次遍歷所有邊,復(fù)雜度O（VE）,E為全部邊，Dijkstra的復(fù)雜度O(Ve),e為部分邊…..效率差別很大!!2、如何優(yōu)化？思考??！單源帶負(fù)權(quán)最短路徑算法分析：19單源帶負(fù)權(quán)最短路徑優(yōu)化1：使用bool值Y標(biāo)記此次迭代是否進(jìn)行松弛，若沒進(jìn)行松弛表明已經(jīng)得到最短路徑，因此跳出循環(huán)。（常系數(shù)優(yōu)化）--YEN氏優(yōu)化優(yōu)化2：使用標(biāo)記數(shù)組以及隊(duì)列輔助，初始化時(shí)推入start點(diǎn)，標(biāo)記start在隊(duì)內(nèi)，每次執(zhí)行時(shí)，將隊(duì)首推出，標(biāo)記其不在隊(duì)內(nèi)，遍歷其鄰邊，進(jìn)行松弛操作，將所有不在隊(duì)內(nèi)且進(jìn)行過松弛操作的邊相關(guān)的點(diǎn)入隊(duì)直到隊(duì)列為空（即不再進(jìn)行松弛操作）--SPFA?。卧磶ж?fù)權(quán)最短路徑20單源帶負(fù)權(quán)最短路徑由優(yōu)化2得到的正是傳說中的SPFA，擁有神一般的效率O（KE），K一般取值3-5。算法如其名ShortestPathFastAlgorithm!瓶頸：如何判負(fù)環(huán)？思考?。。‘?dāng)一個(gè)點(diǎn)入隊(duì)次數(shù)超過邊的次數(shù)！需要輔助數(shù)組統(tǒng)計(jì)各點(diǎn)入隊(duì)次數(shù)，此時(shí)的空間與時(shí)間效率都極低！！因此此算法在稠密帶負(fù)環(huán)圖中的表現(xiàn)不如bellman-ford的YEN氏優(yōu)化?。≌?qǐng)大家慎重選擇使用。單源帶負(fù)權(quán)最短路徑由優(yōu)化2得到的正是傳說中的SPFA，擁有神21多源最短路徑當(dāng)題目要求大量的查詢工作時(shí)，需要一種算法能在多項(xiàng)式時(shí)間內(nèi)得到所有頂點(diǎn)間的最短距離并保存結(jié)果備查。Floyed算法應(yīng)運(yùn)而生!!多源最短路徑22多源最短路徑思想：傳遞關(guān)系閉包策略：動(dòng)態(tài)規(guī)劃O(V*V*V)步驟：1、對(duì)于點(diǎn)k，若存在w(i,k)+w(k,j)<w(i,j)，則更新w(i,j)=w(i,k)+w(k,j).2、迭代k直到結(jié)束多源最短路徑思想：傳遞關(guān)系閉包23多源最短路徑算法分析：1、不論正負(fù)權(quán)，大小通吃2、一次計(jì)算，次次查詢3、可擴(kuò)展性強(qiáng)?。P(guān)系傳遞，最長路徑）多源最短路徑算法分析：24圖的遍歷對(duì)于網(wǎng)絡(luò)圖G，如何不失一般性的搜索各結(jié)點(diǎn)—圖的遍歷.DFS(深度優(yōu)先)BFS(廣度優(yōu)先)--不再一一評(píng)述圖的遍歷對(duì)于網(wǎng)絡(luò)圖G，如何不失一般性的搜索各結(jié)點(diǎn)—圖的遍歷.25圖的表示鄰接陣：對(duì)于擁有稠密邊的圖是個(gè)很好表示方法隆重推出~_~鄰接表：在圖的邊數(shù)有限，點(diǎn)數(shù)過多時(shí)是一個(gè)很好的表示，主要的效率消耗在于結(jié)點(diǎn)的動(dòng)態(tài)生成,然而有一種方法……使得動(dòng)態(tài)的表達(dá)靜態(tài)化…效率神一樣的提高……圖的表示26靜態(tài)鄰接表ZJFC-1236環(huán)球旅行題意:~~中文題自己看!!!靜態(tài)鄰接表27靜態(tài)鄰接表演示Sample的代碼優(yōu)點(diǎn)1、使用輔助數(shù)組p[]，p[i]為p點(diǎn)鄰接的邊號(hào)，若為-1則表示無邊相關(guān)，否則可據(jù)此訪問邊數(shù)組，通過next值遍歷該點(diǎn)鄰接的所有邊優(yōu)點(diǎn)2、空間是邊相關(guān)的O（E），而不是鄰接陣的O（V*V），想想吧,V為10W對(duì)于鄰接陣的恐怖概念…優(yōu)點(diǎn)3、插入操作時(shí)，執(zhí)行三步曲，使表結(jié)構(gòu)成鏈狀，p[]數(shù)組得到更新，具有很高的技巧性，對(duì)于每次操作只需對(duì)p數(shù)組的初始化，而不需要對(duì)邊表進(jìn)行改動(dòng)，從動(dòng)態(tài)向靜態(tài)轉(zhuǎn)變！靜態(tài)鄰接表演示Sample的代碼28靜態(tài)鄰接表鄰接表下對(duì)Dijkstra的優(yōu)化上面講過其時(shí)間效率O（Ve）是基于鄰接表，而在鄰接陣中是O（V*V*V），使用靜態(tài)鄰接表本身就是場(chǎng)轟轟烈烈的優(yōu)化！使用優(yōu)先隊(duì)列（二叉堆）！由于使用到貪心策略，我們可以很好想象，優(yōu)化每次GetMin的操作，即將Dis數(shù)組撤消，轉(zhuǎn)換做優(yōu)先隊(duì)列，每次取與更新Dis值從原先的O（E+V）轉(zhuǎn)換為O（logV）,算法總效率提高到O（VlogV)靜態(tài)鄰接表29靜態(tài)鄰接表對(duì)于環(huán)球旅行題目的求解步驟1、使用map(紅黑樹)進(jìn)行鍵值關(guān)聯(lián)2、構(gòu)造靜態(tài)鄰接表3、二叉堆優(yōu)化下的Dijkstra求解靜態(tài)鄰接表30最小生成樹對(duì)于連通下的帶權(quán)網(wǎng)絡(luò)圖G，存在一個(gè)經(jīng)過所有點(diǎn)而不成回路的連通，使其權(quán)和為本網(wǎng)絡(luò)最小，稱為最小生成樹。應(yīng)用：最小代價(jià)網(wǎng)絡(luò)。方法1：Prim算法方法2：Kruskal算法最小生成樹對(duì)于連通下的帶權(quán)網(wǎng)絡(luò)圖G，存在一個(gè)經(jīng)過所有點(diǎn)而不成31Prim算法對(duì)Dijkstra算法的推廣，主算法幾乎一模一樣。思想：貪心步驟1：第一次首先選擇最小的邊，并標(biāo)記邊的2個(gè)端點(diǎn)步驟2：以后的每次操作都是在被標(biāo)記點(diǎn)為起點(diǎn)，未被標(biāo)記點(diǎn)為末點(diǎn)中取最小邊，執(zhí)行連接，并標(biāo)記末點(diǎn)，直到所有的點(diǎn)被標(biāo)記Prim算法對(duì)Dijkstra算法的推廣，主算法幾乎一模一樣32Prim算法復(fù)雜度為O（VE），想想還有什么更好優(yōu)化？對(duì)!貪心策略的優(yōu)化一般使用優(yōu)先隊(duì)列實(shí)現(xiàn)，使GetMin操作為O(logE)！于是整體復(fù)雜度為O（VlogE）效率大大提高Prim算法復(fù)雜度為O（VE），想想還有什么更好優(yōu)化？33Kruskal算法一種無視頂點(diǎn)的操作進(jìn)行該操作需要邊結(jié)構(gòu)與并查集思想：貪心優(yōu)先隊(duì)列優(yōu)化！步驟：1、得到邊序列推入優(yōu)先隊(duì)列2、每次得到一條邊，使用并查集判斷是否連通，若連通則執(zhí)行并操作。3、迭代直到執(zhí)行|V|-1次操作Kruskal算法一種無視頂點(diǎn)的操作34Kruskal算法算法分析1、點(diǎn)無關(guān)的操作，只需要邊結(jié)構(gòu)，適合多點(diǎn)圖,防止鄰接陣暴內(nèi)存。2、實(shí)現(xiàn)方便，代碼清晰。3、O（VlogE）復(fù)雜度，稀疏圖的良方！Kruskal算法算法分析35差分約束初步什么是差分約束？對(duì)于一組未知解[x1x2x3…xn-1xn]任意兩個(gè)不同解xi,xj存在xi-xj>=(或<=)C（常數(shù)）,以此為模型構(gòu)成的約束系統(tǒng)，稱之為差分約束系統(tǒng)。差分約束初步36差分約束初步首先我們回顧下松弛技術(shù)，在Bellman-Ford算法中，有一個(gè)十分關(guān)鍵的三角不等式Dis[i]+w(i,j)<Dis[j]使得迭代結(jié)束后所有的Dis[j]<=Dis[i]+w(i,j)??！再結(jié)合差分約束系統(tǒng)的概念，任意未知數(shù)間存在xi-xj>=（或<=）C，我們?nèi)?lt;=情況研究,則要求xi-xj<=C，即xi<=xj+C!!看出什么了么？對(duì)！這就是以j為始點(diǎn)，i為末點(diǎn)，C為權(quán)，構(gòu)造出帶約束邊的圖，并以此求得最短路徑的算法?。?shù)與圖得到了完美的結(jié)合??！差分約束初步首先我們回顧下松弛技術(shù)，在Bellman-For37最大流問題在帶源點(diǎn)與匯點(diǎn)的帶權(quán)連通網(wǎng)絡(luò)G中，求得自源點(diǎn)出發(fā)，受各邊容量限制最后到達(dá)匯點(diǎn)的流量的問題，稱之為最大流問題。最大流網(wǎng)絡(luò)滿足3大性質(zhì)：流守恒性網(wǎng)絡(luò)內(nèi)流不增加不減少容量限制流量受邊負(fù)載限制反對(duì)稱性任意結(jié)點(diǎn)流進(jìn)多少流出多少解決方案：FF方法最大流問題在帶源點(diǎn)與匯點(diǎn)的帶權(quán)連通網(wǎng)絡(luò)G中，求得自源點(diǎn)出發(fā)，38Ford-Fulkerson方法這是種方法而非算法，在此種方法指導(dǎo)下的算法最壞上界完全相同，但最好下界卻各有千秋。增廣路徑：在殘留網(wǎng)絡(luò)中，從源點(diǎn)出發(fā)，可以通過該路徑使得所經(jīng)邊殘余流量減少，而通向匯點(diǎn)的流量增大。最小割-最大流定理：網(wǎng)絡(luò)流中，存在的最大流受限制于該網(wǎng)絡(luò)的最小割。E-K算法，此算法是最常用的最大流算法，以BFS為基礎(chǔ)，每次選擇殘余網(wǎng)絡(luò)中的結(jié)點(diǎn)數(shù)最少的可增廣路徑進(jìn)行增廣，直到無法進(jìn)行下去，此算法的最大特點(diǎn)是最后一次保存的路徑是該網(wǎng)絡(luò)流的最小截集。Ford-Fulkerson方法這是種方法而非算法，在此種方39二分匹配對(duì)于圖G，可以將頂點(diǎn)重構(gòu)為兩個(gè)集合，每個(gè)集合內(nèi)的點(diǎn)不自交，則該圖稱之為二部圖，對(duì)其求解最大匹配的過程稱之為二分匹配。在普通二分匹配中，其最小路徑覆蓋為點(diǎn)數(shù)-最大匹配數(shù)。不帶權(quán)二分匹配（匈牙利算法）帶權(quán)二分匹配（KM算法）二分匹配對(duì)于圖G，可以將頂點(diǎn)重構(gòu)為兩個(gè)集合，每個(gè)集合內(nèi)的點(diǎn)不40匈牙利算法由匈牙利數(shù)學(xué)家提出的解決二分圖匹配的算法。本質(zhì)是找增廣路徑。這里的增廣路徑定義為交錯(cuò)軌，即一端為已匹配點(diǎn)，另一端為未匹配點(diǎn)，如果通過任意頂點(diǎn)的遍歷，能夠找到這樣的路徑，則對(duì)其取反,必會(huì)使匹配數(shù)+1，如此迭代直到無法找到這樣的路徑為止。對(duì)最大匹配的題目一般以最小路徑覆蓋的形式出現(xiàn)。匈牙利算法由匈牙利數(shù)學(xué)家提出的解決二分圖匹配的算法。41KM算法KM算法是通過給每個(gè)頂點(diǎn)一個(gè)標(biāo)號(hào)（叫做頂標(biāo)）來把求最大權(quán)匹配的問題轉(zhuǎn)化為求完備匹配的問題的。設(shè)頂點(diǎn)Xi的頂標(biāo)為A[i]，頂點(diǎn)Yi的頂標(biāo)為B[i]，頂點(diǎn)Xi與Yj之間的邊權(quán)為w[i,j]。在算法執(zhí)行過程中的任一時(shí)刻，對(duì)于任一條邊(i,j)，A[i]+B[j]>=w[i,j]始終成立。KM算法的正確性基于以下定理： 若由二分圖中所有滿足A[i]+B[j]=w[i,j]的邊(i,j)構(gòu)成的子圖（稱做相等子圖）有完備匹配，那么這個(gè)完備匹配就是二分圖的最大權(quán)匹配。 這個(gè)定理是顯然的。因?yàn)閷?duì)于二分圖的任意一個(gè)匹配，如果它包含于相等子圖，那么它的邊權(quán)和等于所有頂點(diǎn)的頂標(biāo)和；如果它有的邊不包含于相等子圖，那么它的邊權(quán)和小于所有頂點(diǎn)的頂標(biāo)和。所以相等子圖的完備匹配一定是二分圖的最大權(quán)匹配。算法的本質(zhì)是對(duì)匈牙利算法的改進(jìn)，但實(shí)際上卻比匈牙利算法早發(fā)表幾年，其核心仍然是尋找增廣路徑的過程。KM算法KM算法是通過給每個(gè)頂點(diǎn)一個(gè)標(biāo)號(hào)（叫做頂標(biāo)）來把求42KM算法步驟初始時(shí)為了使A[i]+B[j]>=w[i,j]恒成立，令A(yù)[i]為所有與頂點(diǎn)Xi關(guān)聯(lián)的邊的最大權(quán)，B[j]=0。如果當(dāng)前的相等子圖沒有完備匹配，就按下面的方法修改頂標(biāo)以使擴(kuò)大相等子圖，直到相等子圖具有完備匹配為止。我們求當(dāng)前相等子圖的完備匹配失敗了，是因?yàn)閷?duì)于某個(gè)X頂點(diǎn)，我們找不到一條從它出發(fā)的交錯(cuò)路。這時(shí)我們獲得了一棵交錯(cuò)樹，它的葉子結(jié)點(diǎn)全部是X頂點(diǎn)?，F(xiàn)在我們把交錯(cuò)樹中X頂點(diǎn)的頂標(biāo)全都減小某個(gè)值d，Y頂點(diǎn)的頂標(biāo)全都增加同一個(gè)值d，那么我們會(huì)發(fā)現(xiàn)：兩端都在交錯(cuò)樹中的邊(i,j)，A[i]+B[j]的值沒有變化。也就是說，它原來屬于相等子圖，現(xiàn)在仍屬于相等子圖。兩端都不在交錯(cuò)樹中的邊(i,j)，A[i]和B[j]都沒有變化。也就是說，它原來屬于（或不屬于）相等子圖，現(xiàn)在仍屬于（或不屬于）相等子圖。X端不在交錯(cuò)樹中，Y端在交錯(cuò)樹中的邊(i,j)，它的A[i]+B[j]的值有所增大。它原來不屬于相等子圖，現(xiàn)在仍不屬于相等子圖。X端在交錯(cuò)樹中，Y端不在交錯(cuò)樹中的邊(i,j)，它的A[i]+B[j]的值有所減小。也就說，它原來不屬于相等子圖，現(xiàn)在可能進(jìn)入了相等子圖，因而使相等子圖得到了擴(kuò)大?，F(xiàn)在的問題就是求d值了。為了使A[i]+B[j]>=w[i,j]始終成立，且至少有一條邊進(jìn)入相等子圖，d應(yīng)該等于min{A[i]+B[j]-w[i,j]|Xi在交錯(cuò)樹中，Yi不在交錯(cuò)樹中}。理解原理就行，在一般情況下KM算法的代碼不會(huì)調(diào)整，因此只要會(huì)使用模版，一切不在話下，當(dāng)然圖論本身就是充滿了建模的思想，只有好的模型才能有真正的效率！KM算法步驟43KM算法效率O（V*V*V）KM算法的本質(zhì)，對(duì)于N*N的矩陣每行每列只能取一個(gè)數(shù)，使其和為最大??！KM算法44強(qiáng)連通分支什么是強(qiáng)連通分支？強(qiáng)連通分支就是任意兩點(diǎn)均可達(dá)的有向子圖。理論：白色路徑定理求解：Tarjan算法強(qiáng)連通分支什么是強(qiáng)連通分支？45強(qiáng)連通分支什么是時(shí)間戳？DFS進(jìn)行時(shí)，訪問到節(jié)點(diǎn)所花的時(shí)間算法理論依據(jù)：DFS時(shí)，如果所達(dá)的下一個(gè)點(diǎn)i已經(jīng)被訪問，則從該點(diǎn)j出發(fā)，尋找父節(jié)點(diǎn)到i，其間所經(jīng)過的所有點(diǎn)必為以i為代表的強(qiáng)連通分支上的點(diǎn)(并查實(shí)現(xiàn))如何判斷是否是該次被訪問？時(shí)間戳！強(qiáng)連通分支什么是時(shí)間戳？46強(qiáng)連通分支步驟對(duì)于每個(gè)頂點(diǎn)，設(shè)立Num、Low、Used、Alive四個(gè)屬性，一個(gè)Stack保存當(dāng)前正在被遍歷的頂點(diǎn)；每訪問一個(gè)頂點(diǎn)，將它的Num和Low設(shè)立為當(dāng)前時(shí)間戳，Used、Alive設(shè)為True，并將頂點(diǎn)入棧；對(duì)于它的每條邊，若邊的終點(diǎn)未Used，則訪問，而后用終點(diǎn)的Low值更新它的Low值，對(duì)于每個(gè)Used且Alive的終點(diǎn)，用它的Num值更新當(dāng)前值；訪問完畢當(dāng)前頂點(diǎn)后，若Low與Num相等，說明找到了一個(gè)強(qiáng)連通分量，它包括棧中所有在當(dāng)前頂點(diǎn)上方的頂點(diǎn)，將它們出棧并記下Belong值，出棧的頂點(diǎn)的Alive要置為false。掃描各點(diǎn)Belong值，其代表的點(diǎn)的個(gè)數(shù)便為強(qiáng)連通分支數(shù)！強(qiáng)連通分支步驟47強(qiáng)連通分支應(yīng)用1、求解單純問題HDU12692、縮圖技術(shù)(適用于多點(diǎn)多邊的關(guān)系閉包求解)強(qiáng)連通分支應(yīng)用48待研究的問題次小生成樹最優(yōu)比例生成樹最小樹型圖弦圖穩(wěn)定婚姻問題待研究的問題49數(shù)論

It’seasytolearn!數(shù)論

It’seasytolearn!50數(shù)論什么是數(shù)論？數(shù)論是研究整數(shù)性質(zhì)的一門很古老的數(shù)學(xué)分支，其初等部分是以整數(shù)的整除性為中心的，包括整除性、不定方程、同余式、連分?jǐn)?shù)、素?cái)?shù)（即整數(shù)）分布以及數(shù)論函數(shù)等內(nèi)容，統(tǒng)稱初等數(shù)論（elementarynumbertheory）。初等數(shù)論的大部份內(nèi)容早在古希臘歐幾里德的《幾何原本》中就已出現(xiàn)。歐幾里得證明了素?cái)?shù)有無窮多個(gè)，他還給出求兩個(gè)自然數(shù)的最大公約數(shù)的方法，即所謂歐幾里得算法。我國古代在數(shù)論方面亦有杰出之貢獻(xiàn)，現(xiàn)在一般數(shù)論書中的「中國剩余定理」正是我國古代《孫子算經(jīng)》中的下卷第26題，我國稱之為「孫子定理」。近代初等數(shù)論的發(fā)展得益于費(fèi)馬、歐拉、拉格朗日、勒讓德和高斯等人的工作。1801年，高斯的《算術(shù)探究》是數(shù)論的劃時(shí)代杰作。高斯還提出：「數(shù)學(xué)是科學(xué)的皇后，數(shù)論是數(shù)學(xué)中的皇冠」。可見高斯對(duì)數(shù)論的高度評(píng)價(jià)。由于自20世紀(jì)以來引進(jìn)了抽象數(shù)學(xué)和高等分析的巧妙工具，數(shù)論得到進(jìn)一步的發(fā)展，從而開闊了新的研究領(lǐng)域，出現(xiàn)了代數(shù)數(shù)論、解析數(shù)論、幾何數(shù)論等新分支。而且近年來初等數(shù)論在計(jì)算器科學(xué)、組合數(shù)學(xué)、密碼學(xué)、代數(shù)編碼、計(jì)算方法等領(lǐng)域內(nèi)更得到了廣泛的應(yīng)用，無疑同時(shí)間促進(jìn)著數(shù)論的發(fā)展。數(shù)論什么是數(shù)論？51同余定理對(duì)于正整數(shù)a,b,c(a%c+b%c)%c=(a+b)%c(a*b)%c=(a%c*b%c)%c注意對(duì)于除法與減法%運(yùn)算為非封閉運(yùn)算需要進(jìn)行數(shù)論變換才能繼續(xù)進(jìn)行下去同余定理對(duì)于正整數(shù)a,b,c52同余定理大數(shù)求余設(shè)大數(shù)R=a1*10^0+a2*10^1+….+an*10^n-1則R%C=(a1*10^0%C+a2*10^1%C+….+an*10^n-1%C)%C可以在O（logn）時(shí)間內(nèi)解決大數(shù)求余問題步驟：以字符讀入大數(shù)后，設(shè)置計(jì)數(shù)器sum=0sum=(10*sum+key[i]-’0’)%C;迭代后令sum=sum%C;同余定理大數(shù)求余53GCDGCD（最大公約數(shù)）的一般求解歐幾里德輾轉(zhuǎn)相除法（必須掌握）If(a%b==0)returnb; Elsereturngcd(b,a%b); 本過程具有收斂性質(zhì)……GCDGCD（最大公約數(shù)）的一般求解54擴(kuò)展歐幾里德在一些具體的題目中，我們還需要的到一組滿足ax+by=gcd(a,b)的最小解，用以判斷模方程是否有解，此時(shí)就要使用擴(kuò)展歐幾里德.相比一般歐幾里德方法，擴(kuò)展歐幾里德有一個(gè)對(duì)于X，Y求解的遞推過程。使用遞歸實(shí)現(xiàn)，遞歸條件為b==0時(shí)，X=1,Y=0;否則t=X;X=Y;Y=t-(a/b)*X;(遞推求得)可以證明最后出來的X，Y必然是最小解.應(yīng)用：模線性方程的求解擴(kuò)展歐幾里德在一些具體的題目中，我們還需要的到一組滿足ax+55循環(huán)群生成元對(duì)于modn域中的任意數(shù)a，若有g(shù)cd(m,n)=1，則m為該域的生成元，使得a+km可以為域中任意數(shù).證明十分簡單，若gcd(m,n)=1，則lcm(m,n)=m*n,則對(duì)于a的modn運(yùn)算,需要n次的計(jì)算才能回到a，期間必遍歷該域中所有數(shù)！循環(huán)群生成元對(duì)于modn域中的任意數(shù)a，若有g(shù)cd(m,n56因子分解對(duì)于篩選大量數(shù)的因子分解工作，可以與篩選質(zhì)數(shù)同時(shí)進(jìn)行。令len[i]記錄數(shù)i的因子個(gè)數(shù)，則對(duì)于每個(gè)素?cái)?shù)p的倍數(shù)及本身，插入因子p，并使len值增長，篩選完所有素?cái)?shù)后就完成了因子分解因子分解對(duì)于篩選大量數(shù)的因子分解工作，可以與篩選質(zhì)數(shù)同時(shí)進(jìn)行57素?cái)?shù)判定對(duì)于一千萬內(nèi)素?cái)?shù)的判定：篩選法最優(yōu)對(duì)于一千萬外素?cái)?shù)的判定：米勒測(cè)試素?cái)?shù)判定對(duì)于一千萬內(nèi)素?cái)?shù)的判定：58篩選法給定輔助bool數(shù)組prime，首先全置true,使prime[0]=prime[1]=false;遍歷，當(dāng)遇到prime[i]=true,將之小于n的所有倍數(shù)置false；最后一次遍歷，所有值為true的數(shù)即為素?cái)?shù)！時(shí)空效率均攤相關(guān)偽線性復(fù)雜度篩選法給定輔助bool數(shù)組prime，首先全置true,使p59米勒測(cè)試?yán)碚摶A(chǔ)——費(fèi)馬定理實(shí)踐工具——二分求冪米勒測(cè)試60米勒測(cè)試費(fèi)馬定理：若p為素?cái)?shù)----a^(p-1)%p==1注意此定理只為充分不為必要米勒測(cè)試以概率的形式避免了誤判的發(fā)生從嚴(yán)格意義上來說米勒測(cè)試的意義并不科學(xué)但是實(shí)際證明在可數(shù)范圍內(nèi)的偽素?cái)?shù)十分之少而且同時(shí)滿足a=2,a=3,a=7的底的偽素?cái)?shù)更是少得可憐，因此該測(cè)試從概率上滿足了快速判定素?cái)?shù)的需求。米勒測(cè)試費(fèi)馬定理：61米勒測(cè)試二分快速求冪模原理對(duì)于res=a^b%c的求解若b%2==0則res=((a^(b/2))%c*(a^(b/2))%c)%c否則res=(a*((a^(b/2))%c*(a^(b/2))%c))%c米勒測(cè)試二分快速求冪模原理62歐拉函數(shù)設(shè)E(n)為n以內(nèi)（不包括n）與n互質(zhì)數(shù)的個(gè)數(shù)，則E(n)稱為關(guān)于n的歐拉函數(shù)。歐拉函數(shù)的求法，對(duì)于n=p1*p2*p3…pnE(n)=n*(1-1/p1)*(1-1/p2)…*(1-1/pn)可以以容斥原理證明其正確性！歐拉定理:a^(E(n))%n==1歐拉函數(shù)設(shè)E(n)為n以內(nèi)（不包括n）與n互質(zhì)數(shù)的個(gè)數(shù)，則E63模線性方程求解ax≡b(modn)有解，當(dāng)且僅當(dāng)b%gcd(a,n)==0使用擴(kuò)展歐幾里德求得d=gcd(a,n),則aX+nY=d,x=(X*(b/d))%nWhy?b/d=ma(X*m)+nY*m=b=>x=(X*m)%n模線性方程求解ax≡b(modn)有解，當(dāng)且僅當(dāng)b%gcd64中國剩余定理設(shè)n=n1*n2...nk,其中因子兩兩互質(zhì).有:a-----(a1,a2,...,ak),其中ai=amodni,則a和(a1,a2,...,ak),關(guān)系是一一對(duì)應(yīng)的.就是說可以由a求出(a1,a2,...,ak),也可以由(a1,a2,...,ak)求出a求解：中國古代演算法模線性方程代入中國剩余定理設(shè)n=n1*n2...nk,其中因子兩兩互質(zhì)65中國剩余定理應(yīng)用大整數(shù)表示快速運(yùn)算中國剩余定理應(yīng)用66連分?jǐn)?shù)逼近在數(shù)學(xué)中，連分?jǐn)?shù)或繁分?jǐn)?shù)即如上表達(dá)式.這里的a0是某個(gè)整數(shù)而所有其他的數(shù)an都是正整數(shù)?？梢罉佣x出更長的表達(dá)式。如果部分分子（partialnumerator）和部分分母（partialdenominator）允許假定任意的值，在某些上下文中可以包含函數(shù)，則最終的表達(dá)式是廣義連分?jǐn)?shù)。在需要把上述標(biāo)準(zhǔn)形式與廣義連分?jǐn)?shù)相區(qū)別的時(shí)候，可稱它為簡單或正規(guī)連分?jǐn)?shù)，或稱為是規(guī)范形式的一個(gè)數(shù)的連分?jǐn)?shù)表示是有限的，當(dāng)且僅當(dāng)這個(gè)數(shù)是有理數(shù)?！昂唵巍庇欣頂?shù)的連分?jǐn)?shù)表示是簡短的。任何有理數(shù)的連分?jǐn)?shù)表示是唯一的，如果它沒有尾隨的1。（但是[a0;a1,...an,1]=[a0;a1,...an+1]。）無理數(shù)的連分?jǐn)?shù)表示是唯一的。連分?jǐn)?shù)的項(xiàng)將會(huì)重復(fù)，當(dāng)且僅當(dāng)它是一個(gè)二次無理數(shù)（即整數(shù)系數(shù)的二次方程的實(shí)數(shù)解）的連分?jǐn)?shù)表示。數(shù)x的截?cái)噙B分?jǐn)?shù)表示很早產(chǎn)生x的在特定意義上“最佳可能”的有理數(shù)逼近。連分?jǐn)?shù)逼近在數(shù)學(xué)中，連分?jǐn)?shù)或繁分?jǐn)?shù)即如上表達(dá)式.67連分?jǐn)?shù)逼近意義1、精度保留2、避免浮點(diǎn)運(yùn)算3、無理數(shù)的表示唯一4、研究連分?jǐn)?shù)的動(dòng)機(jī)源于想要有實(shí)數(shù)在“數(shù)學(xué)上純粹”的表示。求解歐幾里德變體??！連分?jǐn)?shù)逼近意義68連分?jǐn)?shù)逼近

連分?jǐn)?shù)逼近69數(shù)據(jù)結(jié)構(gòu)

Soul!!!數(shù)據(jù)結(jié)構(gòu)

Soul!!!70數(shù)據(jù)結(jié)構(gòu)什么是數(shù)據(jù)結(jié)構(gòu)?數(shù)據(jù)結(jié)構(gòu)是計(jì)算機(jī)存儲(chǔ)、組織數(shù)據(jù)的方式。通常情況下，精心選擇的數(shù)據(jù)結(jié)構(gòu)可以帶來更高的運(yùn)行或者存儲(chǔ)效率的算法。數(shù)據(jù)結(jié)構(gòu)往往同高效的檢索算法和索引技術(shù)有關(guān)。數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)科學(xué)界至今沒有標(biāo)準(zhǔn)的定義。個(gè)人根據(jù)各自的理解而有不同的表述方法：SartajSahni在他的《數(shù)據(jù)結(jié)構(gòu)、算法與應(yīng)用》一書中稱：“數(shù)據(jù)結(jié)構(gòu)是數(shù)據(jù)對(duì)象，以及存在于該對(duì)象的實(shí)例和組成實(shí)例的數(shù)據(jù)元素之間的各種聯(lián)系。這些聯(lián)系可以通過定義相關(guān)的函數(shù)來給出?！彼麑?shù)據(jù)對(duì)象（dataobject）定義為“一個(gè)數(shù)據(jù)對(duì)象是實(shí)例或值的集合”。CliffordA.Shaffer在《數(shù)據(jù)結(jié)構(gòu)與算法分析》一書中的定義是：“數(shù)據(jù)結(jié)構(gòu)是ADT（抽象數(shù)據(jù)類型AbstractDataType）的物理實(shí)現(xiàn)?！盠obertL.Kruse在《數(shù)據(jù)結(jié)構(gòu)與程序設(shè)計(jì)》一書中，將一個(gè)數(shù)據(jù)結(jié)構(gòu)的設(shè)計(jì)過程分成抽象層、數(shù)據(jù)結(jié)構(gòu)層和實(shí)現(xiàn)層。其中，抽象層是指抽象數(shù)據(jù)類型層，它討論數(shù)據(jù)的邏輯結(jié)構(gòu)及其運(yùn)算，數(shù)據(jù)結(jié)構(gòu)層和實(shí)現(xiàn)層討論一個(gè)數(shù)據(jù)結(jié)構(gòu)的表示和在計(jì)算機(jī)內(nèi)的存儲(chǔ)細(xì)節(jié)以及運(yùn)算的實(shí)現(xiàn)。數(shù)據(jù)結(jié)構(gòu)什么是數(shù)據(jù)結(jié)構(gòu)?71數(shù)據(jù)結(jié)構(gòu)為什么要使用數(shù)據(jù)結(jié)構(gòu)?1、便于理清結(jié)構(gòu)，易于表示出一個(gè)實(shí)體的內(nèi)部屬性與外部聯(lián)系。2、更好利用實(shí)體特性，從而為算法高效鋪路。3、強(qiáng)有力的數(shù)據(jù)結(jié)構(gòu)，能夠取代算法的優(yōu)勢(shì)。數(shù)據(jù)結(jié)構(gòu)為什么要使用數(shù)據(jù)結(jié)構(gòu)?72數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)的基本類型：1、順序表2、鏈表3、廣義表4、樹5、圖6、串?dāng)?shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)的基本類型：73順序表順序表是在內(nèi)存上開辟的連續(xù)片段，每個(gè)元素單元擁有固定大小，以此組織形成的數(shù)據(jù)結(jié)構(gòu)。優(yōu)點(diǎn)：1、隨機(jī)存取2、索引唯一3、結(jié)構(gòu)簡單順序表順序表是在內(nèi)存上開辟的連續(xù)片段，每個(gè)元素單元擁有固定大74順序表一般應(yīng)用：1、寄存數(shù)組（包括棧和隊(duì)列）2、哈希數(shù)組3、樹狀數(shù)組順序表一般應(yīng)用：75寄存數(shù)組這是我們最常見的順序表表現(xiàn)方式，一般的大數(shù)據(jù)量程序，如果不能有邊讀邊處理的方法，就需要首先保留所有的輸入，從而能夠在而后的過程中進(jìn)行處理。主要應(yīng)用：1、各類算法的線性預(yù)處理2、保留線性邏輯關(guān)系3、記憶化輔助寄存數(shù)組這是我們最常見的順序表表現(xiàn)方式，一般的大數(shù)據(jù)量程序，76寄存數(shù)組優(yōu)點(diǎn)：1、靜態(tài)2、隨機(jī)3、高效缺點(diǎn)：1、插入與刪除操作效率極度低下2、內(nèi)存分配不靈活技巧：1、滿足遞推與DP內(nèi)存需求滾動(dòng)數(shù)組2、滿足圖的快速判重化行為數(shù)狀態(tài)壓縮寄存數(shù)組優(yōu)點(diǎn)：77哈希數(shù)組什么是哈希？從廣義上說哈希是一種鍵值對(duì)應(yīng)的操作，是從數(shù)域到值域的一一映射，也就是我們通常稱其為哈希函數(shù)的由來。為什么哈希表可以用數(shù)組實(shí)現(xiàn)？數(shù)組滿足哈希的3個(gè)必要條件：1、鍵——index2、值——value3、鍵值映射（index->value）O（1）哈希數(shù)組什么是哈希？78哈希數(shù)組散列函數(shù)的選用一般情況下我們使用哈希數(shù)組，采用的是開放散列策略，也就是說內(nèi)存與鍵是一一對(duì)應(yīng)，即hash[key]=value,在對(duì)于key值要求不大的情況下是很好的選擇。然而當(dāng)要求的key很大時(shí)該怎么辦，此時(shí)就應(yīng)該選用一個(gè)好的映射函數(shù)使hash[f(key)]=value，且f(key)的值必定均勻分布在映射區(qū)間內(nèi)。當(dāng)然要找到這樣的函數(shù)是十分困難的，我們無法了解到數(shù)據(jù)的具體信息，因此一般的f(key)為key%p，p為一個(gè)質(zhì)數(shù)，結(jié)合數(shù)論知識(shí)，我們可以知道當(dāng)gcd(key,p)=1時(shí)，key是一個(gè)循環(huán)群生成元，使用這個(gè)性質(zhì)，我們可以少了許多因大多數(shù)沖突而引發(fā)避免策略造成的效率問題。哈希數(shù)組散列函數(shù)的選用79哈希數(shù)組HDU2192題意：遞增的序列組成一個(gè)集合請(qǐng)問至少有幾個(gè)？思路？哈希數(shù)組HDU219280哈希數(shù)組出現(xiàn)次數(shù)最多的數(shù)，決定了能分成的最少群落！實(shí)現(xiàn)方式？？哈希?。?！散列函數(shù)——如何刻畫？思考！根據(jù)問題的輸入規(guī)模，最大10^4個(gè)數(shù)，因此選取大于10^4的質(zhì)數(shù)作為散列函數(shù)的參數(shù)，令f(key)=key%p還有什么問題？思考出現(xiàn)沖突！?。。」?shù)組出現(xiàn)次數(shù)最多的數(shù)，決定了能分成的最少群落！81哈希數(shù)組解決方案：1、線性掃描法2、二次線性掃描3、桶鏈問題完美解決，注意各個(gè)結(jié)點(diǎn)在不同解決方案下添加的相關(guān)變量。哈希數(shù)組解決方案：82樹狀數(shù)組首先我們得知道一個(gè)問題,那就是線段樹的作用并不只是用來存儲(chǔ)線段的,也可以存儲(chǔ)點(diǎn)的值等等.對(duì)于靜態(tài)的線段樹,空間上需要的數(shù)組有:當(dāng)前結(jié)點(diǎn)的數(shù)據(jù)值,左兒子編號(hào),右兒子編號(hào).至少這么三個(gè)數(shù)組.而在時(shí)間上雖然是NlogN的復(fù)雜度,但是系數(shù)很大.實(shí)現(xiàn)起來的時(shí)候編程復(fù)雜度大,空間復(fù)雜度大,時(shí)間效率也不是很理想.樹狀數(shù)組首先我們得知道一個(gè)問題,那就是線段樹的作用并不只是用83有!那就是樹狀數(shù)組!那么是否有更好的解決方法呢?有!那就是樹狀數(shù)組!那么是否有更好的解決方法呢?84樹狀數(shù)組先看一個(gè)例題:數(shù)列操作:給定一個(gè)初始值都為0的序列,動(dòng)態(tài)地修改一些位置上的數(shù)字,加上一個(gè)數(shù),減去一個(gè)數(shù),或者乘上一個(gè)數(shù),然后動(dòng)態(tài)地提出問題,問題的形式是求出一段數(shù)字的和.樹狀數(shù)組先看一個(gè)例題:85樹狀數(shù)組如果直接做的話,修改的復(fù)雜度是O(1),詢問的復(fù)雜度是O(N),M次詢問的復(fù)雜度是M*N.M,N的范圍可以有100000以上樹狀數(shù)組如果直接做的話,修改的復(fù)雜度是O(1),詢問的復(fù)雜度86用線段樹可以這樣解:若要維護(hù)的序列范圍是0..5,先構(gòu)造下面的一棵線段樹:用線段樹可以這樣解:若要維護(hù)的序列范圍是0..5,先構(gòu)造下面87樹狀數(shù)組可以看出,這棵樹的構(gòu)造用二分便可以實(shí)現(xiàn).復(fù)雜度是2*N.每個(gè)結(jié)點(diǎn)用數(shù)組a來表示該結(jié)點(diǎn)所表示范圍內(nèi)的數(shù)據(jù)之和.修改一個(gè)位置上數(shù)字的值,就是修改一個(gè)葉子結(jié)點(diǎn)的值,而當(dāng)程序由葉子結(jié)點(diǎn)返回根節(jié)點(diǎn)的同時(shí)順便修改掉路徑上的結(jié)點(diǎn)的a數(shù)組的值.對(duì)于詢問的回答,可以直接查找i..j范圍內(nèi)的值,遇到分叉時(shí)就兵分兩路,最后在合起來.也可以先找出0..i-1的值和0..j的值,兩個(gè)值減一減就行了.后者的實(shí)際操作次數(shù)比前者小一些.這樣修改與維護(hù)的復(fù)雜度是logN.詢問的復(fù)雜度也是logN,對(duì)于M次詢問,復(fù)雜度是MlogN.樹狀數(shù)組可以看出,這棵樹的構(gòu)造用二分便可以實(shí)現(xiàn).復(fù)雜度是2*88樹狀數(shù)組用樹狀數(shù)組!!!然而不難發(fā)現(xiàn),線段樹的編程復(fù)雜度大,空間復(fù)雜度大,時(shí)間效率也不高.怎么辦樹狀數(shù)組用樹狀數(shù)組!!!然而不難發(fā)現(xiàn),線段樹的編程復(fù)雜度大,89樹狀數(shù)組下圖中的C數(shù)組就是樹狀數(shù)組,a數(shù)組是原數(shù)組先自己研究一下這個(gè)東西

樹狀數(shù)組下圖中的C數(shù)組就是樹狀數(shù)組,a數(shù)組是原數(shù)組先自己研究90樹狀數(shù)組可以發(fā)現(xiàn)這些規(guī)律C1=a1C2=a1+a2C3=a3C4=a1+a2+a3+a4C5=a5……C8=a1+a2+a3+a4+a5+a6+a7+a8……C2^n=a1+a2+….+a2^n樹狀數(shù)組可以發(fā)現(xiàn)這些規(guī)律91樹狀數(shù)組對(duì)于序列a，我們?cè)O(shè)一個(gè)數(shù)組C定義C[i]=a[i–2^k+1]+…+a[i]，k為i在二進(jìn)制下末尾0的個(gè)數(shù)。K的計(jì)算可以這樣:2^k=xand(xxor(x-1))以6為例(6)10=(0110)2xor6-1=(5)10=(0101)2(0011)2and(6)10=(0110)2(0010)2樹狀數(shù)組對(duì)于序列a，我們?cè)O(shè)一個(gè)數(shù)組C定義C[i]=a[i92樹狀數(shù)組functionLowbit(x:Integer):Integer;beginLowbit:=xand(xxor(x–1));end;若要修改a[i]的值,則C數(shù)組的修改是:Procedurechange(k,delta:integer);Beginwhilek<=ndobeginC[k]:=C[k]+delta;k:=k+lowbit(k);End;End;樹狀數(shù)組functionLowbit(x:Integer93樹狀數(shù)組若要求I..j的元素和的值,則求出1..I-1的值和1..j的值.Functiongetsum(k:integer):integer;Vart:integer;Begint:=0;whilek>0dobegint:=t+c[k];k:=k-lowbit(k);end;getsum:=t;End;樹狀數(shù)組若要求I..j的元素和的值,則求出94樹狀數(shù)組對(duì)于剛才的一題,每次修改與詢問都是對(duì)C數(shù)組做處理.空間復(fù)雜度有3N降為N,時(shí)間效率也有所提高.編程復(fù)雜度更是降了不少.在很多的情況下,線段樹都可以用樹狀數(shù)組實(shí)現(xiàn).凡是能用樹狀數(shù)組的一定能用線段樹.當(dāng)題目不滿足減法原則的時(shí)候,就只能用線段樹,不能用樹狀數(shù)組.例如數(shù)列操作如果讓我們求出一段數(shù)字中最大或者最小的數(shù)字,就不能用樹狀數(shù)組了.樹狀數(shù)組對(duì)于剛才的一題,每次修改與詢問都是對(duì)C數(shù)組做處理.空95鏈表鏈表是內(nèi)存中不連續(xù)塊鏈接而成的數(shù)據(jù)結(jié)構(gòu)，本著使用多少分配多少的原則，極大地節(jié)約和利用了內(nèi)存，是一種十分基礎(chǔ)的數(shù)據(jù)結(jié)構(gòu)。優(yōu)勢(shì)：1、動(dòng)態(tài)分配2、快速刪除與插入3、節(jié)省空間鏈表鏈表是內(nèi)存中不連續(xù)塊鏈接而成的數(shù)據(jù)結(jié)構(gòu)，本著使用多少分配96鏈表缺點(diǎn)：1、查找效率低下2、動(dòng)態(tài)分配結(jié)點(diǎn)調(diào)用操作系統(tǒng)實(shí)現(xiàn)，導(dǎo)致空間分配效率消耗一種對(duì)空間的優(yōu)化：內(nèi)存靜態(tài)化??！一般應(yīng)用1、桶2、跳躍表鏈表缺點(diǎn)：97桶一般用做哈希的沖突避免策略，使用桶結(jié)構(gòu)存儲(chǔ)在同一沖突域下的數(shù)據(jù)，作為鍵值的擴(kuò)展?；鶖?shù)數(shù)排序的輔助結(jié)構(gòu)。桶一般用做哈希的沖突避免策略，使用桶結(jié)構(gòu)存儲(chǔ)在同一沖突域下的98跳躍表可以看做是鏈表結(jié)構(gòu)最優(yōu)秀的應(yīng)用，使用跳躍表有著令人震撼的效率，對(duì)查詢、刪除和添加的操作均為O（logn）的復(fù)雜度。利用了鏈表自身的特點(diǎn)，以較小的空間代價(jià)提升了自身的性能。使用了概率算法，使效率堪與AVL、RB-Tree等BST相媲美。相比而言，極低的編程復(fù)雜度?。?！有什么理由可以不去掌握呢？跳躍表可以看做是鏈表結(jié)構(gòu)最優(yōu)秀的應(yīng)用，使用跳躍表有著令人震撼99跳躍表跳躍表由多條鏈構(gòu)成（S0，S1，S2……，Sh），且滿足如下三個(gè)條件：每條鏈必須包含兩個(gè)特殊元素：+∞和-∞S0包含所有的元素，并且所有鏈中的元素按照升序排列。每條鏈中的元素集合必須包含于序數(shù)較小的鏈的元素集合，即：535353454537303030291511111111-∞-∞-∞-∞+∞+∞+∞+∞S0S1S2S3跳躍表的實(shí)例跳躍表跳躍表由多條鏈構(gòu)成（S0，S1，S2……，Sh），且100跳躍表之查找目的：在跳躍表中查找一個(gè)元素x 在跳躍表中查找一個(gè)元素x，按照如下幾個(gè)步驟進(jìn)行：從最上層的鏈（Sh）的開頭開始假設(shè)當(dāng)前位置為p，它向右指向的節(jié)點(diǎn)為q（p與q不一定相鄰），且q的值為y。將y與x作比較x=y 輸出查詢成功，輸出相關(guān)信息x>y 從p向右移動(dòng)到q的位置x<y 從p向下移動(dòng)一格如果當(dāng)前位置在最底層的鏈中（S0），且還要往下移動(dòng)的話，則輸出查詢失敗535353454537303030291511111111-∞-∞-∞-∞+∞+∞+∞+∞查詢?cè)?3的全過程S0S1S2S3查找成功！跳躍表之查找目的：在跳躍表中查找一個(gè)元素x5353101跳躍表之插入目的：在跳躍表中插入一個(gè)元素x插入操作由兩部分組成：查找插入的位置和插入對(duì)應(yīng)元素。為了確定插入的“列高”，我們引入一個(gè)隨機(jī)決策模塊：產(chǎn)生一個(gè)0到1的隨機(jī)數(shù)r r←random()如果r小于一個(gè)概率因子P，則執(zhí)行方案A， ifr<p thendoA否則，執(zhí)行方案B elsedoB列的初始高度為1。插入元素時(shí)，不停地執(zhí)行隨機(jī)決策模塊。如果要求執(zhí)行的是A操作，則將列的高度加1，并且繼續(xù)反復(fù)執(zhí)行隨機(jī)決策模塊。直到第i次，模塊要求執(zhí)行的是B操作，我們結(jié)束決策，并向跳躍表中插入一個(gè)高度為i的列。跳躍表之插入目的：在跳躍表中插入一個(gè)元素x列的初始高度為1102跳躍表之插入假設(shè)我們現(xiàn)在要插入一個(gè)元素40到已有的跳躍表中。373030302915-∞-∞-∞-∞S0S1S2S3插入的位置5353534545+∞+∞+∞+∞40404040高度+1隨機(jī)化模塊運(yùn)行狀況：高度=4高度+1高度+1結(jié)束53跳躍表之插入假設(shè)我們現(xiàn)在要插入一個(gè)元素40到已有的跳躍表中。103跳躍表之刪除 目的：從跳躍表中刪除一個(gè)元素x刪除操作分為以下三個(gè)步驟：在跳躍表中查找到這個(gè)元素的位置，如果未找到，則退出將該元素所在整列從表中刪除將多余的“空鏈”刪除 -∞-∞-∞-∞S0S1S2S3111111115353534545373030302915+∞+∞+∞+∞5353534545373030302915-∞-∞-∞+∞+∞+∞S0S1S2跳躍表之刪除 目的：從跳躍表中刪除一個(gè)元素x-∞-∞104跳躍表之概率因子影響在插入操作中，我們引入了一個(gè)概率因子P，它決定了跳躍表的高度，并影響到了整個(gè)數(shù)據(jù)結(jié)構(gòu)的效率。讓我們來看看在實(shí)際評(píng)測(cè)過程中，不同的P在時(shí)空效率上的差異。P平均操作時(shí)間平均列高總結(jié)點(diǎn)數(shù)每次查找跳躍次數(shù)（平均值）每次插入跳躍次數(shù)（平均值）每次刪除跳躍次數(shù)（平均值）2/30.0024690ms3.0049123339.87841.60441.5661/20.0020180ms1.9956068327.80729.94729.0721/e0.0019870ms1.5844757027.33228.23828.4521/40.0021720ms1.3304047828.72629.47229.6641/80.0026880ms1.1443442035.14735.82136.007跳躍表之概率因子影響在插入操作中，我們引入了一個(gè)概率因子P，105跳躍表高效率的相關(guān)操作和較低的編程復(fù)雜度使得跳躍表在實(shí)際應(yīng)用中的范圍十分廣泛。尤其在那些編程時(shí)間特別緊張的情況下，高性價(jià)比的跳躍表很可能會(huì)成為你的得力助手。在實(shí)際編程中，使用指針而非構(gòu)造多級(jí)鏈表以實(shí)現(xiàn)跳躍。跳躍表高效率的相關(guān)操作和較低的編程復(fù)雜度使得跳躍表在實(shí)際應(yīng)用106廣義表廣義表是對(duì)表概念的擴(kuò)充，使鏈表到樹之間的概念緩沖，其所有的表元素并非原子集合，在概念上是對(duì)自身的遞歸定義。實(shí)際應(yīng)用：Trie廣義表廣義表是對(duì)表概念的擴(kuò)充，使鏈表到樹之間的概念緩沖，其所107Trie什么是Trie?Trie是一種十分清晰的廣義表結(jié)構(gòu)，它存儲(chǔ)字母，并實(shí)現(xiàn)了前綴字母路徑唯一，因此被稱作前綴字典樹，或者字母樹。它是如何實(shí)現(xiàn)的呢？Trie什么是Trie?108Trie前綴共享每個(gè)結(jié)點(diǎn)分叉26條支路實(shí)現(xiàn)跳轉(zhuǎn)以標(biāo)記變量表示一個(gè)單詞的結(jié)束其中前綴共享是一個(gè)非常重要的性質(zhì)??！Trie前綴共享109TrieHDU1251題意：中文題！！自己理解!!思考？。。。TrieHDU1251110Trie根據(jù)題意，需要統(tǒng)計(jì)單詞前綴，此時(shí)，首先應(yīng)將所有字典單詞加入Trie。在加入的過程中，在各結(jié)點(diǎn)設(shè)置計(jì)數(shù)器，每個(gè)字母走過后，進(jìn)行計(jì)數(shù)累加。得到查詢串，在字典樹上走完后，返回計(jì)數(shù)器值。是不是很簡單？Trie根據(jù)題意，需要統(tǒng)計(jì)單詞前綴，此時(shí)，首先應(yīng)將所有字典單111樹樹的實(shí)質(zhì)就是對(duì)廣義表的約束，它只有一個(gè)入度為0的結(jié)點(diǎn)，作為一切遍歷的開始，這也是對(duì)非線性數(shù)據(jù)結(jié)構(gòu)的一種形象表示。優(yōu)點(diǎn)：1、快速查找2、快速刪除與插入3、內(nèi)存分配的靈活總結(jié)：可見樹是對(duì)鏈表與數(shù)組優(yōu)勢(shì)的互補(bǔ)，缺憾的折衷，可以說是一種優(yōu)秀的數(shù)據(jù)結(jié)構(gòu)。樹樹的實(shí)質(zhì)就是對(duì)廣義表的約束，它只有一個(gè)入度為0的結(jié)點(diǎn)，作為112樹樹結(jié)構(gòu)的一些應(yīng)用：1、二叉排序樹2、二叉平衡樹3、堆4、可并堆5、AC自動(dòng)機(jī)樹樹結(jié)構(gòu)的一些應(yīng)用：113二叉排序樹所謂二叉排序樹是這樣的一種結(jié)構(gòu)，對(duì)于它的每個(gè)結(jié)點(diǎn)，左兒子的值小于根的值，右兒子的值大于根值，對(duì)其進(jìn)行中序遍歷后，將得到一個(gè)遞增的數(shù)列。優(yōu)點(diǎn)：1、適用于快速查找2、實(shí)現(xiàn)簡單二叉排序樹所謂二叉排序樹是這樣的一種結(jié)構(gòu)，對(duì)于它的每個(gè)結(jié)點(diǎn)，114二叉排序樹缺點(diǎn)只有一個(gè)：樹的退化（致命的）怎么樣才算是一種退化？思考！以降序輸入數(shù)據(jù)后，得到的將是一張鏈表，查找效率退化為O(n)二叉排序樹缺點(diǎn)只有一個(gè)：115二叉排序樹如何解決？引入平衡概念！！BST從此誕生??！二叉排序樹116二叉平衡樹什么是二叉平衡樹？任意結(jié)點(diǎn)左子樹深度與右子樹深度之差的絕對(duì)值不大于1如何保持這一性質(zhì)？AVL：記錄深度，違反平衡必引起旋轉(zhuǎn)。RB-Tree:進(jìn)行染色，違反染色原則，進(jìn)行重染，不超過3次的旋轉(zhuǎn)染色。實(shí)際上STL都已經(jīng)封裝了這2個(gè)數(shù)據(jù)結(jié)構(gòu)AVL（BinarySearchTree），RB-Tree(SetorMap)!二叉平衡樹什么是二叉平衡樹？117堆以樹為概念，以樹型數(shù)組實(shí)現(xiàn)的數(shù)據(jù)結(jié)構(gòu)滿足對(duì)于任意結(jié)點(diǎn)，其值必然小于左兒子與右兒子的值理論證明，從堆中得到最小元素的復(fù)雜度是log(n),因此為n個(gè)序列進(jìn)行排序的復(fù)雜為nlog(n)。其構(gòu)造復(fù)雜度不超過O（4n），在小數(shù)據(jù)量下甚至超過了主算法，因此在數(shù)據(jù)較小情況下不考慮使用堆排序。STL的封裝priority_queue!!堆以樹為概念，以樹型數(shù)組實(shí)現(xiàn)的數(shù)據(jù)結(jié)構(gòu)118堆性質(zhì)對(duì)于堆來說，堆頂永遠(yuǎn)為堆中最小值。每次pop，將犧牲O(logn)的時(shí)間進(jìn)行調(diào)整每次push，將犧牲O(logn)的時(shí)間進(jìn)行調(diào)整致命缺陷：堆的歸并?。?！思考，為什么？2個(gè)大小為n的堆進(jìn)行歸并，必須逐個(gè)彈入，即O(nlogn)的復(fù)雜度，不可進(jìn)行快速歸并，否則將影響堆的平衡性！如何解決？堆性質(zhì)119可并堆為了解決堆間的合并問題，必須使用一個(gè)更好的數(shù)據(jù)結(jié)構(gòu)適應(yīng)這種頻繁的操作。目前有2種編程復(fù)雜度比較實(shí)際的應(yīng)用1、左偏樹2、斜堆可并堆為了解決堆間的合并問題，必須使用一個(gè)更好的數(shù)據(jù)結(jié)構(gòu)適應(yīng)120左偏樹一個(gè)左偏樹滿足如下性質(zhì)：1、左偏樹(LeftistTree)是一種可并堆(MergeableHeap)，它除了支持優(yōu)先隊(duì)列的三個(gè)基本操作（插入，刪除，取最小節(jié)點(diǎn)），還支持一個(gè)很特殊的操作——合并操作2、左偏樹是一棵堆有序(HeapOrdered)二叉樹。3、左偏樹滿足左偏性質(zhì)(LeftistProperty)。左偏樹一個(gè)左偏樹滿足如下性質(zhì)：121左偏樹的性質(zhì)定義一棵左偏樹中的外節(jié)點(diǎn)(ExternalNode)為左子樹或右子樹為空的節(jié)點(diǎn)。定義節(jié)點(diǎn)i的距離(dist(i))為節(jié)點(diǎn)i到它的后代中，最近的外節(jié)點(diǎn)所經(jīng)過的邊數(shù)。任意節(jié)點(diǎn)的左子節(jié)點(diǎn)的距離不小于右子節(jié)點(diǎn)的距離（左偏性質(zhì)）左偏樹滿足下面兩條基本性質(zhì)：[性質(zhì)1]節(jié)點(diǎn)的鍵值小于或等于它的左右子節(jié)點(diǎn)的鍵值。即key(i)≤key(parent(i))這條性質(zhì)又叫堆性質(zhì)。符合該性質(zhì)的樹是堆有序的(Heap-Ordered)。有了性質(zhì)1，我們可以知道左偏樹的根節(jié)點(diǎn)是整棵樹的最小節(jié)點(diǎn)，于是我們可以在O(1)的時(shí)間內(nèi)完成取最小節(jié)點(diǎn)操作。[性質(zhì)2]節(jié)點(diǎn)的左子節(jié)點(diǎn)的距離不小于右子節(jié)點(diǎn)的距離。即dist(left(i))≥dist(right(i))這條性質(zhì)稱為左偏性質(zhì)。性質(zhì)2是為了使我們可以以更小的代價(jià)在優(yōu)先隊(duì)列的其它兩個(gè)基本操作（插入節(jié)點(diǎn)、刪除最小節(jié)點(diǎn)）進(jìn)行后維持堆性質(zhì)。。由左偏性質(zhì)可知，一個(gè)節(jié)點(diǎn)的距離等于以該節(jié)點(diǎn)為根的子樹最右路徑的長度。定理：若一棵左偏樹有N個(gè)節(jié)點(diǎn)，則該左偏樹的距離不超過

log(N+1)

-1。左偏樹的性質(zhì)定義一棵左偏樹中的外節(jié)點(diǎn)(ExternalNo122左偏樹C←Merge(A,B)Merge()把A,B兩棵左偏樹合并，返回一棵新的左偏樹C，包含A和B中的所有元素。在本文中，一棵左偏樹用它的根節(jié)點(diǎn)的指針表示。在合并操作中，最簡單的情況是其中一棵樹為空（也就是，該樹根節(jié)點(diǎn)指針為NULL）。這時(shí)我們只須要返回另一棵樹。若A和B都非空，我們假設(shè)A的根節(jié)點(diǎn)小于等于B的根節(jié)點(diǎn)（否則交換A,B），把A的根節(jié)點(diǎn)作為新樹C的根節(jié)點(diǎn)，剩下的事就是合并A的右子樹right(A)和B了。right(A)←Merge(right(A),B)合并了right(A)和B之后，right(A)的距離可能會(huì)變大，當(dāng)right(A)的距離大于left(A)的距離時(shí)，左偏樹的性質(zhì)2會(huì)被破壞。在這種情況下，我們只須要交換left(A)和right(A)。若dist(left(A))>dist(right(A))，交換left(A)和right(A)

最后，由于right(A)的距離可能發(fā)生改變，我們必須更新A的距離：dist(A)←dist(right(A))+1不難驗(yàn)證，經(jīng)這樣合并后的樹C符合性質(zhì)1和性質(zhì)2，因此是一棵左偏樹。至此左偏樹的合并就完成了。左偏樹C←Merge(A,B)123左偏樹合并操作都是一直沿著兩棵左偏樹的最右路徑進(jìn)行的。一棵N個(gè)節(jié)點(diǎn)的左偏樹，最右路徑上最多有

log(N+1)

個(gè)節(jié)點(diǎn)。因此，合并操作的時(shí)間復(fù)雜度為：

O(logN1+logN2)=O(logN)合并操作的代碼如下： FunctionMerge(A,B) IfA=NULLThenreturnB IfB=NULLThenreturnA Ifkey(B)<key(A)Thenswap(A,B) right(A)←Merge(right(A),B) Ifdist(right(A))>dist(left(A))Then swap(left(A),right(A)) Ifright(A)=NULLThendist(A)←0 Elsedist(A)←dist(right(A))+1 returnA EndFunction左偏樹合并操作都是一直沿著兩棵左偏樹的最右路徑進(jìn)行的。124左偏樹左偏樹的特點(diǎn)：時(shí)空效率高編程復(fù)雜度低左偏樹的應(yīng)用：可并堆優(yōu)先隊(duì)列左偏樹左偏樹的特點(diǎn)：125左偏樹HDU1512題意：剛開始所有的猴子自成一群且互相都不認(rèn)識(shí)，他們互相認(rèn)識(shí)當(dāng)且僅當(dāng)他們各自群中最強(qiáng)的猴子互相打了一場(chǎng)，體力各減為一半。問最后這群猴子中體力最強(qiáng)猴子的體力是多少思路如何？左偏樹HDU1512126左偏樹并查？可行，但只能作為輔助手段。優(yōu)先隊(duì)列+并查？O（nlogn）的合并效率實(shí)在不敢恭維很好。。。左偏樹開始發(fā)揮了效力了！左偏樹并查？127左偏樹步驟：使用并查集（這里其實(shí)準(zhǔn)確來說應(yīng)該是一種記錄父結(jié)點(diǎn)編號(hào)的數(shù)組）記錄各結(jié)點(diǎn)在各自堆中的父結(jié)點(diǎn)查詢兩只猴子所在堆的根結(jié)點(diǎn)，如果兩只猴子根結(jié)點(diǎn)相同，則不必打架，否則，取各自堆中最大元素（也就是根結(jié)點(diǎn)）打一場(chǎng)打架，此時(shí)先讓各自堆中根的左右兒子指向本身，再對(duì)左右兒子進(jìn)行合并生成新樹（即pop操作）并適當(dāng)修改父結(jié)點(diǎn)數(shù)組，令根結(jié)點(diǎn)值減半后與新樹再次合并，并適時(shí)修改父結(jié)點(diǎn)數(shù)組（即push操作），再將兩個(gè)堆中的根進(jìn)行合并（即unition操作）。是不是很簡單的實(shí)現(xiàn)？左偏樹步驟：128斜堆如何對(duì)左偏樹進(jìn)行優(yōu)化？思考?。。∥覀冏⒁獾皆谧笃珮渲斜仨氁芯嚯x的概念，但我們可以發(fā)現(xiàn)一個(gè)性質(zhì)，如果每次合并都向右進(jìn)行，每次完成后將右邊的結(jié)點(diǎn)甩到左邊，不正好符合了左偏的性質(zhì)么？很好去掉距離，提高效率，優(yōu)化的王道！不足（單次合并可能退化到O(n)，但實(shí)際效果上，兩者都差不多）斜堆如何對(duì)左偏樹進(jìn)行優(yōu)化？129AC自動(dòng)機(jī)AC自動(dòng)機(jī)是由Aho和Corasick提出的數(shù)據(jù)結(jié)構(gòu),是對(duì)Trie樹的一種改造，是對(duì)find操作的修正，也是多模式串匹配的基本實(shí)現(xiàn)！HDU2222題意給你N個(gè)關(guān)鍵字,以及一句描述,問有多少個(gè)關(guān)鍵字在這句描述中出現(xiàn)?思路???AC自動(dòng)機(jī)AC自動(dòng)機(jī)是由Aho和Corasick提出的數(shù)據(jù)結(jié)130AC自動(dòng)機(jī)采用普通方法？O（Nnm）…m=50,n=1000000,N=10000黃花菜都涼了……KMP?O(N(m+n))?就這點(diǎn)優(yōu)化？塞牙縫都不夠那怎么辦?。。C自動(dòng)機(jī)??！O（Nm+n）…強(qiáng)大！??！AC自動(dòng)機(jī)采用普通方法？131AC自動(dòng)機(jī)步驟將所有關(guān)鍵字塞入Trie好了，現(xiàn)在我們已經(jīng)有一棵Trie了，但這還不夠，我們還要在Trie上引入一個(gè)很強(qiáng)大的東西：失敗指針或者說shift數(shù)組或者說Next函數(shù)…..你愛怎么叫怎么叫吧，反正就是KMP的精華所在，這也是我為什么叫你看KMP的原因。KMP中我們用兩個(gè)指針i和j分別表示，A[i-j+1..i]與B[1..j]完全相等。也就是說，i是不斷增加的，隨著i的增加j相應(yīng)地變化，且j滿足以A[i]結(jié)尾的長度為j的字符串正好匹配B串的前j個(gè)字符，當(dāng)A[i+1]<>B[j+1]，KMP的策略是調(diào)整j的位置（減小j值）使得A[i-j+1..i]與B[1..j]保持匹配且新的B[j+1]恰好與A[i+1]匹配（從而使得i和j能繼續(xù)增加）。Trie樹上的失敗指針與此類似。AC自動(dòng)機(jī)步驟132AC自動(dòng)機(jī)假設(shè)有一個(gè)節(jié)點(diǎn)k，他的失敗指針指向j。那么k,j滿足這個(gè)性質(zhì)：設(shè)root到j(luò)的距離為n，則從k之上的第n個(gè)節(jié)點(diǎn)到k所組成的長度為n的單詞，與從root到j(luò)所組成的單詞相同。那么我們要怎樣構(gòu)建這個(gè)東西呢？其實(shí)我們可以用一個(gè)簡單的BFS搞定這一切。對(duì)于每個(gè)節(jié)點(diǎn)，我們可以這樣處理：設(shè)這個(gè)節(jié)點(diǎn)上的字母為C，沿著他父親的失敗指針走，直到走到一個(gè)節(jié)點(diǎn)，他的兒子中也有字母為C的節(jié)點(diǎn)。然后把當(dāng)前節(jié)點(diǎn)的失敗指針指向那個(gè)字目也為C的兒子。如果一直走到了root都沒找到，那就把失敗指針指向root最開始，我們把root加入隊(duì)列(root的失敗指針顯然指向自己)，這以后我們每處理一個(gè)點(diǎn)，就把它的所有兒子加入隊(duì)列，直到搞完。好了，現(xiàn)在我們有了一棵帶失敗指針的Trie了?。?！可以開始進(jìn)行AC自動(dòng)機(jī)了！AC自動(dòng)機(jī)假設(shè)有一個(gè)節(jié)點(diǎn)k，他的失敗指針指向j。那么k,j滿133AC自動(dòng)機(jī)一開始，Trie中有一個(gè)指針t1指向root，待匹配串(也就是“文章”)中有一個(gè)指針t2指向串頭。接下來的操作和KMP很相似：如果t2指向的字母，是Trie樹中，t1指向的節(jié)點(diǎn)的兒子，那么t2+1,t1改為那個(gè)兒子的編號(hào)，否則t1順這當(dāng)前節(jié)點(diǎn)的失敗指針向上找，直到t2是t1的一個(gè)兒子，或者t1指向根。如果t1路過了一個(gè)綠色的點(diǎn)，那么以這個(gè)點(diǎn)結(jié)尾的單詞就算出現(xiàn)過了?；蛘呷绻鹴1所在的點(diǎn)可以順著失敗指針走到一個(gè)綠色點(diǎn)，那么以那個(gè)綠點(diǎn)結(jié)尾的單詞就算出現(xiàn)過了。本題要注意的是必須在描述串后面添加特殊符號(hào)，否則將忽略對(duì)完全匹配關(guān)鍵字的統(tǒng)計(jì)。注意：BFS尋找失敗指針的過程，是一個(gè)自我匹配的過程。AC自動(dòng)機(jī)一開始，Trie中有一個(gè)指針t1指向root，待匹134AC自動(dòng)機(jī)特點(diǎn)：多模式匹配的良方，一次自我適配后，對(duì)任意文章的匹配均是線性復(fù)雜度。編程復(fù)雜度較低。使用方便，居家旅行之必備！AC自動(dòng)機(jī)特點(diǎn)：135圖圖的結(jié)構(gòu)是樹結(jié)構(gòu)的拓展，但在實(shí)現(xiàn)基本以數(shù)組的形式進(jìn)行，在本質(zhì)上來說所有的數(shù)據(jù)結(jié)構(gòu)都是互相滲透交融的，所謂大道行簡，只有掌握了本質(zhì)，才能以不變應(yīng)萬變?。?！基本表示：鄰接陣鄰接表由于上部分內(nèi)容已經(jīng)有所涉獵，這里就不再提過了圖圖的結(jié)構(gòu)是樹結(jié)構(gòu)的拓展，但在實(shí)現(xiàn)基本以數(shù)組的形式進(jìn)行，在本136串什么是串？串是由字符所組成的有限序列，我們只關(guān)心串的字符屬性，而不關(guān)心其數(shù)值屬性。串有著十分明顯的邏輯結(jié)構(gòu)，前驅(qū)后繼都是固定的，不得隨意更改！關(guān)于字符串的處理一般而言都是ICPC的中檔題目，如果使用模擬或者暴力方法，一般來說都是無效的。應(yīng)用結(jié)構(gòu)：后綴數(shù)組串什么是串？137后綴數(shù)組什么是后綴數(shù)組？對(duì)于長度為len的字符串str，從位置i開始至len的所有字符序列稱為i的后綴后綴數(shù)組（SA）保存的就是這些后綴序列的排序后的開頭位置.Rank數(shù)組是SA的反函數(shù)，也就是說Rank[i]保存的是從位置i開始的后綴在所有后綴中的名次.后綴數(shù)組什么是后綴數(shù)組？138后綴數(shù)組如何利用這種結(jié)構(gòu)性質(zhì)？我們還需要計(jì)算一個(gè)輔助的工具——最長公共前綴（LongestCommonPrefix）!!對(duì)兩個(gè)字符串u,v定義函數(shù)lcp(u,v)=max{i|u=iv}，也就是從頭開始順次比較u和v的對(duì)應(yīng)字符，對(duì)應(yīng)字符持續(xù)相等的最大位置，稱為這兩個(gè)字符串的最長公共前綴。對(duì)正整數(shù)i,j定義LCP(i,j)=lcp(Suffix(SA[i]),Suffix(SA[j])，其中i,j均為1至n的整數(shù)。LCP(i,j)也就是后綴數(shù)組中第i個(gè)和第j個(gè)后綴的最長公共前綴的長度。關(guān)于LCP有兩個(gè)顯而易見的性質(zhì)：性質(zhì)2.1LCP(i,j)=LCP(j,i)性質(zhì)2.2LCP(i,i)=len(Suffix(SA[i]))=n-SA[i]+1這兩個(gè)性質(zhì)的用處在于，我們計(jì)算LCP(i,j)時(shí)只需要考慮i<j的情況，因?yàn)閕>j時(shí)可交換i,j，i=j時(shí)可以直接輸出結(jié)果n-SA[i]+1。后綴數(shù)組如何利用這種結(jié)構(gòu)性質(zhì)？139后綴數(shù)組直接根據(jù)定義，用順次比較對(duì)應(yīng)字符的方法來計(jì)算LCP(i,j)顯然是很低效的，時(shí)間復(fù)雜度為O(n)，所以我們必須進(jìn)行適當(dāng)?shù)念A(yù)處理以降低每次計(jì)算LCP的復(fù)雜度。經(jīng)過仔細(xì)分析，我們發(fā)現(xiàn)LCP函數(shù)有一個(gè)非常好的性