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

1、ACM 賽 常用算法 浙江大學(xué)微軟技術(shù)俱樂(lè)部彭鵬 1、 ACM/ICPC 簡(jiǎn)介 2、 競(jìng)賽中常見(jiàn)的16種題型 3、 時(shí)空復(fù)朵度的分析 4、 5、 競(jìng)賽中基木的數(shù)據(jù)結(jié)構(gòu)與算法 ZOJ入門(mén) 2 ACM/IC PC 簡(jiǎn)介 ACM - Assocxatxon for Coixqputxng Machinery -美國(guó)計(jì)算機(jī)學(xué)會(huì) ICPC - International Collegiate Programming Contest -國(guó)際大學(xué)生程序設(shè)計(jì)競(jìng)賽 ACM ACM (Assocxatxon for Computing Machinery) 成立于計(jì)算機(jī)誕生次年，是目前計(jì)算機(jī)學(xué)界中歷史最 悠久、最

2、具權(quán)威性的組織，是推進(jìn)信息技術(shù)專(zhuān)業(yè)人員 和學(xué)生提高技巧的主要力量。ACM通過(guò)提供前沿技 術(shù)信息和從理論到實(shí)踐的轉(zhuǎn)化，為其全球75萬(wàn)名成 員服務(wù)，并已經(jīng)成為信息科技領(lǐng)域的一個(gè)基本信息來(lái) O 4 ICPC ACM主辦的國(guó)際大學(xué)生程序設(shè)計(jì)競(jìng)賽(International Collegiate Programming Contest),簡(jiǎn)稱(chēng)ACM / ICPC,自從1977年開(kāi)始至今己經(jīng)連續(xù)舉辦28屆。其宗旨 是提供一個(gè)讓大學(xué)生向HT界展示自己分析問(wèn)題和解決問(wèn) 題的能力的絕好機(jī)會(huì)，并成為一個(gè)有效的途徑，讓下一代 PT天才可以接觸到其日后工作中將要用到的各種軟件。 自1998年IBM成為該項(xiàng)競(jìng)賽的贊助商

3、以來(lái)，大賽規(guī)模不 斷擴(kuò)大。去年有個(gè)國(guó)家1582所大學(xué)派出4109支隊(duì)伍 參加了30個(gè)賽點(diǎn)的分區(qū)賽，其中78支隊(duì)伍參加今年4月在 上海香格里拉酒丿占舉辦的世界總決賽。 -現(xiàn)在，ACM / ICPC已成為世界各國(guó)大學(xué)生中最具影響力 的國(guó)際計(jì)算機(jī)賽事。 ICPC競(jìng)賽規(guī)則 三人組隊(duì) 在46小時(shí) 編寫(xiě)C/C+或Java程序 解決6-10道題 完成題目數(shù)多的隊(duì)伍優(yōu)勝 完成題冃數(shù)一樣的隊(duì)伍罰時(shí)少的優(yōu)勝 6 acm IBM Q Contwi iTTWwrl HMMor ICPC log A problem A thought A solution A balloon 中國(guó)各高校ACM開(kāi)展情況 清華人學(xué)上海交通

4、大學(xué) 中山大學(xué)復(fù)旦大學(xué) 北京人學(xué)南京人學(xué) 浙江人學(xué) 8 浙江大學(xué)ACM集訓(xùn)隊(duì)選拔標(biāo)準(zhǔn) 根據(jù)校內(nèi)程序設(shè)計(jì)竟春的結(jié)采.現(xiàn)擬定集訓(xùn)隊(duì)具體選拔標(biāo)進(jìn)如2 1.曾參加過(guò)去年4假集訓(xùn)的隊(duì)員口愿入【嗣： 未參加過(guò)集訓(xùn)，但滿足卜列條件若口愿入國(guó)： 2對(duì)ACM ICPC活動(dòng)右極人熱悄，視練習(xí)題如游戲；并且 3校內(nèi)程序設(shè)計(jì)競(jìng)賽前5名，或者 4. 校內(nèi)程序設(shè)汁競(jìng)賽第69名，并1L7JJ11J前在ZOJ通過(guò)至少100 題；或者 5. 校內(nèi)程序設(shè)訃競(jìng)賽10-15名，并L7丿J1U就在ZOJ通過(guò)金少 150題；或者 6. 7月1日詢(xún)?cè)赯OJ通過(guò)至少200題。 如何建立一支強(qiáng)隊(duì) 個(gè)人的能力 理論（兒何數(shù)論，動(dòng)態(tài)規(guī)劃，圖論等）

