ACM計劃(針對大一)1

1、濰坊學院濰坊學院 ACM 集訓計劃集訓計劃 鑒于初次接觸編程和鑒于初次接觸編程和 ACM 以及你們的現(xiàn)狀，第一步要語法過關。以及你們的現(xiàn)狀，第一步要語法過關。 要求：要求： 1、 熟練掌握基本控制結構、數(shù)組、函數(shù)、結構體、指針等。 2、 熟練掌握庫函數(shù)（string.h,stdlib.h,ctype.h 等）的使用。 3、 養(yǎng)成良好的編程習慣。 4、 不會的查百度、谷歌，注重細節(jié)。 方式：方式： 1、 完成山東理工大學 online judge（http:/ 右的題目?；蛘呤呛贾蓦娮涌萍即髮W online judge（http:/ 認為自己已經(jīng)熟練掌握基本認為自己已經(jīng)熟練掌握基本 C 語言的用

2、法的同學，就可以進行下面的系統(tǒng)學習了！語言的用法的同學，就可以進行下面的系統(tǒng)學習了！ 下面給出的題目共計下面給出的題目共計 560560 道，去掉重復的也有近道，去掉重復的也有近 500500 題，題， 作為作為 ACMerACMer TrainingTraining Step1Step1，用，用 1 1 年到年到 1 1 年半年時間完成。年半年時間完成。 打牢基礎，厚積薄發(fā)。打牢基礎，厚積薄發(fā)。 第一部分：第一部分：( (算法競賽入門經(jīng)典算法競賽入門經(jīng)典) ) 語言篇（前 4 章）簡要介紹了 C 語言的知識，有針對性的講解了 C 語言在程序 設計競賽中常見的應用，這些是一般 C 語言書中不涉

3、及的，對競賽入門是大有 幫助。雖然這一部分從內(nèi)容設計上看是針對零編程基礎的讀者，但是作為 C 語 言入門顯然是不足夠的、并且跨度較大。 /index.php?option=com_onlinejudge&Itemid=8& category=94 第二部分：第二部分： 算法篇（58 章） ，從簡單的編程題目開始，引入數(shù)據(jù)結構和算法的基礎知識。 并且介紹了如何在 Online Judge 系統(tǒng)（OJ）上做題，進而引導讀者開始編程訓 練，進入程序設計競賽的領域。 第 5 章：基礎題目 57 道題。 第 6 章 http:/uva.onlinejud

4、/index.php?option=com_onlinejudge&Itemid=8&category=95 第 6 章：基礎數(shù)據(jù)結構 32 道題。 /index.php?option=com_onlinejudge&Itemid=8&category=102 第 7 章：暴力 68 道題。 /index.php?option=com_onlinejudge&Itemid=8&category=106 第 8 章，算法設計， 34 道題。 http:/uva.onlinejudge.

5、org/index.php?option=com_onlinejudge&Itemid=8&category=113 第三部分：第三部分： 競賽篇（911 章） ，在第 2 部分的基礎上，介紹了一些競賽常用的基礎知識和思路，進一 步練習編程能力，培養(yǎng)求解問題的建模能力。 第 9 章：動態(tài)規(guī)劃， 60 道題。 /index.php?option=com_onlinejudge&Itemid=8&category=114 第 10 章：數(shù)學方法 62 道題。 /index.php?option=co

6、m_onlinejudge&Itemid=8&category=115 第 11 章：圖論模型 26 道題。 /index.php?option=com_onlinejudge&Itemid=8&category=116 第四部分：（挑戰(zhàn)編程）第四部分：（挑戰(zhàn)編程） 第一章：入門 1.1 PC/UVa 題號: 110101/100 The 3n+1 problem （3n+1 問題） 1.2 PC/UVa 題號: 110102/10189 Minesweeper （掃雷） 1.3 PC/UVa 題號: 110103/10137 The Trip

7、 （旅行） 1.4 PC/UVa 題號: 110104/706 LC-Display （液晶顯示屏） 1.5 PC/UVa 題號: 110105/10267 Graphical Editor （圖形化編輯器） 1.6 PC/UVa 題號: 110106/10033 Interpreter （解釋器） 1.7 PC/UVa 題號: 110107/10196 Check the Check （將軍） 1.8 PC/UVa 題號: 110108/10142 Australian Voting （澳大利亞投票） 第二章：數(shù)據(jù)結構 2.1 PC/UVa 題號: 110201/10038 Jolly Ju

