Acm競賽常用算法與數(shù)據(jù)結(jié)構(gòu)

1、 常用算法 &數(shù)據(jù)結(jié)構(gòu) 浙江大學微軟技術(shù)俱樂部 彭鵬ACM競賽11、競賽中常見的16種題型 3、競賽中基本的數(shù)據(jù)結(jié)構(gòu)與算法 2、時空復(fù)雜度的分析0、如何建立一支強隊？2如何建立一支強隊個人的能力理論(幾何, 數(shù)論, 動態(tài)規(guī)劃, 圖論等)技術(shù)(編程)隊員能力上的互補某論壇，一無聊男yy的中國“夢之隊”錢文杰（？） 反應(yīng)奇快，擅長隨機化，貪心，NOI貪心王劉汝佳or吳嘉之 見多識廣，做過的題必別人見過的題多趙爽 上海交大的“割題手”3Leader/Coordinato(協(xié)調(diào)比賽進程)Reader(發(fā)現(xiàn)題目隱諱的涵義)Thinker(邏輯能力強, 收集其他隊員意見)Programmer/Debugg

2、er(反應(yīng)快/穩(wěn),細心)Helper(協(xié)助比賽, 查錯, 驗證數(shù)據(jù)等)一支強隊需要的角色4參考書籍主要參考書籍C+ Primer C+ 標準程序庫算法導(dǎo)論算法藝術(shù)與信息學競賽組合數(shù)學計算幾何？ 歷屆國家集訓(xùn)隊論文 5時空復(fù)雜度的分析時間復(fù)雜度的分析空間復(fù)雜度的分析6函數(shù)增長和運行時間引用劉汝佳序列和字符串7常見題型Dynamic Programming(動態(tài)規(guī)劃)Greedy(貪心) Complete Search(窮舉) Flood Fill (種子填充)8常見題型Shortest Path (最短路徑)Recursive Search Techniques (回溯）Minimum Span

3、ning Tree （最小生成樹）Knapsack（背包） 9常見題型Computational Geometry(計算幾何) Network Flow(網(wǎng)絡(luò)流) Eulerian Path (歐拉回路)Two-Dimensional Convex Hull (二維凸包)10常見題型BigNums (大數(shù))Heuristic Search(啟發(fā)式搜索) Approximate Search (近似搜索)Ad Hoc Problems(雜題) 1112枚舉法又叫窮舉法，它利用了計算機計算速度快且準確的特點，是最為樸素和有效的一種算法。不是辦法的辦法但有時卻是最好的辦法13Pizza Anyone

4、? （ZOJ 1219）題目大意： 你需要為你和你的朋友們訂一個皮薩。每個朋友都會告訴你他們想和不想放進皮薩里的東西。 你是否能訂一個皮薩，讓他滿足每個人至少一個條件。 假設(shè)一共有16種東西可以放進皮薩。14 是個對計算機很小的數(shù)15貪心法(Greedy)矩陣胚理論（詳情請參考算法導(dǎo)論） 枚舉法的時間效率很低，貪心法恰恰與其相反。并且貪心法的程序也很好實現(xiàn)。 無數(shù)論文都指責貪心法往往得不到問題的最優(yōu)解。 絕世高手與普通高手的差距所在。16棧和隊列棧：后進先出（LIFO）隊列：先進先出（FIFO）17字符串的輸入與輸出 或 char s100;scanf(%s,s); string a(s);S

5、tring a; cin a;C+常用頭文件字符串的讀入哪種讀入更快？在輸入數(shù)據(jù)達到1M時，cin，cout將比scanf , printf在速度上有明顯的劣勢18排序排序的種類：交換排序，選擇排序，插入排序，堆排序希爾排序，快速排序，歸并排序，桶排序19用C+實現(xiàn)排序#include數(shù)組 asort( a , a + 5 );vector asort( a. begin() , a. end() );20并查集并查集是一種樹型的數(shù)據(jù)結(jié)構(gòu)，用于處理一些不相交集合的合并問題。并查集的主要操作有1合并兩個不相交集合2判斷兩個元素是否屬于同一個集合3路徑壓縮21Parity(ceoi99)有一個01

6、序列,長度=1000000000,現(xiàn)在有n條信息,每條信息的形式是a b even/odd。表示第a位到第b位元素之間的元素總和是偶數(shù)/奇數(shù)。你的任務(wù)是對于這些給定的信息，輸出第一個不正確的信息所在位置-1。信息的數(shù)目不超過5000。如果信息全部正確，即可以找到一個滿足要求的01序列，那么輸出n。22Parity(ceoi99)從整個01序列肯定是無法入手的，因為它的長度高達109。從范圍比較小的n入手。也就是說我們需要對信息進行一些特殊的處理。a b even/odd，那么將元素b指向a-1，邊的權(quán)值是even/odd。下面我們由樣例來說明一下這個處理方法。23Parity(ceoi99)（

7、肖天）建立sum數(shù)組，sumi表示從1到i之和是奇（true）還是偶（false），sum0=false。這樣題目中給的任意問題（a,b）的答案都可以用sumb xor suma-1表示。開始我們并不知道sum1.n的值，不妨設(shè)為false，這時任意suma,sumb都是獨立的。對于每對問答(a,b,c)，都可以知道sumb xor suma-1=c,由此把sumb和suma-1聯(lián)系起來。這步操作可以用并查集完成，對于問答（a,b,c）如果suma-1,sumb不屬于一個集合就把它們并起來，否則如果suma-1 xor sumb不等于c則說明出現(xiàn)矛盾，輸出總句數(shù)，退出。對于不出現(xiàn)矛盾的sum數(shù)

8、組，對于每個集合分為兩個部分，我們指定其中一個部分為true，另一個部分為false，則可以確定sum數(shù)組，利用sumi xor sumi-1可以求出第i位的數(shù)字，由于不同集合之間沒有問答出現(xiàn)，所以此數(shù)列是一可行解，證明算法正確。 24堆(優(yōu)先隊列)優(yōu)點： 實現(xiàn)簡單動態(tài)維護一組數(shù)據(jù)中最?。ù螅┑囊粋€數(shù)組維護 25例題: 積水一個長方形網(wǎng)格包含了n*m塊地，每塊地上面有1個長方體。每一個長方形蓋住了一塊地，地的面積是1平方英寸。相鄰的地上的長方體之間沒有空隙。一場大雨降臨了這個建筑物，在建筑物的某些區(qū)域有積水產(chǎn)生。給各方格高度, 求積水總量26分析定義每塊地上的長方體的高度稱為原始高度積滿水時的

9、水面高度稱為積水高度（高于積水高度的水一定會流走，低于積水高度的水一定流不走）積水高度與原始高度之差為積水深度如果一個長方體上不可能有積水，那么它的積水高度就等于它的原始高度。最外圈不能積水，積水高度等于原始高度27分析由外而內(nèi)計算。每次選取外圍的格子中積水高度最低的一個格子x，考慮它周圍所有在網(wǎng)格內(nèi)部的格子y想象不斷的往x和y里注水，但是x的積水高度固定（想象該高度處有一個小孔），因此如果y的原始高度不小于x的積水高度，那么它的積水高度就是它的原始高度如果y的原始高度小于x的積水高度，那么它的積水高度就等于x的積水高度每次用堆取出x進行計算，O(mnlogmn)。28哈希表(Hash)理論上

10、查找速度最快的數(shù)據(jù)結(jié)構(gòu)之一缺點：需要大量的內(nèi)存需要構(gòu)造Key 29Hash表的實現(xiàn)數(shù)組沖突解決法開散列法閉散列法C+ sgi stl 實現(xiàn)30Hash Key的選取數(shù)值：方法一：直接取余數(shù)（一般選取質(zhì)數(shù)M最為除數(shù)）方法二：平方取中法，即計算關(guān)鍵值的平方，再取中間r位形成一個大小為 的表是多少？31字符串：int ELFhash( char* key )unsigned int h = 0;while( *key )h = ( h 24;h &= -g;return h % M;方法二：ELFhash函數(shù)方法一： 折疊法：即把所有字符的ASCII碼加起來32二分搜索樹普通的二分搜索樹時間復(fù)雜度：

11、缺點： 容易出現(xiàn)不平衡的情況AVL Tree ， Splay tree , 紅黑樹 33樹堆(Treap)Treap = Tree + heap每次插入/刪除結(jié)點的時候，給結(jié)點隨機分配一個優(yōu)先級，讓Treap關(guān)于優(yōu)先級形成一個堆的同時，關(guān)于關(guān)鍵碼形成BST跳躍表、B樹34跳躍表（Skiplists）35線段樹 在一類問題中，我們需要經(jīng)常處理可以映射在一個坐標軸上的一些固定線段，例如說映射在OX軸上的線段。由于線段是可以互相覆蓋的，有時需要動態(tài)地取線段的并，例如取得并區(qū)間的總長度，或者并區(qū)間的個數(shù)等等。一個線段是對應(yīng)于一個區(qū)間的，因此線段樹也可以叫做區(qū)間樹。3637 Atlantis （ZOJ

12、1128） 一個平面被很多矩形覆蓋，矩形之間會相互疊加。輸出矩形覆蓋的總面積。38Atlantis （ZOJ 1128）線段樹矩形切割39矩形切割40字典樹( Trie )當關(guān)鍵字是串的時候，理論上查找最快的數(shù)據(jù)結(jié)構(gòu)定義：保存字符串用的樹型數(shù)據(jù)結(jié)構(gòu)(多叉樹），其中每個節(jié)點表示一個公共前綴，單詞信息保存在相應(yīng)的頁節(jié)點里面。41給如下幾個單詞，構(gòu)造的單詞樹：An，Ant，All，AllotAlloy，Aloe，Are，Atebe版權(quán)歸浙江大學ACM領(lǐng)隊徐串所有轉(zhuǎn)載需保留此字樣42T9（ZOJ 1038）題目描述：手機有智能英文輸入法，他根據(jù)自己已有的詞匯表，即使你每個數(shù)字只按一次也可以猜出你要按的

13、是哪個單詞（方法就是從所有可能的串中選出出現(xiàn)概率最高的一個）。詞匯表:hell 3hello 4idea 8next 8super 3按435561是的響應(yīng)顯示iidhelhellhello43動態(tài)規(guī)劃動態(tài)規(guī)劃的時間效率極高。 動態(tài)規(guī)劃的算法簡潔，一般只用邊界和狀態(tài)轉(zhuǎn)移方程就可清晰地表示出進行規(guī)劃的步驟；而因為有了這些用數(shù)學語言描述的天然材料，編程也較為方便。最重要的一點：動態(tài)規(guī)劃不單是一種思想，也不單是一類算法，它是思想方法和具體算法的混合物。 摘自徐靜動態(tài)規(guī)劃的算法與實現(xiàn)44動態(tài)規(guī)劃無后效性遞推法和記憶化搜索45深度優(yōu)先搜索(DFS)按照深度優(yōu)先的順序遍歷狀態(tài)空間，通常用遞歸或者棧來實現(xiàn)。

14、void dfs ( state , depth )if ( state = 結(jié)束狀態(tài) ）退出；枚舉所有可行狀態(tài)更新全局變量；dfs( newstate , depth + 1 );還原全局變量46寬度優(yōu)先搜索(BFS)如果代價和搜索樹深度成正比，那么可以通過廣度優(yōu)先搜索得到解。由于空間占用大，BFS用處不是很廣，一般只用在路徑尋找問題中，但是一旦使用，將比深度優(yōu)先搜括看得多雙向?qū)挾葍?yōu)先搜索深度優(yōu)先和寬度優(yōu)先搜索比較47Prime Ring Problem （ZOJ 1457）A ring is compose of n circles as shown in diagram. Put nat

15、ural number 1, 2, ., n into each circle separately, and the sum of numbers in two adjacent circles should be a prime.Note: the number of first circle should always be 1. n (0 n 20) 48while ( !deque.empty() )state = deque0;deque.pop();枚舉所有可行狀態(tài)tempstate = 狀態(tài)改變(state);deque.push_back(tempstate);寬度優(yōu)先搜索(

16、BFS)寬度優(yōu)先搜索的框架49Winlinez (ZOJ 1591)Now we have a board of 9 * 9 grids, on which there are several beads. These beads have only seven colors, we number them 1 - 7. We define the empty grid to be zero. Each turn you can move any bead on the board to the destination where there is a route between them.

17、The route means that the bead can move up, down, left or right to the adjacent empty grid and may go on until it reaches the destination. After the moving, if there are five or more same-colored beads in a line (row, column, diagonal), they will all be eliminated.50博弈問題 給定一個有向無環(huán)圖(X, F)，其中X是一個非空的點集(每

18、個點表示一個位置)，F(xiàn)是一個在集合X上的函數(shù)，對于集合X中的任意一個元素x，F(xiàn)(x)返回一個集合X的子集，即，F(xiàn)(x)表示了由一個位置x可以到達的位置。如果F(x)是空集，則稱x是一個結(jié)束位置。 現(xiàn)在兩個人在這樣的一個有向圖上玩游戲，首先在一個初始位置x0上放置了一個棋子，然后他們將按照如下規(guī)則進行游戲： 首先由選手I從初始位置x0進行移動。 兩個選手交替移動。 在一個位置x，選手可以將棋子移到位置y上，其中yx。 如果輪到某一個選手移動時棋子處在一個結(jié)束位置，那么這個選手就會因為無法繼續(xù)移動棋子而被判輸?shù)暨@局游戲。 對于給定的有向圖和初始位置，請你判斷出選手I與選手II誰會獲勝。 樓天城淺談

19、一類博弈問題的解法51局面局面局面終結(jié)局面局面估價函數(shù)Alpha-Beta剪枝52A Multiplication Game（）Stan和Ollie一起做游戲。游戲的內(nèi)容是將一個整數(shù)乘上到中的任一個數(shù)。Stan總是從開始，然后兩個人交替相乘。在游戲開始前，兩個人訂了一個數(shù)（1n4294967295 ),誰先到達，誰就是最后的勝利者。53最大公約數(shù)最小公倍數(shù)歐幾里得輾轉(zhuǎn)相除int gcd ( int a , int b)return b?gcd(b,a%b):a;int lcm ( int a , int b)return a / gcd (a , b) * b;54篩選法求質(zhì)數(shù)表Eratost