5、 技術(shù)（編程） 隊(duì)員能力上的互補(bǔ) 某論壇，一無(wú)聊男yy的中國(guó)“夢(mèng)之隊(duì)” 錢(qián)文杰（？）反應(yīng)奇快，擅長(zhǎng)隨機(jī)化，貪心，Ncn貪心王 上海交大的“割懸手” 劉汝佳or吳嘉之 見(jiàn)多識(shí)廣，做過(guò)的題必別人見(jiàn)過(guò)的題多 趙爽 10 支強(qiáng)隊(duì)需要的角色 Leader/Coordinato（協(xié)調(diào)比賽進(jìn)程） Reader（發(fā)現(xiàn)題I隱諱的涵義） ThinkerC邏輯能力強(qiáng)收集其他隊(duì)員意見(jiàn)） Programmer/Debugger（反應(yīng)快/ 穩(wěn)細(xì)心） Helper（協(xié)助比賽，查錯(cuò)，驗(yàn)證數(shù)據(jù)等） 11 參考書(shū)籍 上要參考書(shū)籍 -C+ P rimer -C+標(biāo)準(zhǔn)程序庫(kù) -算法導(dǎo)論 -算法藝術(shù)與信息學(xué)競(jìng)賽 -組合數(shù)學(xué) -計(jì)算兒何

6、？ ？ -歷屈國(guó)家集訓(xùn)隊(duì)論文 12 網(wǎng)絡(luò)資源 httD：/acmzjueducn httD：/acmtimusru http:/acmsqunj httD：/acedeloscom/usacogate http:/ http:/wwwoibhorq/bbs/index，Dhp 13 時(shí)空復(fù)雜度的分析 時(shí)間復(fù)雜度的分析 空間復(fù)雜度的分析 14 g 阿 N NqN 咖2尸 必 2 3 3 10 33 110 32 100 7 10 100 664 4+14 IODO loaoQ 10 32 1000 9966 99317 31623 lOCOOOO 13 100 10000 132377 1765

7、033 10COCOO lOCOOOOOO 17 316 100000 1660964 27588016 31622777 10000000000 20 1000 1000000 19931569 397267426 laDooaoooo lOOOQQaDOOOOO 1.T minutoe 2 hOuTfl 1.1 days 1.6 weeks 3S months 3years 3.1 docadfis 3J oemurtea we 函數(shù)增長(zhǎng)和運(yùn)行時(shí)間 引川劉汝保 序列和7 符小 QQoratons per secondss Ipmbhm sb I tvnqN secondsseconds 1

8、0inscontirtfunc 1q32linstantinstart weeksIhourshoursnever hourssxo 仇 ds孔8ndecodes BocondsinsXrftinctantwaakc 15 常見(jiàn)題型 Dynamic Programming （動(dòng) 態(tài)規(guī)劃） Greedy （貪心） Complete Search （窮舉） Flood Fill （種子填充） 16 常見(jiàn)題型 Shortest P a th （最短路徑） Recursive Search Techniques （回溯） Minimum Spanning Tree （最小 生成樹(shù)） Knapsack

9、（背包） 17 常見(jiàn)題型 Computational Geometry （計(jì)算幾何） Network Flow （網(wǎng)絡(luò)流） Eulerian Path （歐拉回路: Two-Dimensional Convex Hull （二維凸包） 19 BigNums （大數(shù)） Search （啟發(fā)式 常見(jiàn)題型 Heuristic 搜索） Approximate Search （近 師索） Ad Hoc Problems （雜題） 19 ga盼（總共2閥） 滕動(dòng)態(tài)規(guī)劃 金心 圖論 廿草幾何數(shù)學(xué)阿豊數(shù)麟柯 #也 2630 10 10 Ifi15436 47 旳占比削 12.75% 14. ns 4.9W 4