8、mpers （快樂的跳躍者） 2.2 PC/UVa 題號: 110202/10315 Poker Hands （撲克牌型） 2.3 PC/UVa 題號: 110203/10050 Hartals （罷工） 2.4 PC/UVa 題號: 110204/843 Crypt Kicker （解密） 2.5 PC/UVa 題號: 110205/10205 Stack em Up （完美洗牌術） 2.6 PC/UVa 題號: 110206/10044 Erdos Numbers （Erdos 數(shù)） 2.7 PC/UVa 題號: 110207/10258 Contest Scoreboard （比賽計分板

9、） 2.8 PC/UVa 題號: 110208/10149 Yahtzee （Yahtzee 游戲） 第三章：字符串 3.1 PC/UVa 題號: 110301/10082 WERTYU （WERTYU 鍵盤） 3.2 PC/UVa 題號: 110302/10010 Wheres Waldorf?（尋找單詞） 3.3 PC/UVa 題號: 110303/10252 Common Permutation （公共排列） 3.4 PC/UVa 題號: 110304/850 Crypt Kicker II （解密 II） 3.5 PC/UVa 題號: 110305/10188 Automated Ju

10、dge Script （自動評測腳本） 3.6 PC/UVa 題號: 110306/10132 File Fragmentation （文件碎片） 3.7 PC/UVa 題號: 110307/10150 Doublets （Doublets 序列） 3.8 PC/UVa 題號: 110308/848 Fmt （Fmt 程序） 第四章：排序 4.1 PC/UVa 題號: 110401/10041 Vitos Family （Vito 家族） 4.2 PC/UVa 題號: 110402/120 Stacks of Flapjacks （煎餅堆） 4.3 PC/UVa 題號: 110403/1003

11、7 Bridge （過橋） 4.4 PC/UVa 題號: 110404/10191 Longest Nap （最長打盹時間） 4.5 PC/UVa 題號: 110405/10026 Shoemakers Problem （鞋匠的煩惱） 4.6 PC/UVa 題號: 110406/10138 CDVII （CDVII 高速公路） 4.7 PC/UVa 題號: 110407/10152 ShellSort （龜殼排序） 4.8 PC/UVa 題號: 110408/10194 Football (aka Soccer) （足球） 第五章：算術與代數(shù) 5.1 PC/UVa 題號: 110501/100

12、35 Primary Arithmetic （小學生算術） 5.2 PC/UVa 題號: 110502/10018 Reverse and Add （反轉相加） 5.3 PC/UVa 題號: 110503/701 The Archeologists Dilemma （考古學家的煩 惱） 5.4 PC/UVa 題號: 110504/10127 Ones （僅由 1 組成的數(shù)） 5.5 PC/UVa 題號: 110505/847 A Multiplication Game （乘法游戲） 5.6 PC/UVa 題號: 110506/10105 Polynomial Coefficients （多項式

13、系數(shù)） 5.7 PC/UVa 題號: 110507/10077 The Stern-Brocot Number System （Stern- Brocot 代數(shù)系統(tǒng)） 5.8 PC/UVa 題號: 110508/10202 Pairsumonious Numbers （兩兩之和） 第六章：組合數(shù)學 6.1 PC/UVa 題號: 110601/10183 How Many Fibs? （斐波那契計數(shù)） 6.2 PC/UVa 題號: 110602/10213 How Many Pieces of Land? （土地分割） 6.3 PC/UVa 題號: 110603/10198 Counting （

14、數(shù)數(shù)） 6.4 PC/UVa 題號: 110604/10157 Expressions （括號表達式） 6.5 PC/UVa 題號: 110605/10247 Complete Tree Labeling （完全樹標號） 6.6 PC/UVa 題號: 110606/10254 The Priest Mathematician （牧師數(shù)學家） 6.7 PC/UVa 題號: 110607/10049 Self-describing Sequence （自描述序列） 6.8 PC/UVa 題號: 110608/846 Steps （數(shù)軸行走） 第七章：數(shù)論 7.1 PC/UVa 題號: 110701

15、/10110 Light, More Light （開燈與關燈） 7.2 PC/UVa 題號: 110702/10006 Carmichael Numbers （Carmichael 數(shù)） 7.3 PC/UVa 題號: 110703/10104 Euclid Problem （歐幾里德問題） 7.4 PC/UVa 題號: 110704/10139 Factovisors （階乘與整除） 7.5 PC/UVa 題號: 110705/10168 Summation of Four Primes （四素數(shù)之和） 7.6 PC/UVa 題號: 110706/10042 Smith Numbers （S