20、henes（埃拉托色尼）篩選法：每次求出一個新的素數(shù)，就把n以內(nèi)的它的所有倍數(shù)都篩去。在實現(xiàn)的時候，對于一個素數(shù)p，只需要篩去 等就可以了，因為 已經(jīng)在q的第一個素因子被找到的時候被篩去了55#define N 100#define M 100int p M , plist = 0;int init()memset( p , 0 , sizeof( p ) );for ( int i = 2; i = N; i+ )if ( !p i )p plist+ = i;int del = i * i;while ( del a i + 1 & i = 0 ) i-; if ( i 0 ) retur

21、n 0; for ( Min = i + 1 , j = i + 2; j a i & a j a Min ) Min = j; swap( a i , a Min ); for ( int j = i + 1; j n; j+ ) for ( int k = j + 1; k a k ) swap( a j , a k ); return 1;61Catalan數(shù)將正邊形用對角線剖分成三角形的方法數(shù)通項公式62Fibonacci數(shù)Fibonacci數(shù)的O(lgn)實現(xiàn)63彩票 大街上到處在賣彩票，一元錢一張。購買撕開它上面的錫箔，你會看到一個漂亮的圖案。圖案有n種，如果你收集到所有n種彩票，

22、就可以得大獎。請問，在平均情況下，需要買多少張彩票才能得到大獎呢？ 64分析總結(jié)已有0個圖案: 拿1次就可以多搜集一個已有1個圖案: 平均拿n/(n-1)次就可多搜集一個已有k個圖案: 平均拿n/(n-k)次就可多搜集一個所以總次數(shù)為: n(1+1/2+1/3+1/n)65數(shù)值分析定積分計算(Romberg)多項式求根(牛頓法)線形方程組(高斯消元法)66生成樹問題最小生成樹(MST)最大生成樹 ?Prim算法Kruskal算法兩種算法的使用范圍67最短路問題單源最短路徑問題Dijkstra多源最短路徑問題Floyd-WarshallBellman-ford68第n短路徑第二最短路徑：枚舉最短