10、.9QX ?. 35% 1 7.35S 2L0弘 2.MM 23.04S 20 枚舉法 又叫窮舉法，它利用了計(jì)算機(jī)計(jì)算 速度快且準(zhǔn)確的特點(diǎn)，是最為樸索 和有效的一種算法。 不是辦法的辦法 但有時(shí)卻是最好的辦法 21 Pizza Any one? (ZOJ 1219) 題冃大意： 你需要為你和你的刖友們訂一個(gè)皮薩。 每個(gè)朋友都會(huì)告訴你他們想和不想放進(jìn)皮薩 里的東西。 你是否能訂一個(gè)皮薩，讓他滿足每個(gè)人 至少一個(gè)條件。 假設(shè)一共有16種東西可以放進(jìn)皮薩。 22 24 216 65536 足個(gè)對(duì)計(jì)算機(jī)彳H 小的數(shù) J 23 貪心法(Greedy) 枚舉法的時(shí)間效率很低，貪心法恰恰與英 相反。并1L貪

11、心法的程序也很好實(shí)現(xiàn)。 無(wú)數(shù)論文都指責(zé)貪心法往往得不到問(wèn)題的 絕壯高手與普通高于的差距所在。 矩陣胚理論(詳情請(qǐng)參考算法導(dǎo)論) 棧和隊(duì)列 棧：后進(jìn)先出(LIFO) 隊(duì)列：先進(jìn)先出(FIFO) 25 26 字符串的輸入與輸出 Z 在輸入數(shù)據(jù)達(dá)到iM時(shí)， cin. cout將比scanf, printf/H速應(yīng)匕何明顯 的劣勢(shì) / C+常用頭文件 或 哪種讀入吏快？ 字符串的讀入L r char s100;scanf(%s,s); string 0紺ing a; cin a; 排序 排序的種類(lèi)： 堆排序 桶排序 27 交換排序，選擇排序，插入排序, 希爾扌非序，快速排序，歸并排序, 用C+ +實(shí)現(xiàn)

12、排序 #include 數(shù)組a sort( a , a + 5 ); vector a sort( a. beginO , a. end(); 28 并査集 并查集是一種樹(shù)型的數(shù)據(jù)結(jié)構(gòu)，川 于處理一些不相交集合的合并問(wèn)題。 并查集的左耍操作有 1 合并兩個(gè)不和交集合 2 判斷兩個(gè)元素是否屬于同一個(gè)集合 3 路徑壓縮 29 P arity(ceoi99) 有一個(gè)01序歹1,長(zhǎng)度 = 1000000000見(jiàn) 沁有n條信息f每條信息的形式是一a b even/oddo表示第a位到第b位元素之間 的元素總和是偶數(shù)/奇數(shù)。 你的任務(wù)是對(duì)于這些給定的信息，輸出第 一個(gè)不正確的信息所在位置7。信息的數(shù) 目不

13、超過(guò)5000。 如果信息全部正確，即可以找到一個(gè)滿足 要求的01序列，那么輸出n。 P arity(ceot99) 從整個(gè)01序列肯定是無(wú)法入手的，丙為它 的長(zhǎng)度高達(dá)109。 從范圍比較小的n入手。也就是說(shuō)我們需要 對(duì)信息進(jìn)行一些特殊的處理。 a b even/odd,那么將元索匕指向a-l, 邊的權(quán) ffiteven/oddo 下而我們由樣例來(lái)說(shuō)明一下這個(gè)處理方法。 31 Parlty(ceoi99)(肖天) 建立sum數(shù)組 sumi表示從1到iZ和足奇(true)還是偶 (false) . sum0=falseo這棉題U中給的任意問(wèn)題(可b) 的答案都可以rnsumb xor sumal表

14、示。 開(kāi)始我們并不知ifisuml.n的值，不妨設(shè)為false,這時(shí)任意 sumaLsumb都是立的。對(duì)T毎對(duì)問(wèn)答(a.b,c)者*可以 知道sumbl xor suma-ll=cj|此把sumfb和sumal 聯(lián)系赴來(lái)。迖步操作町以用升住集完成，對(duì)問(wèn)答(a,b,c)如 果SLimalbsumb不屬于一個(gè)集介就把它們并起來(lái)，否則 如果sumFa-l xor sumb4個(gè)部分為false.則口J以確泄 sum數(shù)紐，利用sumi xor sumi-liiji求出制彳的藪字， 山于不同集合Z間沒(méi)右詢(xún)答出現(xiàn)，所以此數(shù)列是一町行解，證 呦算法正確。 32 堆（優(yōu)先隊(duì)列） 優(yōu)點(diǎn)： 動(dòng)態(tài)維護(hù)一組數(shù)據(jù)屮最小（