16、mith 數(shù)） 7.7 PC/UVa 題號: 110707/10090 Marbles （彈珠） 7.8 PC/UVa 題號: 110708/10089 Repackaging （重新打包） 第八章：回溯法 8.1 PC/UVa 題號: 110801/861 Little Bishops （棋盤上的象） 8.2 PC/UVa 題號: 110802/10181 15-Puzzle Problem （15 數(shù)碼游戲） 8.3 PC/UVa 題號: 110803/10128 Queue （隊伍） 8.4 PC/UVa 題號: 110804/10160 Servicing Stations （服務站）

17、 8.5 PC/UVa 題號: 110805/10032 Tug of War （拔河） 8.6 PC/UVa 題號: 110806/10001 Garden of Eden （伊甸園） 8.7 PC/UVa 題號: 110807/704 Colour Hash （色彩繽紛游戲） 8.8 PC/UVa 題號: 110808/10270 Bigger Square Please. （拼接正方形） 第九章：圖遍歷 9.1 PC/UVa 題號: 110901/10004 Bicoloring （雙著色） 9.2 PC/UVa 題號: 110902/10067 Playing With Wheels

18、（擺弄輪子） 9.3 PC/UVa 題號: 110903/10099 The Tourist Guide （導游） 9.4 PC/UVa 題號: 110904/705 Slash Maze （斜線迷宮） 9.5 PC/UVa 題號: 110905/10029 Edit Step Ladders （遞變階梯） 9.6 PC/UVa 題號: 110906/10051 Tower of Cubes （立方體之塔） 9.7 PC/UVa 題號: 110907/10187 From Dusk till Dawn （從黃昏到拂曉） 9.8 PC/UVa 題號: 110908/10276 Hanoi Tow

19、er Troubles Again! （漢諾塔卷土 重來?。?第十章：圖算法 10.1 PC/UVa 題號: 111001/10034 Freckles （斑點） 10.2 PC/UVa 題號: 111002/10054 The Necklace （項鏈） 10.3 PC/UVa 題號: 111003/10278 Fire Station （消防站） 10.4 PC/UVa 題號: 111004/10039 Railroads （鐵路） 10.5 PC/UVa 題號: 111005/10158 War （戰(zhàn)爭） 10.6 PC/UVa 題號: 111006/10199 Tourist Guid

20、e （導游） 10.7 PC/UVa 題號: 111007/10249 The Grand Dinner （豐盛的晚餐） 10.8 PC/UVa 題號: 111008/10092 The Problem With the Problem Setter （命 題者的難題） 第十一章：動態(tài)規(guī)劃 11.1 PC/UVa 題號: 111101/10131 Is Bigger Smarter? （越大越聰明？） 11.2 PC/UVa 題號: 111102/10069 Distinct Subsequences （不同的子序列） 11.3 PC/UVa 題號: 111103/10154 Weights

21、and Measures （重量和力量） 11.4 PC/UVa 題號: 111104/116 Unidirectional TSP （單向旅行商問題） 11.5 PC/UVa 題號: 111105/10003 Cutting Sticks （切割木棍） 11.6 PC/UVa 題號: 111106/10261 Ferry Loading （渡船裝載） 11.7 PC/UVa 題號: 111107/10271 Chopsticks （筷子） 11.8 PC/UVa 題號: 111108/10201 Adventures in Moving: Part IV （搬家大冒 險：第四部） 第十二章：

22、網(wǎng)格 12.1 PC/UVa 題號: 111201/10161 Ant on a Chessboard （棋盤上的螞蟻） 12.2 PC/UVa 題號: 111202/10047 The Monocycle（獨輪車） 12.3 PC/UVa 題號: 111203/10159 Star （六角星） 12.4 PC/UVa 題號: 111204/10182 Bee Maja （蜜蜂 Maja） 12.5 PC/UVa 題號: 111205/707 Robbery （搶劫） 12.6 PC/UVa 題號: 111206/10177 (2/3/4)-D Sqr/Rects/Cubes/Boxes? （

23、2/3/4-維立方體？） 12.7 PC/UVa 題號: 111207/10233 Dermuba Triangle （Dermuba 三角） 12.8 PC/UVa 題號: 111208/10075 Airlines （航線） 第十三章：幾何 13.1 PC/UVa 題號: 111301/10310 Dog and Gopher （狗拿地鼠） 13.2 PC/UVa 題號: 111302/10180 Rope Crisis in Ropeland! （繩子王國的危 機！） 13.3 PC/UVa 題號: 111303/10195 The Knights of the Round Table