23、路徑上的每條邊，每次刪除一條，然后求新圖的最短路徑，取這些圖的最短路徑。最短的一條即為第二最短路徑第n最短路徑可以在求解第n-1最短路徑的基礎(chǔ)上求解69Arbitrage (ZOJ 1092)題目大意:有很多很多種貨幣,每兩種貨幣之間都有一個匯率,問是否能找到一種套匯(?)的方法70網(wǎng)絡(luò)流問題特點： 2.較高的編程復(fù)雜度 3.較死板的構(gòu)造方法 1.較廣的使用范圍由于后面的兩個特點，網(wǎng)絡(luò)流算法已經(jīng)逐步淡出了高中信息學舞臺。但在競賽中，網(wǎng)絡(luò)流算法仍占據(jù)著一席之地71網(wǎng)絡(luò)流模型若有向圖G=(V,E)滿足下列條件： 有且僅有一個頂點S，它的入度為零，即d-(S) = 0，這個頂點S便稱為源點，或稱為發(fā)

24、點。有且僅有一個頂點T，它的出度為零，即d+(T) = 0，這個頂點T便稱為匯點，或稱為收點。每一條弧都有非負數(shù)，叫做該邊的容量。邊(vi, vj)的容量用cij表示。則稱之為網(wǎng)絡(luò)流圖，記為G = (V, E, C)72最大流最大流的定義求有向帶權(quán)圖G=(V,E,C)的一個流,它滿足容量限制條件 ，且原點提供的流量最大最大流解法Ford-Fulkerson methodPush-relabel algorithmRelabel-to-front algorithm算法導(dǎo)論第26章73最小費用最大流給定網(wǎng)絡(luò)G=（V，E，C，W），求網(wǎng)絡(luò)上的一個流f，使得f是網(wǎng)絡(luò)的最大流，且每條弧的流量與費用的乘