15、大）的一個(gè) 實(shí)現(xiàn)簡(jiǎn)單 數(shù)組維護(hù) 33 一個(gè)長(zhǎng)方形網(wǎng)格包含了n*rn塊地，毎塊地上ifii有1個(gè) 長(zhǎng)方體。每一個(gè)長(zhǎng)方形蓋住了一塊地，地的血積足1 平方英寸。相鄰的地上的長(zhǎng)方體2間沒(méi)冇空隙。場(chǎng) 大雨降臨了這個(gè)建筑物，在建筑物的某些區(qū)域有枳水 產(chǎn)生。 給各方格高度，求積水總量 34 分析 定義每塊地上的 -長(zhǎng)方休的高度稱(chēng)為原始高度 -積滿水時(shí)的水Iffi高度稱(chēng)為積水高度（咼于積水 高度的水一定會(huì)流走，低于積水高度的水一定 流不是） -積水高度與原始高度之差為積水深度 如果一個(gè)長(zhǎng)方體上不町能有積水，那么它 的積水高度就等于它的原始高度。 最外圈不能積水，積水高度等于原始高度 35 分析 由外而內(nèi)計(jì)算。

16、每次選取外圍的格子中積水高度 最低的一個(gè)格子X(jué),考慮它周用所有在網(wǎng)格內(nèi)部的 格fy -想彖不斷的往X和y里注水，但是X的積水高度固定（想 彖該高度處有一個(gè)小孔），因此 -如果y的原始高度不小丁-X的積水高度，那么它的積水 高度就是它的原始高度 -如果y的原始高度小丁-X的積水高度，那么它的積水高 度就等于X的積水高度 每次用堆取出X進(jìn)行計(jì)算，O（mnlogmn）o 36 哈希表(Hash) 理論上查找速度最快的數(shù)據(jù)結(jié)構(gòu)之一 缺點(diǎn)： 需要犬量的內(nèi)存 需要構(gòu)造Key 37 Hash表的實(shí)現(xiàn) 數(shù)組 沖突解決法 開(kāi)散列法 閉散列法 C+ sgi sti 實(shí)現(xiàn) 38 Hash Key的選取 數(shù)值： 方法

17、一：直接取余數(shù)（一般選取質(zhì)數(shù)M垠為除 數(shù)） 方法二：平方取屮法，即汁算關(guān)鍵值的平方, 再取屮間位形成一個(gè)人小為丫的表 是多少? 40 39 字符串: 方法一: 折疊法: 方法二: 即把所佇字符的ASCII碼加起來(lái) ELFhash 函數(shù) int ELFhash( char* key ) unsigned int h 0; while( *key ) h = ( h 4 ) + *key+; unsigned long g = h h return h % M; 二分搜索樹(shù) 普通的二分搜索樹(shù) 時(shí)1可復(fù)雜度：(log, n) 缺點(diǎn)： 容易出現(xiàn)不平衡的情況 AVL Tree , Splay tree

18、,紅黑樹(shù) 樹(shù)堆(Treap) Trea p = Tree + hea p 每次插入/刪除結(jié)點(diǎn)的時(shí)候，給結(jié)點(diǎn)隨機(jī) 分配一個(gè)優(yōu)先級(jí)，止Trea P關(guān)于優(yōu)先級(jí)形 成個(gè)堆的同時(shí)，關(guān)于關(guān)鍵碼形成BST 跳躍表、B樹(shù) 跳躍表(Skiplists) Srch path MIL 25 r- 刁 7| -S3-: E-S3- 2? oHgigl iir, 17 ic inserted qfib his&Jig updar ptnnrers w gf sa 3HZ0 IgR-rnR-l rq-|2fira-t 43 線段樹(shù) 在一類(lèi)問(wèn)題中，我們需耍經(jīng)常處理 町以映射在一個(gè)坐標(biāo)軸上的一些固定線 段，例如說(shuō)映射在OX軸上的線段。IIT- 線段是可以互相覆蓋的，有時(shí)需要?jiǎng)討B(tài) 地取線段的并，例如取得并區(qū)間