24、（圓桌騎 士） 13.4 PC/UVa 題號: 111304/10136 Chocolate Chip Cookies （巧克力片餅干） 13.5 PC/UVa 題號: 111305/10167 Birthday Cake （生日蛋糕） 13.6 PC/UVa 題號: 111306/10215 The Largest/Smallest Box. （最大/最小 的盒子） 13.7 PC/UVa 題號: 111307/10209 Is This Integration? （需要積分嗎？） 13.8 PC/UVa 題號: 111308/10012 How Big Is It? （它有多大？） 第十四

25、章：計算幾何 14.1 PC/UVa 題號: 111401/10135 Herding Frosh （新生集會） 14.2 PC/UVa 題號: 111402/10245 The Closest Pair Problem （最近點對問題） 14.3 PC/UVa 題號: 111403/10043 Chainsaw Massacre （電鋸驚魂） 14.4 PC/UVa 題號: 111404/10084 Hotter Colder （冷熱游戲） 14.5 PC/UVa 題號: 111405/10065 Useless Tile Packers （沒用的瓷磚打包公 司） 14.6 PC/UVa 題

26、號: 111406/849 Radar Tracking （雷達追蹤） 14.7 PC/UVa 題號: 111402/10088 Trees on My Island （島上的樹） 14.8 PC/UVa 題號: 111408/10117 Nice Milk （美味的牛奶） 第五部分：（第五部分：（USACOUSACO） http:/ （USACO 97 道題） 1 Chapter1-Getting started(入門) 21 道題 1.1 Section 1.0 1.2 Section 1.1 1.3 Section 1.2 1.4 Section 1.3 1.5 Section 1.4

27、1.6 Section 1.5 2 Chapter2-Bigger Challenges(更大的挑戰(zhàn)) 19 道題 2.1 Section 2.1 2.2 Section 2.2 2.3 Section 2.3 2.4 Section 2.4 3 Chapter3-Techniques more subtle(更微妙的技術) 21 道題 3.1 Section 3.1 3.2 Section 3.2 3.3 Section 3.3 3.4 Section 3.4 4 Chapter4-Advanced algorithms and difficult drills(高級算法與困難 的習題) 1

28、5 道題 4.1 Section 4.1 4.2 Section 4.2 4.3 Section 4.3 4.4 Section 4.4 5 Chapter5-Serious challenges(嚴峻的挑戰(zhàn)) 18 道題 5.1 Section 5.1 5.2 Section 5.2 5.3 Section 5.3 5.4 Section 5.4 5.5 Section 5.5 6 Chapter6-Contest Practice(大賽的實踐) 3 道題 6.1 Section 6.1 經(jīng)過經(jīng)過 Step1-500Step1-500 題訓練，接下來可以開始題訓練，接下來可以開始 Step2

29、-500Step2-500 題，題， 包括包括 POJPOJ 訓練計劃的訓練計劃的 298298 題和題和 SGUSGU 前兩章前兩章 200200 題。需要題。需要 1-11-1 年半時間繼續(xù)提高解決問題和編碼實現(xiàn)能力，加油年半時間繼續(xù)提高解決問題和編碼實現(xiàn)能力，加油 ACMerACMer！ 任重道遠！任重道遠！ 集訓第一天POJ 純水題 = =： Like the following 20172017 12181218 20002000 10461046 12181218 10031003 10041004 10051005 10081008 1013(1013(枚舉枚舉) ) 12071

30、207 15521552 21052105 23882388 13161316 24992499 30063006（篩法求素數(shù)）（篩法求素數(shù)） 第一階段第一階段 初級：第初級：第 1 周周-第第 4 周周 項目項目時間時間必做題目必做題目 枚舉poj1753,poj2965基基 本本貪心 第 1 周 poj1328,poj2109,poj2586 分治法poj2524 遞推poj2506 構造法poj3295 算算 法法 模擬法poj1068,poj2632,poj1573, poj2993,poj2996 圖的深度優(yōu)先遍歷和廣度 優(yōu)先遍歷 poj3278, poj2049, poj3083

31、最短路徑算法poj1860,poj3259,poj1062, poj2253,poj1125,poj2240 最小生成樹算法poj1789,poj2485,poj1258, poj3026 拓撲排序poj1094, poj3267，poj3687 二分圖的最大匹配poj3041,poj3020 圖圖 算算 法法 最大流的增廣路算法 第 1 周 poj1459,poj3436 串poj1035,poj3080,poj1936 排序poj2388,poj2299 簡單并查集的應用poj1611 哈希表和二分查找等高效 查找法 poj3349,poj3274,POJ2151 ,poj1840,poj