25、積加起來的總合帶上下界的最小費用最大流最小費用路算法消圈算法74網(wǎng)絡(luò)流算法（金愷） 難點：網(wǎng)絡(luò)流在具體問題中的應(yīng)用，最具挑戰(zhàn)性的部分是模型的構(gòu)造，其次是算法的優(yōu)化。 構(gòu)造沒有現(xiàn)成的模式可依，只能根據(jù)題目的具體條件來分析。這需要對各種網(wǎng)絡(luò)流的性質(zhì)了如指掌，并且歸納總結(jié)一些經(jīng)驗，發(fā)揮我們的創(chuàng)造性。一般來說，用得最多的方法是拆點法。優(yōu)化是算法的重要環(huán)節(jié)，它并非朝夕之功就能提高的，必須靠經(jīng)驗的積累。 75二分圖匹配問題二分圖是一類很重要的圖，它的頂點可以分成兩個集合X和Y，圖的所有邊一定是有一個頂點屬于集合X，另一個頂點屬于集合Y。76二分圖的最大匹配同類結(jié)點不鄰接。圖的一個匹配是一些邊的集合，任意兩

26、條邊沒有公共端點。圖中包含邊數(shù)最多的匹配稱為圖的最大匹配匈牙利算法網(wǎng)絡(luò)流解法（Hopcroft）77二分圖的最小覆蓋定理：二分圖中點對邊的最小覆蓋等于其最大匹配數(shù)。M個是足夠的。只需要讓它們覆蓋最大匹配的M條邊，則其它邊一定被覆蓋（如果有邊e不被覆蓋，把e加入后得到一個更大的匹配）M個是必須的。僅考慮形成最大匹配的這M條邊，由于它們兩兩個無公共點，因此至少需要M個點才能把它們覆蓋78二分圖的匹配二分圖的最佳匹配二分圖的完美匹配二分圖的完備匹配穩(wěn)定婚姻問題79獨立集考慮圖G=（V，E）。S是V的一個子集，如果在S中任意兩個頂點在G中都不是鄰接的，那么S就是G的一個獨立集。如果在G中不存在具有|S

