Acm競賽常用算法與數(shù)據(jù)結構.

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

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

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

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

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

6、？ ？ -歷屈國家集訓隊論文 12 網(wǎng)絡資源 httD：/acmzjueducn httD：/acmtimusru http:/acmsqunj httD：/acedeloscom/usacogate http:/ http:/wwwoibhorq/bbs/index，Dhp 13 時空復雜度的分析 時間復雜度的分析 空間復雜度的分析 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ù)增長和運行時間 引川劉汝保 序列和7 符小 QQoratons per secondss Ipmbhm sb I tvnqN secondsseconds 1

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

9、（背包） 17 常見題型 Computational Geometry （計算幾何） Network Flow （網(wǎng)絡流） Eulerian Path （歐拉回路: Two-Dimensional Convex Hull （二維凸包） 19 BigNums （大數(shù)） Search （啟發(fā)式 常見題型 Heuristic 搜索） Approximate Search （近 師索） Ad Hoc Problems （雜題） 19 ga盼（總共2閥） 滕動態(tài)規(guī)劃 金心 圖論 廿草幾何數(shù)學阿豊數(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 枚舉法 又叫窮舉法，它利用了計算機計算 速度快且準確的特點，是最為樸索 和有效的一種算法。 不是辦法的辦法 但有時卻是最好的辦法 21 Pizza Any one? (ZOJ 1219) 題冃大意： 你需要為你和你的刖友們訂一個皮薩。 每個朋友都會告訴你他們想和不想放進皮薩 里的東西。 你是否能訂一個皮薩，讓他滿足每個人 至少一個條件。 假設一共有16種東西可以放進皮薩。 22 24 216 65536 足個對計算機彳H 小的數(shù) J 23 貪心法(Greedy) 枚舉法的時間效率很低，貪心法恰恰與英 相反。并1L貪

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

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

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

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

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

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

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

18、,紅黑樹 樹堆(Treap) Trea p = Tree + hea p 每次插入/刪除結點的時候，給結點隨機 分配一個優(yōu)先級，止Trea P關于優(yōu)先級形 成個堆的同時，關于關鍵碼形成BST 跳躍表、B樹 跳躍表(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 線段樹 在一類問題中，我們需耍經(jīng)常處理 町以映射在一個坐標軸上的一些固定線 段，例如說映射在OX軸上的線段。IIT- 線段是可以互相覆蓋的，有時需要動態(tài) 地取線段的并，例如取得并區(qū)間