32、2002,poj2503 哈夫曼樹poj3253 堆,優(yōu)先隊列poj2442, poj1442 數(shù)數(shù) 據(jù)據(jù) 結結 構構 trie 樹 第 2 周 poj2513, poj2418 深度優(yōu)先搜索poj2488,poj3083,poj3009, poj1321,poj2251 簡簡 單單 搜搜 廣度優(yōu)先搜索 第 2 周 poj3278,poj1426,poj3126, poj3087.poj3414索索 簡單搜索技巧和剪枝poj2531,poj1416,poj2676, poj1129 背包問題poj1837,poj1276動動 態(tài)態(tài) 規(guī)規(guī) 劃劃 型如下表的簡單 DP 第 3 周 poj3267,

33、poj1836,poj1260, poj2533,poj3176,poj1080, poj1159 組合數(shù)學POJ3252,poj1850,poj1019 ,poj1942 數(shù)論poj2635, poj3292,poj1845,poj2115 數(shù)數(shù) 學學 計算方法 第 3 周 poj3273,poj3258,poj1905, poj3122 幾何公式poj1265(pick 定理) 叉積和點積的運用poj2031,poj1039 多邊型的簡單算法和相關 判定 poj1408,poj1584 計計 算算 幾幾 何何 學學凸包 第 4 周 poj2187,poj1113 第二階段第二階段 中級：第

34、中級：第 4 周周-第第 9 周周 項目項目時間時間必做題目必做題目 C+的標準模版庫的應用poj3096,poj3007基基 本本 算算 法法 較為復雜的模擬題的訓練 第 4 周 poj3393,poj1472,poj3371, poj1027,poj2706 圖圖 算算 差分約束系統(tǒng)的建立和求 解 第 5 周poj1201,poj2983, poj3159 poj1275, poj1364 最小費用最大流poj2516, poj2195, poj3422 雙連通分量poj2942，poj3694 強連通分支及其縮點poj2186, poj3592, poj3114 圖的割邊和割點poj33

35、52 法法 最小割模型poj3308, poj3155（偏難） KM 算法(最大權/最小權）poj2195, poj2400, poj3686 線段樹poj2528,poj2828,poj2777, poj2886,poj2750 靜態(tài)二叉檢索樹,平衡樹 treap,splay poj2482,poj2352, poj2892 poj3468, 樹狀樹組poj1195,poj3321 RMQpoj3264,poj3368 并查集的高級應用poj1703,2492 數(shù)數(shù) 據(jù)據(jù) 結結 構構 KMP 算法 第 6 周 poj1961,poj2406 最優(yōu)化剪枝和可行性剪枝poj1699 搜索的技巧和

36、優(yōu)化poj3411,poj1724 搜搜 索索 記憶化搜索 第 7 周 poj3373,poj1691 較為復雜的動態(tài)規(guī)劃poj1191,poj1054,poj3280, poj2029,poj2948,poj1925, poj3034 記錄狀態(tài)的動態(tài)規(guī)劃poj3254,poj2411,poj1185 動動 態(tài)態(tài) 規(guī)規(guī) 劃劃樹型動態(tài)規(guī)劃 第 7 周 poj2057,poj1947,poj2486, poj3140 組合數(shù)學,polya 定理,置 換群 poj1286,poj2409,poj3270, poj1026 高斯消元法poj2947,poj1487, poj2065,poj1166,p

37、oj1222 概率問題poj3071,poj3440 GCD、擴展的歐幾里德poj1061, poj2891,poj3101 poj2115 計算方法(矩陣、三分等)poj2976,poj3150,poj3422, poj3070, poj3301 隨機化算法poj3318,poj2454 數(shù)數(shù) 學學 雜題 第 8 周 poj1870,poj3296,poj3286, poj1095 坐標離散化 poj1151 掃描線算法poj1765,poj1177,poj1151, poj3277,poj2280,poj3004 多邊形的核poj3130,poj3335 計計 算算 幾幾 何何 學學 幾何

38、工具的綜合應用 第 9 周 poj1819,poj1066,poj2043, poj3227,poj2165,poj3429 第三階段第三階段 高級：第高級：第 10 周周-第第 18 周周 項目項目時間時間必做題目必做題目 代碼快速寫成poj2525,poj1684,poj1421, poj1048,poj2050,poj3306 基基 本本 算算 法法 保證正確性和高效性 第 10 周 poj3434 圖圖 算算 度限制最小生成樹和第 K 最短路,分數(shù)規(guī)劃 第 10-11 周poj1639, poj3621, poj2976 poj3255，poj2513，poj24 49 最短路,最小生成樹,二分 圖,最大流問