27、1|S|，則稱S為G的最大獨立集80誘導(dǎo)子圖頂點-導(dǎo)出子圖另V1是圖G=(V,E)的頂點集V的子集,如果E1是E的子集,且邊(vi,vj)屬于E1,當且僅當vi和vj屬于V1,那么子圖G1=(V1,E1)就叫做G在頂點集V1上的導(dǎo)出子圖。如果vi和vj屬于V1，那么E中任何一條以vi和vj為端點的邊都屬于E181弦圖定理:如果一個圖的任何誘導(dǎo)子圖都不是K階環(huán)(K=4),那么該圖稱為弦圖82Fishing Net (ZOJ 1015)判斷一個圖是否是弦圖?83計算幾何判兩條線斷相交判點在多邊性內(nèi)部二維凸包叉乘84Online Judge的簡稱一種通過網(wǎng)絡(luò)信息交互在線判題的系統(tǒng)它模擬了ICPC比賽

28、真實的情況當前世界上規(guī)模比較大的OJUVA ZOJURALUSACOOJ是什么85Zhejiang university online judge推薦使用：gcc + vivs2003/vs200586Submission Error - 提交使用了不正確的隊名、題號等。No Such Problem - 檢查題號有沒有填錯？Compile Error - 程序不能通過編譯。Run Time Error - 程序運行過程中出現(xiàn)非正常中斷。Memory Limit Exceeded - 內(nèi)存使用量超過裁判規(guī)定的上限。Output Limit Exceeded - 輸出數(shù)據(jù)量過大，多半死循環(huán)了Ti

29、me Limit Exceeded - 運行超過時限還沒有得到輸出結(jié)果。Wrong Answer - 答案錯誤。Presentation Error - 輸出格式不對，可檢查空格、回車等等細節(jié)。Accepted - 恭喜恭喜！Out Of Contest Time - 比賽已經(jīng)結(jié)束啦！Contest Rule Violation - 宣判極刑，參賽資格隨即被取消?？赡苁盏降姆答佇畔ǎ?7常見問題long long vc+6.0 _int64gcc vc+7.0 long longprintf(“%lld”)在處理浮點數(shù)時，請選擇double讀入一行g(shù)ets() , getline()88ZOJ輸入輸出程序提交上去后，服務(wù)器（？）會編譯它（gcc),然后重新定向它的輸入輸出。所以，cod