acm常用演算法

⑴ acm必備知識都有哪些

備戰ACM資料
一：知識點
數據結構：
1，單，雙鏈表及循環鏈表
2，樹的表示與存儲，二叉樹（概念，遍歷）二叉樹的
應用（二叉排序樹，判定樹，博弈樹，解答樹等）
3，文件操作（從文本文件中讀入數據並輸出到文本文
件中）
4，圖（基本概念，存儲結構，圖的運算）
數學知識
1，離散數學知識的應用（如排列組合、簡單的圖論，數
理邏輯）
2，數論知識
3，線性代數
4，組合代數
5，計算幾何
二 演算法
1，排序演算法（冒拋法，插入排序，合並排序，快速排
序，堆排序）
2，查找（順序查找，二分發）
3，回溯演算法
4，遞歸演算法
5，分治演算法
6，模擬法
7，貪心法
8，簡單搜索演算法（深度優先，廣度優先），搜索中的
剪枝，A*演算法
9，動態規劃的思想及基本演算法
10，高精度運算
三、ACM競賽的題型分析
競賽的程序設計一般只有16種類型，它們分別是：
Dynamic Programming （動態規劃）
Greedy （貪心演算法）
Complete Search （窮舉搜索）
Flood Fill （不知該如何翻譯）
Shortest Path （最短路徑）
Recursive Search Techniques （回溯搜索技術）
Minimum Spanning Tree （最小生成樹）
Knapsack （背包問題）
Computational Geometry (計算幾何學)
Network Flow （網路流）
Eulerian Path （歐拉迴路）
Two-Dimensional Convex Hull （不知如何翻譯）
BigNums （大數問題）
Heuristic Search （啟發式搜索）
Approximate Search （近似搜索）
Ad Hoc Problems （雜題）
四 ACM競賽參考書
《實用演算法的分析與程序設計》 （吳文虎，王建德著，電子工業出版社，競賽類的黑寶書）
《青少年國際和全國信息學（計算機）奧林匹克競賽指導）――組合數學的演算法
和程序設計》（吳文虎，王建德著，清華大學出版社，參加競賽組合數學必學）
《計算機演算法設計與分析》 （王曉東編著，最好的數據結構教材）
《數據結構與演算法》 （傅清祥，王曉東編著，我所見過的最好的演算法教材）
《信息學奧林匹克競賽指導――1997-1998競賽試題解析》（吳文虎，王建德著，清華大學出版社）
《計算機程序設計技巧》 D.E.Kruth著，演算法書中最著名的《葵花寶典》，大師的作品，難度大）
《計算幾何》周陪德著
《ACM國際大學生程序設計競賽試題與解析（一）》 （吳文虎著，清華大學出版社）
《數學建模競賽培訓教材》 共三本 葉其孝主編
《數學模型》 第二版 姜啟源
《隨機規劃》
《模糊數學》
《數學建模入門》 徐全智
《計算機演算法設計與分析》 國防科大
五 常見的幾個網上題庫
常用網站：
1）信息學初學者之家：http://oibh.ioiforum.org/
（2）大榕樹編程世界：http://www.fjsdfz.org/~drs/program/default.asp
（3）中國教育曙光網：http://www.chinaschool.org/aosai/
（4）福建信息學奧林匹克：http://www.cfcs.com.cn/fjas/index.htm
（5）第20屆全國青少年信息學奧林匹克競賽：http://www.noi2003.org/
（6）第15屆國際青少年信息學奧林匹克競賽：http://www.ioi2003.org/
（7）全美計算機奧林匹克競賽：http://ace.delos.com/usacogate
（8）美國信息學奧林匹克競賽官方網站：http://www.usaco.org/
（9）俄羅斯Ural州立大學：http://acm.timus.ru/
（10）西班牙Valladolid大學：http://acm.uva.es/problemset
（11）ACM-ICPC：http://icpc.baylor.e/icpc/
（12）北京大學：http://acm.pku.e.cn/JudgeOnline/index.acm
（13）浙江大學：http://acm.zju.e.cn/
（14）IOI：http://olympiads.win.tue.nl/ioi/
（15）2003年江蘇省信息學奧林匹克競賽夏令營：http://jsoi.czyz.com.cn
（16）http://acm.zju.e.cn
（17）http://acm.zsu.e.cn
（18）www.shumo.com
（19）http://www.bepark.com/downldmanag/index.asp
（20）http://www.yh01.com colin_fox/colin_fox
五 如何備戰ACM/ICPC
1，個人准備（演算法書，習題集，網上做題和討論）
2，1000題=亞洲冠軍=世界決賽
3，做好資料收集和整理工作

⑵ ACM入門學什麼

初學者建議購買，《演算法競賽入門經典》 劉汝佳作，十分好，在深入可以是他的另外一本，黑書，《演算法藝術與信息學競賽》。
計劃：
ACM的演算法（覺得很好，有層次感）POJ上的一些水題(可用來練手和增加自信)
(poj3299,poj2159,poj2739,poj1083,poj2262,poj1503,poj3006,poj2255,poj3094)
初期:
一.基本演算法:
(1)枚舉. (poj1753,poj2965)
(2)貪心(poj1328,poj2109,poj2586)
(3)遞歸和分治法.
(4)遞推.
(5)構造法.(poj3295)
(6)模擬法.(poj1068,poj2632,poj1573,poj2993,poj2996)
二.圖演算法:
(1)圖的深度優先遍歷和廣度優先遍歷.
(2)最短路徑演算法(dijkstra,bellman-ford,floyd,heap+dijkstra)
(poj1860,poj3259,poj1062,poj2253,poj1125,poj2240)
(3)最小生成樹演算法(prim,kruskal)
(poj1789,poj2485,poj1258,poj3026)
(4)拓撲排序 (poj1094)
(5)二分圖的最大匹配 (匈牙利演算法) (poj3041,poj3020)
(6)最大流的增廣路演算法(KM演算法). (poj1459,poj3436)
三.數據結構.
(1)串 (poj1035,poj3080,poj1936)
(2)排序(快排、歸並排(與逆序數有關)、堆排) (poj2388,poj2299)
(3)簡單並查集的應用.
(4)哈希表和二分查找等高效查找法(數的Hash,串的Hash)
(poj3349,poj3274,POJ2151,poj1840,poj2002,poj2503)
(5)哈夫曼樹(poj3253)
(6)堆
(7)trie樹(靜態建樹、動態建樹) (poj2513)
四.簡單搜索
(1)深度優先搜索 (poj2488,poj3083,poj3009,poj1321,poj2251)
(2)廣度優先搜索(poj3278,poj1426,poj3126,poj3087.poj3414)
(3)簡單搜索技巧和剪枝(poj2531,poj1416,poj2676,1129)
五.動態規劃
(1)背包問題. (poj1837,poj1276)
(2)型如下表的簡單DP(可參考lrj的書 page149):
1.E[j]=opt{D[i]+w(i,j)} (poj3267,poj1836,poj1260,poj2533)
2.E[i,j]=opt{D[i-1,j]+xi,D[i,j-1]+yj,D[i-1][j-1]+zij} (最長公共子序列)
(poj3176,poj1080,poj1159)
3.C[i,j]=w[i,j]+opt{C[i,k-1]+C[k,j]}.(最優二分檢索樹問題)
六.數學
(1)組合數學:
1.加法原理和乘法原理.
2.排列組合.
3.遞推關系.
(POJ3252,poj1850,poj1019,poj1942)
(2)數論.
1.素數與整除問題
2.進制位.
3.同餘模運算.
(poj2635, poj3292,poj1845,poj2115)
(3)計算方法.
1.二分法求解單調函數相關知識.(poj3273,poj3258,poj1905,poj3122)
七.計算幾何學.
(1)幾何公式.
(2)叉積和點積的運用(如線段相交的判定,點到線段的距離等). (poj2031,poj1039)
(3)多邊型的簡單演算法(求面積)和相關判定(點在多邊型內,多邊型是否相交)
(poj1408,poj1584)
(4)凸包. (poj2187,poj1113)
中級:
一.基本演算法:
(1)C++的標准模版庫的應用. (poj3096,poj3007)
(2)較為復雜的模擬題的訓練(poj3393,poj1472,poj3371,poj1027,poj2706)
二.圖演算法:
(1)差分約束系統的建立和求解. (poj1201,poj2983)
(2)最小費用最大流(poj2516,poj2516,poj2195)
(3)雙連通分量(poj2942)
(4)強連通分支及其縮點.(poj2186)
(5)圖的割邊和割點(poj3352)
(6)最小割模型、網路流規約(poj3308, )
三.數據結構.
(1)線段樹. (poj2528,poj2828,poj2777,poj2886,poj2750)
(2)靜態二叉檢索樹. (poj2482,poj2352)
(3)樹狀樹組(poj1195,poj3321)
(4)RMQ. (poj3264,poj3368)
(5)並查集的高級應用. (poj1703,2492)
(6)KMP演算法. (poj1961,poj2406)
四.搜索
(1)最優化剪枝和可行性剪枝
(2)搜索的技巧和優化 (poj3411,poj1724)
(3)記憶化搜索(poj3373,poj1691)
五.動態規劃
(1)較為復雜的動態規劃(如動態規劃解特別的施行商問題等)
(poj1191,poj1054,poj3280,poj2029,poj2948,poj1925,poj3034)
(2)記錄狀態的動態規劃. (POJ3254,poj2411,poj1185)
(3)樹型動態規劃(poj2057,poj1947,poj2486,poj3140)
六.數學
(1)組合數學:
1.容斥原理.
2.抽屜原理.
3.置換群與Polya定理(poj1286,poj2409,poj3270,poj1026).
4.遞推關系和母函數.
(2)數學.
1.高斯消元法(poj2947,poj1487, poj2065,poj1166,poj1222)
2.概率問題. (poj3071,poj3440)
3.GCD、擴展的歐幾里德(中國剩餘定理) (poj3101)
(3)計算方法.
1.0/1分數規劃. (poj2976)
2.三分法求解單峰(單谷)的極值.
3.矩陣法(poj3150,poj3422,poj3070)
4.迭代逼近(poj3301)
(4)隨機化演算法(poj3318,poj2454)
(5)雜題.
(poj1870,poj3296,poj3286,poj1095)
七.計算幾何學.
(1)坐標離散化.
(2)掃描線演算法(例如求矩形的面積和周長並,常和線段樹或堆一起使用).
(poj1765,poj1177,poj1151,poj3277,poj2280,poj3004)
(3)多邊形的內核(半平面交)(poj3130,poj3335)
(4)幾何工具的綜合應用.(poj1819,poj1066,poj2043,poj3227,poj2165,poj3429)
高級:
一.基本演算法要求:
(1)代碼快速寫成,精簡但不失風格
(poj2525,poj1684,poj1421,poj1048,poj2050,poj3306)
(2)保證正確性和高效性. poj3434
二.圖演算法:
(1)度限制最小生成樹和第K最短路. (poj1639)
(2)最短路,最小生成樹,二分圖,最大流問題的相關理論(主要是模型建立和求解)
(poj3155, poj2112,poj1966,poj3281,poj1087,poj2289,poj3216,poj2446
(3)最優比率生成樹. (poj2728)
(4)最小樹形圖(poj3164)
(5)次小生成樹.
(6)無向圖、有向圖的最小環
三.數據結構.
(1)trie圖的建立和應用. (poj2778)
(2)LCA和RMQ問題(LCA(最近公共祖先問題) 有離線演算法(並查集+dfs) 和 在線演算法
(RMQ+dfs)).(poj1330)
(3)雙端隊列和它的應用(維護一個單調的隊列,常常在動態規劃中起到優化狀態轉移的
目的). (poj2823)
(4)左偏樹(可合並堆).
(5)後綴樹(非常有用的數據結構,也是賽區考題的熱點).
(poj3415,poj3294)
四.搜索
(1)較麻煩的搜索題目訓練(poj1069,poj3322,poj1475,poj1924,poj2049,poj3426)
(2)廣搜的狀態優化:利用M進制數存儲狀態、轉化為串用hash表判重、按位壓縮存儲狀態、雙向廣搜、A*演算法. (poj1768,poj1184,poj1872,poj1324,poj2046,poj1482)
(3)深搜的優化:盡量用位運算、一定要加剪枝、函數參數盡可能少、層數不易過大、可以考慮雙向搜索或者是輪換搜索、IDA*演算法. (poj3131,poj2870,poj2286)
五.動態規劃
(1)需要用數據結構優化的動態規劃.
(poj2754,poj3378,poj3017)
(2)四邊形不等式理論.
(3)較難的狀態DP(poj3133)
六.數學
(1)組合數學.
1.MoBius反演(poj2888,poj2154)
2.偏序關系理論.
(2)博奕論.
1.極大極小過程(poj3317,poj1085)
2.Nim問題.
七.計算幾何學.
(1)半平面求交(poj3384,poj2540)
(2)可視圖的建立(poj2966)
(3)點集最小圓覆蓋.
(4)對踵點(poj2079)
八.綜合題.
(poj3109,poj1478,poj1462,poj2729,poj2048,poj3336,poj3315,poj2148,poj1263)gsyagsy 2007-11-29 00:22
以及補充 Dp狀態設計與方程總結
1.不完全狀態記錄
<1>青蛙過河問題
<2>利用區間dp
2.背包類問題
<1> 0-1背包，經典問題
<2>無限背包，經典問題
<3>判定性背包問題
<4>帶附屬關系的背包問題
<5> + -1背包問題
<6>雙背包求最優值
<7>構造三角形問題
<8>帶上下界限制的背包問題(012背包)
3.線性的動態規劃問題
<1>積木游戲問題
<2>決斗（判定性問題）
<3>圓的最大多邊形問題
<4>統計單詞個數問題
<5>棋盤分割
<6>日程安排問題
<7>最小逼近問題(求出兩數之比最接近某數/兩數之和等於某數等等)
<8>方塊消除游戲(某區間可以連續消去求最大效益)
<9>資源分配問題
<10>數字三角形問題
<11>漂亮的列印
<12>郵局問題與構造答案
<13>最高積木問題
<14>兩段連續和最大
<15>2次冪和問題
<16>N個數的最大M段子段和
<17>交叉最大數問題
4.判定性問題的dp(如判定整除、判定可達性等)
<1>模K問題的dp
<2>特殊的模K問題，求最大(最小)模K的數
<3>變換數問題
5.單調性優化的動態規劃
<1>1-SUM問題
<2>2-SUM問題
<3>序列劃分問題(單調隊列優化)
6.剖分問題(多邊形剖分/石子合並/圓的剖分/乘積最大)
<1>凸多邊形的三角剖分問題
<2>乘積最大問題
<3>多邊形游戲(多邊形邊上是操作符,頂點有權值)
<4>石子合並(N^3/N^2/NLogN各種優化)
7.貪心的動態規劃
<1>最優裝載問題
<2>部分背包問題
<3>乘船問題
<4>貪心策略
<5>雙機調度問題Johnson演算法
8.狀態dp
<1>牛仔射擊問題(博弈類)
<2>哈密頓路徑的狀態dp
<3>兩支點天平平衡問題
<4>一個有向圖的最接近二部圖
9.樹型dp
<1>完美伺服器問題(每個節點有3種狀態)
<2>小胖守皇宮問題
<3>網路收費問題
<4>樹中漫遊問題
<5>樹上的博弈
<6>樹的最大獨立集問題
<7>樹的最大平衡值問題
<8>構造樹的最小環

⑶ ACM中常用的搜索方法有哪些謝謝啦

最基礎就是DFS和BFS吧！然後擴展的還有雙向的BFS、迭代加深搜、記憶化搜索、A*、IDA*等等，還有啟發式的演算法都可以的。熟悉的話，可以多做些題來練習。

⑷ acm初學者要准備什麼 看什麼書啊

剛剛接觸信息學領域的同學往往存在很多困惑，不知道從何入手學習，在這篇文章里，我希望能將自己不多的經驗與大家分享，希望對各位有所幫助。
一、語言是最重要的基本功

無論側重於什麼方面，只要是通過計算機程序去最終實現的競賽，語言都是大家要過的第一道關。亞洲賽區的比賽支持的語言包括C/C++與JAVA。筆者首先說說JAVA，眾所周知，作為面向對象的王牌語言，JAVA在大型工程的組織與安全性方面有著自己獨特的優勢，但是對於信息學比賽的具體場合，JAVA則顯得不那麼合適，它對於輸入輸出流的操作相比於C++要繁雜很多，更為重要的是JAVA程序的運行速度要比C++慢10倍以上，而競賽中對於JAVA程序的運行時限卻往往得不到同等比例的放寬，這無疑對演算法設計提出了更高的要求，是相當不利的。其實，筆者並不主張大家在這種場合過多地運用面向對象的程序設計思維，因為對於小程序來說這不旦需要花費更多的時間去編寫代碼，也會降低程序的執行效率。

接著說C和C++。許多現在參加講座的同學還在上大一，C的基礎知識剛剛學完，還沒有接觸過C++，其實在賽場上使用純C的選手還是大有人在的，它們主要是看重了純C在效率上的優勢，所以這部分同學如果時間有限，並不需要急著去學習新的語言，只要提高了自己在演算法設計上的造詣，純C一樣能發揮巨大的威力。

而C++相對於C，在輸入輸出流上的封裝大大方便了我們的操作，同時降低了出錯的可能性，並且能夠很好地實現標准流與文件流的切換，方便了調試的工作。如果有些同學比較在意這點，可以嘗試C和C++的混編，畢竟僅僅學習C++的流操作還是不花什麼時間的。

C++的另一個支持來源於標准模版庫（STL），庫中提供的對於基本數據結構的統一介面操作和基本演算法的實現可以縮減我們編寫代碼的長度，這可以節省一些時間。但是，與此相對的，使用STL要在效率上做出一些犧牲，對於輸入規模很大的題目，有時候必須放棄STL，這意味著我們不能存在「有了STL就可以不去管基本演算法的實現」的想法；另外，熟練和恰當地使用STL必須經過一定時間的積累，准確地了解各種操作的時間復雜度，切忌對STL中不熟悉的部分濫用，因為這其中蘊涵著許多初學者不易發現的陷阱。

通過以上的分析，我們可以看出僅就信息學競賽而言，對語言的掌握並不要求十分全面，但是對於經常用到的部分，必須十分熟練，不允許有半點不清楚的地方，下面我舉個真實的例子來說明這個道理——即使是一點很細微的語言障礙，都有可能釀成錯誤：

在去年清華的賽區上，有一個隊在做F題的時候使用了cout和printf的混合輸出，由於一個帶緩沖一個不帶，所以輸出一長就混亂了。只是因為當時judge team中負責F題的人眼睛尖，看出答案沒錯只是順序不對（答案有一頁多，是所有題目中最長的一個輸出），又看了看程序發現只是輸出問題就給了個Presentation error（格式錯）。如果審題的人不是這樣而是直接給一個 Wrong Answer，相信這個隊是很難查到自己錯在什麼地方的。

現在我們轉入第二個方面的討論，基礎學科知識的積累。

二、以數學為主的基礎知識十分重要

雖然被定性為程序設計競賽，但是參賽選手所遇到的問題更多的是沒有解決問題的思路，而不是有了思路卻死活不能實現，這就是平時積累的基礎知識不夠。今年World Final的總冠軍是波蘭華沙大學，其成員出自於數學系而非計算機系，這就是一個鮮活的例子。競賽中對於基礎學科的涉及主要集中於數學，此外對於物理、電路等等也可能有一定應用，但是不多。因此，大一的同學也不必為自己還沒學數據結構而感到不知從何入手提高，把數學撿起來吧！下面我來談談在競賽中應用的數學的主要分支。

1、離散數學——作為計算機學科的基礎，離散數學是競賽中涉及最多的數學分支，其重中之重又在於圖論和組合數學，尤其是圖論。

圖論之所以運用最多是因為它的變化最多，而且可以輕易地結合基本數據結構和許多演算法的基本思想，較多用到的知識包括連通性判斷、DFS和BFS，關節點和關鍵路徑、歐拉迴路、最小生成樹、最短路徑、二部圖匹配和網路流等等。雖然這部分的比重很大，但是往往也是競賽中的難題所在，如果有初學者對於這部分的某些具體內容暫時感到力不從心，也不必著急，可以慢慢積累。

競賽中設計的組合計數問題大都需要用組合數學來解決，組合數學中的知識相比於圖論要簡單一些，很多知識對於小學上過奧校的同學來說已經十分熟悉，但是也有一些部分需要先對代數結構中的群論有初步了解才能進行學習。組合數學在競賽中很少以難題的形式出現，但是如果積累不夠，任何一道這方面的題目卻都有可能成為難題。

2、數論——以素數判斷和同餘為模型構造出來的題目往往需要較多的數論知識來解決，這部分在競賽中的比重並不大，但只要來上一道，也足以使知識不足的人冥思苦想上一陣時間。素數判斷和同餘最常見的是在以密碼學為背景的題目中出現，在運用密碼學常識確定大概的過程之後，核心演算法往往要涉及數論的內容。

3、計算幾何——計算幾何相比於其它部分來說是比較獨立的，就是說它和其它的知識點很少有過多的結合，較常用到的部分包括——線段相交的判斷、多邊形面積的計算、內點外點的判斷、凸包等等。計算幾何的題目難度不會很大，但也永遠不會成為最弱的題。

4、線性代數——對線性代數的應用都是圍繞矩陣展開的，一些表面上是模擬的題目往往可以藉助於矩陣來找到更好的演算法。

5、概率論——競賽是以黑箱來判卷的，這就是說你幾乎不能動使用概率演算法的念頭，但這也並不是說概率就沒有用。關於這一點，只有通過一定的練習才能體會。

6、初等數學與解析幾何——這主要就是中學的知識了，用的不多，但是至少比高等數學多，我覺得熟悉一下數學手冊上的相關內容，至少要知道在哪兒能查到，還是必要的。

7、高等數學——純粹運用高等數學來解決的題目我接觸的只有一道，但是一些題目的敘述背景往往需要和這部分有一定聯系，掌握得牢固一些總歸沒有壞處。

以上就是競賽所涉及的數學領域，可以說范圍是相當廣的。我認識的許多人去搞信息學的競賽就是為了逼著自己多學一點數學，因為數學是一切一切的基礎。

三、數據結構與演算法是真正的核心

雖然數學十分十分重要，但是如果讓三個只會數學的人參加比賽，我相信多數情況下會比三個只會數據結構與演算法的人得到更為悲慘的結局。

先說說數據結構。掌握隊列、堆棧和圖的基本表達與操作是必需的，至於樹，我個人覺得需要建樹的問題有但是並不多。（但是樹往往是很重要的分析工具）除此之外，排序和查找並不需要對所有方式都能很熟練的掌握，但你必須保證自己對於各種情況都有一個在時間復雜度上滿足最低要求的解決方案。說到時間復雜度，就又該說說哈希表了，競賽時對時間的限制遠遠多於對空間的限制，這要求大家盡快掌握「以空間換時間」的原則策略，能用哈希表來存儲的數據一定不要到時候再去查找，如果實在不能建哈希表，再看看能否建二叉查找樹等等——這都是爭取時間的策略，掌握這些技巧需要大家對數據結構尤其是演算法復雜度有比較全面的理性和感性認識。

接著說說演算法。演算法中最基本和常用的是搜索，主要是回溯和分支限界法的使用。這里要說的是，有些初學者在學習這些搜索基本演算法是不太注意剪枝，這是十分不可取的，因為所有搜索的題目給你的測試用例都不會有很大的規模，你往往察覺不出程序運行的時間問題，但是真正的測試數據一定能過濾出那些沒有剪枝的演算法。實際上參賽選手基本上都會使用常用的搜索演算法，題目的區分度往往就是建立在諸如剪枝之類的優化上了。

常用演算法中的另一類是以「相似或相同子問題」為核心的，包括遞推、遞歸、貪心法和動態規劃。這其中比較難於掌握的就是動態規劃，如何抽象出重復的子問題是很多題目的難點所在，筆者建議初學者仔細理解圖論中一些以動態規劃為基本思想所建立起來的基本演算法（比如Floyd-Warshall演算法），並且多閱讀一些定理的證明，這雖然不能有什麼直接的幫助，但是長期堅持就會對思維很有幫助。

四、團隊配合

通過以上的介紹大家也可以看出，信息學競賽對於知識面覆蓋的非常廣，想憑一己之力全部消化這些東西實在是相當困難的，這就要求我們盡可能地發揮團隊協作的精神。同組成員之間的熟練配合和默契的形成需要時間，具體的情況因成員的組成不同而不同，這里我就不再多說了。

五、練習、練習、再練習

知識的積累固然重要，但是信息學終究不是看出來的，而是練出來的，這是多少前人最深的一點體會，只有通過具體題目的分析和實踐，才能真正掌握數學的使用和演算法的應用，並在不斷的練習中增加編程經驗和技巧，提高對時間復雜度的感性認識，優化時間的分配，加強團隊的配合。總之，在這里光有紙上談兵是絕對不行的，必須要通過實戰來鍛煉自己。

大家一定要問，我們去哪裡找題做，又如何檢驗程序是否正確呢？這大可不必擔心，現在已經有了很多網上做題的站點，這些站點提供了大量的題庫並支持在線判卷，你只需要把程序源碼提交上去，馬上就可以知道自己的程序是否正確，運行所使用的時間以及消耗的內存等等狀況。下面我給大家推薦幾個站點，筆者不建議大家在所有這些站點上做題，選擇一個就可以了，因為每個站點的題都有一定的難易比例，系統地做一套題庫可以使你對各種難度、各種類型的題都有所認識。

1、Ural：

Ural是中國學生對俄羅斯的Ural州立大學的簡稱 ，那裡設立了一個Ural Online Problem Set，並且支持Online Judge。Ural的不少題目演算法性和趣聞性都很強，得到了國內廣大學生的厚愛。根據「信息學初學者之家」網站的統計，Ural的題目類型大概呈如下的分布：

題型
搜索
動態規劃
貪心
構造
圖論
計算幾何
純數學問題
數據結構
其它

所佔比例
約10%
約15%
約5%
約5%
約10%
約5%
約20%
約5%
約25%

這和實際比賽中的題型分布也是大體相當的。有興趣的朋友可以去看看。

2、UVA：

UVA代表西班牙Valladolid大學(University de Valladolid)。該大學有一個那裡設立了一個PROBLEM SET ARCHIVE with ONLINE JUDGE ，並且支持ONLINE JUDGE，形式和Ural大學的題庫類似。不過和Ural不同的是，UVA題目多的多，而且比較雜，而且有些題目的測試數據比較刁鑽。這使得剛到那裡做題的朋友往往感覺到無所適從，要麼難以找到合適的題目，要麼Wrong Answer了很多次以後仍然不知道錯在那裡。 如果說做Ural題目主要是為了訓練演算法，那麼UVA題目可以訓練全方位的基本功和一些必要的編程素質。UVA和許多世界知名大學聯合辦有同步網上比賽，因此那裡強人無數，不過你先要使自己具有聽懂他們在說什麼的素質：）

3、ZOJ：

ZOJ是浙江大學建立的ONLINE JUDGE，是中國大學建立的第一個同類站點，也是最好和人氣最高的一個，筆者和許多班裡的同學就是在這里練習。ZOJ雖然也定位為一個英文網站，但是這里的中國學生比較多，因此讓人覺得很親切。這里目前有500多道題目，難易分配適中，且涵蓋了各大洲的題目類型並配有索引，除此之外，ZOJ的JUDGE系統是幾個網站中表現得比較好的一個，很少出現Wrong Answer和Presentation error混淆的情況。這里每月也辦有一次網上比賽，只要是注冊的用戶都可以參加。

說起中國的ONLINE JUDGE，去年才開始參加ACM競賽的北京大學現在也建立了自己的提交系統；而我們學校也是去年開始參加比賽，現在也有可能推出自己的提交系統，如果能夠做成，到時候大家就可以去上面做題了。同類網站的飛速發展標志著有越來越多的同學有興趣進入信息學的領域探索，這是一件好事，同時也意味著更激烈的競爭。

看看這篇文章對你有什麼幫助！我也是ACM初學者！

⑸ acm競賽知識點

1. acm常用小知識點
acm常用小知識點 1.ACM 關於ACM程序設計競賽,需要掌握哪些知識點,最好能詳細一
訓練過ACM等程序設計競賽的人在演算法上有較大的優勢，這就說明當你編程能力提高之後，主要時間是花在思考演算法上，不是花在寫程序與debug上。

下面給個計劃你練練：第一階段：練經典常用演算法，下面的每個演算法給我打上十到二十遍，同時自己精簡代碼，因為太常用，所以要練到寫時不用想，10-15分鍾內打完，甚至關掉顯示器都可以把程序打出來。1.最短路（Floyd、Dijstra,BellmanFord） 2.最小生成樹（先寫個prim,kruscal要用並查集，不好寫） 3.大數（高精度）加減乘除4.二分查找. （代碼可在五行以內） 5.叉乘、判線段相交、然後寫個凸包. 6.BFS、DFS，同時熟練hash表（要熟，要靈活，代碼要簡） 7.數學上的有：輾轉相除（兩行內），線段交點、多角形面積公式. 8. 調用系統的qsort， 技巧很多，慢慢掌握. 9. 任意進制間的轉換第二階段：練習復雜一點，但也較常用的演算法。

如： 1. 二分圖匹配（匈牙利），最小路徑覆蓋 2. 網路流，最小費用流。 3. 線段樹. 4. 並查集。

5. 熟悉動態規劃的各個典型：LCS、最長遞增子串、三角剖分、記憶化dp 6.博弈類演算法。博弈樹，二進製法等。

7.最大團，最大獨立集。 8.判斷點在多邊形內。

9. 差分約束系統. 10. 雙向廣度搜索、A*演算法，最小耗散優先.第三階段： 前兩個階段是打基礎，第三階段是鍛煉在比賽中可以快速建立模型、想新演算法。這就要平時多做做綜合的題型了。

1. 把oibh上的論文看看（大概幾百篇的，我只看了一點點，呵呵）。 2. 平時掃掃zoj上的難題啦，別老做那些不用想的題.（中大acm的版主經常說我挑簡單的來做：-P ） 3. 多參加網上的比賽，感受一下比賽的氣氛，評估自己的實力. 4. 一道題不要過了就算，問一下人，有更好的演算法也打一下。

5. 做過的題要記好 ：-）下面轉自：ACMer必備知識（任重而道遠。）

圖論 路徑問題 0/1邊權最短路徑 BFS 非負邊權最短路徑（Dijkstra） 可以用Dijkstra解決問題的特徵 負邊權最短路徑 Bellman-Ford Bellman-Ford的Yen-氏優化 差分約束系統 Floyd 廣義路徑問題 傳遞閉包 極小極大距離 / 極大極小距離 Euler Path / Tour 圈套圈演算法 混合圖的 Euler Path / Tour Hamilton Path / Tour 特殊圖的Hamilton Path / Tour 構造 生成樹問題 最小生成樹 第k小生成樹 最優比率生成樹 0/1分數規劃 度限制生成樹 連通性問題 強大的DFS演算法 無向圖連通性 割點 割邊 二連通分支 有向圖連通性 強連通分支 2-SAT 最小點基 有向無環圖 拓撲排序 有向無環圖與動態規劃的關系 二分圖匹配問題 一般圖問題與二分圖問題的轉換思路 最大匹配 有向圖的最小路徑覆蓋 0 / 1矩陣的最小覆蓋 完備匹配 最優匹配 穩定婚姻 網路流問題 網路流模型的簡單特徵和與線性規劃的關系 最大流最小割定理 最大流問題 有上下界的最大流問題 循環流 最小費用最大流 / 最大費用最大流 弦圖的性質和判定組合數學 解決組合數學問題時常用的思想 逼近 遞推 / 動態規劃 概率問題 Polya定理計算幾何 / 解析幾何 計算幾何的核心：叉積 / 面積 解析幾何的主力：復數 基本形 點 直線，線段 多邊形 凸多邊形 / 凸包 凸包演算法的引進，卷包裹法 Graham掃描法 水平序的引進，共線凸包的補丁 完美凸包演算法 相關判定 兩直線相交 兩線段相交 點在任意多邊形內的判定 點在凸多邊形內的判定 經典問題 最小外接圓 近似O(n)的最小外接圓演算法 點集直徑 旋轉卡殼，對踵點 多邊形的三角剖分數學 / 數論 最大公約數 Euclid演算法 擴展的Euclid演算法 同餘方程 / 二元一次不定方程 同餘方程組 線性方程組 高斯消元法 解mod 2域上的線性方程組 整系數方程組的精確解法 矩陣 行列式的計算 利用矩陣乘法快速計算遞推關系 分數 分數樹 連分數逼近 數論計算 求N的約數個數 求phi(N) 求約數和 快速數論變換 …… 素數問題 概率判素演算法 概率因子分解數據結構 組織結構 二叉堆 左偏樹 二項樹 勝者樹 跳躍表 樣式圖標 斜堆 reap 統計結構 樹狀數組 虛二叉樹 線段樹 矩形面積並 圓形面積並 關系結構 Hash表 並查集 路徑壓縮思想的應用 STL中的數據結構 vector deque set / map動態規劃 / 記憶化搜索 動態規劃和記憶化搜索在思考方式上的區別 最長子序列系列問題 最長不下降子序列 最長公共子序列 最長公共不下降子序列 一類NP問題的動態規劃解法 樹型動態規劃 背包問題 動態規劃的優化 四邊形不等式 函數的凸凹性 狀態設計 規劃方向線性規劃常用思想 二分 最小表示法串 KMP Trie結構 後綴樹/後綴數組 LCA/RMQ 有限狀態自動機理論排序 選擇/冒泡 快速排序 堆排序 歸並排序 基數排序 拓撲排序 排序網路。
2.ACM需要具備什麼知識
ACM國際大學生程序設計競賽（ACM/ICPC :ACM International Collegiate Programming Contest）是由國際計算機界歷史悠久、頗具權威性的組織ACM（ 美國計算機協會）學會（Association for puter Machineary）主辦，是世界上公認的規模最大、水平最高的國際大學生程序設計競賽，其目的旨在使大學生運用計算機來充分展示自已分析問題和解決問題的能力。該項競賽從1970年舉辦至今已歷25屆，因歷屆競賽都薈萃了世界各大洲的精英，雲集了計算機界的「希望之星」，而受到國際各知名大學的重視，並受到全世界各著名計算機公司如Microsoft（微軟公司） 、IBM等的高度關注，成為世界各國大學生最具影響力的國際級計算機類的賽事，ACM所頒發的獲獎證書也為世界各著名計算機公司、各知名大學所認可。

該項競賽是年度性競賽，分區域預賽和國際決賽兩個階段進行，各預賽區第一名自動獲得參加世界決賽的資格，世界決賽安排在每年的3~4月舉行，而區域預賽安排在上一年的9月~12月在各大洲舉行。從1998年開始，IBM公司連續5年獨家贊助該項賽事的世界決賽和區域預賽。這項比賽是以大學為單位組隊（每支隊由教練、3名正式隊員，一名後備隊員組成）參賽，要求在5個小時內，解決5~8到題目。

ACM/ICPC的區域預賽是規模很大，范圍很廣的賽事，近幾年，全世界有1000多所大學， 2000多支參賽隊在六大洲的28~30個賽站中爭奪世界決賽的60~66個名額，去年我校舉辦的區域預賽，就有來自50多所高校的100多支隊伍參加，其激烈程度可想而知。

與其他編程競賽相比，ACM/ICPC題目難度更大，更強調演算法的高效性，不僅要解決一個指定的命題，而且必需要以最佳的方式解決指定的命題；它涉及知識面廣，與大學計算機系本科以及研究生如程序設計、離散數學、數據結構、人工智慧、演算法分析與設計等相關課程直接關聯，對數學要求更高，由於採用英文命題，對英語要求高，ACM/ICPC採用3人合作、共用一台電腦，所以它更強調團隊協作精神；由於許多題目並無現成的演算法，需要具備創新的精神，ACM/ICPC不僅強調學科的基礎，更強調全面素質和能力的培養。ACM/ICPC是一種全封閉式的競賽，能對學生能力進行實時的全面的考察，其成績的真實性更強，所以目前已成為內地高校的一個熱點，是培養全面發展優秀人材的一項重要的活動。概括來說就是：強調演算法的高效性、知識面要廣、對數學和英語要求較高、團隊協作和創新精神。
3.ACM需要那些方面的知識
一、語言是最重要的基本功 無論側重於什麼方面，只要是通過計算機程序去最終實現的競賽，語言都是大家要 過的第一道關。

亞洲賽區的比賽支持的語言包括C/C++與JAVA。筆者首先說說JAVA，眾所 周知，作為面向對象的王牌語言，JAVA在大型工程的組織與安全性方面有著自己獨特的 優勢，但是對於信息學比賽的具體場合，JAVA則顯得不那麼合適，它對於輸入輸出流的 操作相比於C++要繁雜很多，更為重要的是JAVA程序的運行速度要比C++慢10倍以上，而 競賽中對於JAVA程序的運行時限卻往往得不到同等比例的放寬，這無疑對演算法設計提出 了更高的要求，是相當不利的。

其實，筆者並不主張大家在這種場合過多地運用面向對 象的程序設計思維，因為對於小程序來說這不旦需要花費更多的時間去編寫代碼，也會 降低程序的執行效率。 接著說C和C++。

許多現在參加講座的同學還在上大一，C的基礎知識剛剛學完，還沒 有接觸過C++，其實在賽場上使用純C的選手還是大有人在的，它們主要是看重了純C在效 率上的優勢，所以這部分同學如果時間有限，並不需要急著去學習新的語言，只要提高 了自己在演算法設計上的造詣，純C一樣能發揮巨大的威力。 而C++相對於C，在輸入輸出流上的封裝大大方便了我們的操作，同時降低了出錯的 可能性，並且能夠很好地實現標准流與文件流的切換，方便了調試的工作。

如果有些同 學比較在意這點，可以嘗試C和C++的混編，畢竟僅僅學習C++的流操作還是不花什麼時間 的。 C++的另一個支持來源於標准模版庫（STL），庫中提供的對於基本數據結構的統一 介面操作和基本演算法的實現可以縮減我們編寫代碼的長度，這可以節省一些時間。

但是 ，與此相對的，使用STL要在效率上做出一些犧牲，對於輸入規模很大的題目，有時候必 須放棄STL，這意味著我們不能存在「有了STL就可以不去管基本演算法的實現」的想法； 另外，熟練和恰當地使用STL必須經過一定時間的積累，准確地了解各種操作的時間復雜 度，切忌對STL中不熟悉的部分濫用，因為這其中蘊涵著許多初學者不易發現的陷阱。 通過以上的分析，我們可以看出僅就信息學競賽而言，對語言的掌握並不要求十分 全面，但是對於經常用到的部分，必須十分熟練，不允許有半點不清楚的地方，下面我 舉個真實的例子來說明這個道理——即使是一點很細微的語言障礙，都有可能釀成錯誤 ： 在去年清華的賽區上，有一個隊在做F題的時候使用了cout和printf的混合輸出，由 於一個帶緩沖一個不帶，所以輸出一長就混亂了。

只是因為當時judge team中負責F題的 人眼睛尖，看出答案沒錯只是順序不對（答案有一頁多，是所有題目中最長的一個輸出 ），又看了看程序發現只是輸出問題就給了個Presentation error（格式錯）。如果審 題的人不是這樣而是直接給一個 Wrong Answer，相信這個隊是很難查到自己錯在什麼地 方的。

現在我們轉入第二個方面的討論，基礎學科知識的積累。 二、以數學為主的基礎知識十分重要 雖然被定性為程序設計競賽，但是參賽選手所遇到的問題更多的是沒有解決問題的 思路，而不是有了思路卻死活不能實現，這就是平時積累的基礎知識不夠。

今年World Final的總冠軍是波蘭華沙大學，其成員出自於數學系而非計算機系，這就是一個鮮活的 例子。競賽中對於基礎學科的涉及主要集中於數學，此外對於物理、電路等等也可能有 一定應用，但是不多。

因此，大一的同學也不必為自己還沒學數據結構而感到不知從何 入手提高，把數學撿起來吧！下面我來談談在競賽中應用的數學的主要分支。 1、離散數學——作為計算機學科的基礎，離散數學是競賽中涉及最多的數學分支， 其重中之重又在於圖論和組合數學，尤其是圖論。

圖論之所以運用最多是因為它的變化最多，而且可以輕易地結合基本數據結構和許 多演算法的基本思想，較多用到的知識包括連通性判斷、DFS和BFS，關節點和關鍵路徑、歐拉迴路、最小生成樹、最短路徑、二部圖匹配和網路流等等。雖然這部分的比重很大 ，但是往往也是競賽中的難題所在，如果有初學者對於這部分的某些具體內容暫時感到 力不從心，也不必著急，可以慢慢積累。

競賽中設計的組合計數問題大都需要用組合數學來解決，組合數學中的知識相比於 圖論要簡單一些，很多知識對於小學上過奧校的同學來說已經十分熟悉，但是也有一些 部分需要先對代數結構中的群論有初步了解才能進行學習。組合數學在競賽中很少以難 題的形式出現，但是如果積累不夠，任何一道這方面的題目卻都有可能成為難題。

2、數論——以素數判斷和同餘為模型構造出來的題目往往需要較多的數論知識來解 決，這部分在競賽中的比重並不大，但只要來上一道，也足以使知識不足的人冥思苦想 上一陣時間。素數判斷和同餘最常見的是在以密碼學為背景的題目中出現，在運用密碼 學常識確定大概的過程之後，核心演算法往往要涉及數論的內容。

3、計算幾何——計算幾何相比於其它部分來說是比較獨立的，就是說它和其它的知 識點很少有過多的結合，較常用到的部分包括——線段相交的判斷、多邊形面積的計算 、內點外點的判斷、凸包等。
4.ACM需要那些方面的知識
一、語言是最重要的基本功 無論側重於什麼方面，只要是通過計算機程序去最終實現的競賽，語言都是大家要 過的第一道關。

亞洲賽區的比賽支持的語言包括C/C++與JAVA。筆者首先說說JAVA，眾所 周知，作為面向對象的王牌語言，JAVA在大型工程的組織與安全性方面有著自己獨特的 優勢，但是對於信息學比賽的具體場合，JAVA則顯得不那麼合適，它對於輸入輸出流的 操作相比於C++要繁雜很多，更為重要的是JAVA程序的運行速度要比C++慢10倍以上，而 競賽中對於JAVA程序的運行時限卻往往得不到同等比例的放寬，這無疑對演算法設計提出 了更高的要求，是相當不利的。

其實，筆者並不主張大家在這種場合過多地運用面向對 象的程序設計思維，因為對於小程序來說這不旦需要花費更多的時間去編寫代碼，也會 降低程序的執行效率。 接著說C和C++。

許多現在參加講座的同學還在上大一，C的基礎知識剛剛學完，還沒 有接觸過C++，其實在賽場上使用純C的選手還是大有人在的，它們主要是看重了純C在效 率上的優勢，所以這部分同學如果時間有限，並不需要急著去學習新的語言，只要提高 了自己在演算法設計上的造詣，純C一樣能發揮巨大的威力。 而C++相對於C，在輸入輸出流上的封裝大大方便了我們的操作，同時降低了出錯的 可能性，並且能夠很好地實現標准流與文件流的切換，方便了調試的工作。

如果有些同 學比較在意這點，可以嘗試C和C++的混編，畢竟僅僅學習C++的流操作還是不花什麼時間 的。 C++的另一個支持來源於標准模版庫（STL），庫中提供的對於基本數據結構的統一 介面操作和基本演算法的實現可以縮減我們編寫代碼的長度，這可以節省一些時間。

但是 ，與此相對的，使用STL要在效率上做出一些犧牲，對於輸入規模很大的題目，有時候必 須放棄STL，這意味著我們不能存在「有了STL就可以不去管基本演算法的實現」的想法； 另外，熟練和恰當地使用STL必須經過一定時間的積累，准確地了解各種操作的時間復雜 度，切忌對STL中不熟悉的部分濫用，因為這其中蘊涵著許多初學者不易發現的陷阱。 通過以上的分析，我們可以看出僅就信息學競賽而言，對語言的掌握並不要求十分 全面，但是對於經常用到的部分，必須十分熟練，不允許有半點不清楚的地方，下面我 舉個真實的例子來說明這個道理——即使是一點很細微的語言障礙，都有可能釀成錯誤 ： 在去年清華的賽區上，有一個隊在做F題的時候使用了cout和printf的混合輸出，由 於一個帶緩沖一個不帶，所以輸出一長就混亂了。

只是因為當時judge team中負責F題的 人眼睛尖，看出答案沒錯只是順序不對（答案有一頁多，是所有題目中最長的一個輸出 ），又看了看程序發現只是輸出問題就給了個Presentation error（格式錯）。如果審 題的人不是這樣而是直接給一個 Wrong Answer，相信這個隊是很難查到自己錯在什麼地 方的。

現在我們轉入第二個方面的討論，基礎學科知識的積累。 二、以數學為主的基礎知識十分重要 雖然被定性為程序設計競賽，但是參賽選手所遇到的問題更多的是沒有解決問題的 思路，而不是有了思路卻死活不能實現，這就是平時積累的基礎知識不夠。

今年World Final的總冠軍是波蘭華沙大學，其成員出自於數學系而非計算機系，這就是一個鮮活的 例子。競賽中對於基礎學科的涉及主要集中於數學，此外對於物理、電路等等也可能有 一定應用，但是不多。

因此，大一的同學也不必為自己還沒學數據結構而感到不知從何 入手提高，把數學撿起來吧！下面我來談談在競賽中應用的數學的主要分支。 1、離散數學——作為計算機學科的基礎，離散數學是競賽中涉及最多的數學分支， 其重中之重又在於圖論和組合數學，尤其是圖論。

圖論之所以運用最多是因為它的變化最多，而且可以輕易地結合基本數據結構和許 多演算法的基本思想，較多用到的知識包括連通性判斷、DFS和BFS，關節點和關鍵路徑、歐拉迴路、最小生成樹、最短路徑、二部圖匹配和網路流等等。雖然這部分的比重很大 ，但是往往也是競賽中的難題所在，如果有初學者對於這部分的某些具體內容暫時感到 力不從心，也不必著急，可以慢慢積累。

競賽中設計的組合計數問題大都需要用組合數學來解決，組合數學中的知識相比於 圖論要簡單一些，很多知識對於小學上過奧校的同學來說已經十分熟悉，但是也有一些 部分需要先對代數結構中的群論有初步了解才能進行學習。組合數學在競賽中很少以難 題的形式出現，但是如果積累不夠，任何一道這方面的題目卻都有可能成為難題。

2、數論——以素數判斷和同餘為模型構造出來的題目往往需要較多的數論知識來解 決，這部分在競賽中的比重並不大，但只要來上一道，也足以使知識不足的人冥思苦想 上一陣時間。素數判斷和同餘最常見的是在以密碼學為背景的題目中出現，在運用密碼 學常識確定大概的過程之後，核心演算法往往要涉及數論的內容。

3、計算幾何——計算幾何相比於其它部分來說是比較獨立的，就是說它和其它的知 識點很少有過多的結合，較常用到的部分包括——線段相交的判斷、多邊形面積的計算 、內點外點的判斷、凸包等。
5.ACM需要具備什麼知識
ACM國際大學生程序設計競賽（ACM/ICPC :ACM International Collegiate Programming Contest）是由國際計算機界歷史悠久、頗具權威性的組織ACM（ 美國計算機協會）學會（Association for puter Machineary）主辦，是世界上公認的規模最大、水平最高的國際大學生程序設計競賽，其目的旨在使大學生運用計算機來充分展示自已分析問題和解決問題的能力。該項競賽從1970年舉辦至今已歷25屆，因歷屆競賽都薈萃了世界各大洲的精英，雲集了計算機界的「希望之星」，而受到國際各知名大學的重視，並受到全世界各著名計算機公司如Microsoft（微軟公司） 、IBM等的高度關注，成為世界各國大學生最具影響力的國際級計算機類的賽事，ACM所頒發的獲獎證書也為世界各著名計算機公司、各知名大學所認可。

該項競賽是年度性競賽，分區域預賽和國際決賽兩個階段進行，各預賽區第一名自動獲得參加世界決賽的資格，世界決賽安排在每年的3~4月舉行，而區域預賽安排在上一年的9月~12月在各大洲舉行。從1998年開始，IBM公司連續5年獨家贊助該項賽事的世界決賽和區域預賽。這項比賽是以大學為單位組隊（每支隊由教練、3名正式隊員，一名後備隊員組成）參賽，要求在5個小時內，解決5~8到題目。

ACM/ICPC的區域預賽是規模很大，范圍很廣的賽事，近幾年，全世界有1000多所大學， 2000多支參賽隊在六大洲的28~30個賽站中爭奪世界決賽的60~66個名額，去年我校舉辦的區域預賽，就有來自50多所高校的100多支隊伍參加，其激烈程度可想而知。

與其他編程競賽相比，ACM/ICPC題目難度更大，更強調演算法的高效性，不僅要解決一個指定的命題，而且必需要以最佳的方式解決指定的命題；它涉及知識面廣，與大學計算機系本科以及研究生如程序設計、離散數學、數據結構、人工智慧、演算法分析與設計等相關課程直接關聯，對數學要求更高，由於採用英文命題，對英語要求高，ACM/ICPC採用3人合作、共用一台電腦，所以它更強調團隊協作精神；由於許多題目並無現成的演算法，需要具備創新的精神，ACM/ICPC不僅強調學科的基礎，更強調全面素質和能力的培養。ACM/ICPC是一種全封閉式的競賽，能對學生能力進行實時的全面的考察，其成績的真實性更強，所以目前已成為內地高校的一個熱點，是培養全面發展優秀人材的一項重要的活動。概括來說就是：強調演算法的高效性、知識面要廣、對數學和英語要求較高、團隊協作和創新精神。
6.ACM常用的經典演算法
大概分為數論演算法，圖論演算法，A*演算法。

數論演算法：

排序（選擇，冒泡，快速，歸並，堆，基數，桶排序等）

遞歸，回溯

概率，隨機

公約數，素數

因數分解

矩陣運算

線性規劃

最小二乘

微積分

多項式分解和級數

圖論演算法：

哈夫曼樹（即最優二叉樹）

哈希表

Prim,Kruskal演算法（即最小生成樹演算法）

紅黑樹

a-B剪枝法

深、廣度搜索

拓撲排序

強連通分量

Dijkstra,Bellman-Ford,Floyd-Warashall演算法（最短路徑演算法）

計算幾何（線段相交，凸包，最近點對）

A*演算法：

動態規劃

貪心演算法

KMP演算法

哈密頓迴路問題

子集問題

博弈（極大極小值演算法等）
7.參加ACM需要准備哪些知識
學ACM要熟練C語言的基礎語法，對編程有很大的興趣，還要學關於數據結構的知識。

內容大多數是考數據結構，例如：深度搜索（dfs）、廣度搜索（bfs）、並查集、母函數、最小生成樹、數論、動態規劃（重點）、背包問題、最短路、網路流……還有很多演算法，我列出這些是經常考到的，我也在學習上述所說的。 最好買一本《數據結構》或者關於演算法的書看看，看完一些要自己動手實踐做題，做題的話去杭電acm做題，裡面有很多很基礎的題，不錯的。

資料的話，網路有很多，我多數都是網路或者 *** ，還有可以看看別人的博客的解題報告，裡面有詳細的介紹，不懂還可以問問同學師兄的。 對了，還有一點，acm比賽都是英文題目的，比賽時帶本字典查吧。

希望我說的你能滿意，祝你能在acm方面有所收獲。

⑹ ACM:給定點集S,求S中周長最小的三角形（點集中點數N<=20000),求一個復雜度可接受的演算法（n^2以下）

關於搜尋一定范圍內素數的演算法及其復雜度分析
——曾曉奇
關於素數的演算法是信息學競賽和程序設計競賽中常考的數論知識，在這里我跟大家講一下尋找一定范圍內素數的幾個演算法。看了以後相信
對大家一定有幫助。
正如大家都知道的那樣，一個數 n 如果是合數，那麼它的所有的因子不超過sqrt(n)--n的開方,那麼我們可以用這個性質用最直觀的方法
來求出小於等於n的所有的素數。
num = 0;
for(i=2; i<=n; i++)
{ for(j=2; j<=sqrt(i); j++)
if( j%i==0 ) break;
if( j>sqrt(i) ) prime[num++] = i; //這個prime[]是int型，跟下面講的不同。
}
這就是最一般的求解n以內素數的演算法。復雜度是o(n*sqrt(n))，如果n很小的話，這種演算法（其實這是不是演算法我都懷疑，沒有水平。當然沒
接觸過程序競賽之前我也只會這一種求n以內素數的方法。-_-~）不會耗時很多.
但是當n很大的時候，比如n=10000000時，n*sqrt(n)>30000000000,數量級相當大。在一般的機子它不是一秒鍾跑不出結果，它是好幾分鍾都跑不
出結果，這可不是我瞎掰的，想鍛煉耐心的同學不妨試一試~。。。。
在程序設計競賽中就必須要設計出一種更好的演算法要求能在幾秒鍾甚至一秒鍾之內找出n以內的所有素數。於是就有了素數篩法。
（我表達得不清楚的話不要罵我，見到我的時候扁我一頓我不說一句話。。。）
素數篩法是這樣的：
1.開一個大的bool型數組prime[]，大小就是n+1就可以了.先把所有的下標為奇數的標為true,下標為偶數的標為false.
2.然後：
for( i=3; i<=sqrt(n); i+=2 )
{ if(prime[i])
for( j=i+i; j<=n; j+=i ) prime[j]=false;
}
3.最後輸出bool數組中的值為true的單元的下標，就是所求的n以內的素數了。
原理很簡單，就是當i是質(素)數的時候，i的所有的倍數必然是合數。如果i已經被判斷不是質數了，那麼再找到i後面的質數來把這個質
數的倍數篩掉。
一個簡單的篩素數的過程：n=30。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30

第 1 步過後2 4 ... 28 30這15個單元被標成false,其餘為true。
第 2 步開始：
i=3; 由於prime[3]=true, 把prime[6], [9], [12], [15], [18], [21], [24], [27], [30]標為false.
i=4; 由於prime[4]=false,不在繼續篩法步驟。
i=5; 由於prime[5]=true, 把prime[10],[15],[20],[25],[30]標為false.
i=6>sqrt(30)演算法結束。
第 3 步把prime[]值為true的下標輸出來：
for(i=2; i<=30; i++)
if(prime[i]) printf("%d ",i);
結果是 2 3 5 7 11 13 17 19 23 29

這就是最簡單的素數篩選法，對於前面提到的10000000內的素數，用這個篩選法可以大大的降低時間復雜度。把一個只見黑屏的演算法
優化到立竿見影，一下就得到結果。關於這個演算法的時間復雜度，我不會描述，沒看到過類似的記載。只知道演算法書上如是說：前幾年比
較好的演算法的復雜度為o(n),空間復雜度為o(n^(1/2)/logn).另外還有時間復雜度為o(n/logn),但空間復雜度為O(n/(lognloglogn))的演算法。
我水平有限啦，自己分析不來。最有說服力的就是自己上機試一試。下面給出這兩個演算法的程序：
//最普通的方法：
#include<stdio.h>
#include<math.h>
#define N 10000001

int prime[N];

int main()
{
int i, j, num = 0;
for(i=2; i<N; i++)
{ for(j=2; j<=sqrt(i); j++)
if( j%i==0 ) break;
if( j>sqrt(i) ) prime[num++] = i;
}
for(i=2; i<100; i++) //由於輸出將佔用太多io時間，所以只輸出2-100內的素數。可以把100改為N
if( prime[i] )printf("%d ",i);

return 0;
}

//用了篩法的方法：
#include<stdio.h>
#include<math.h>

#define N 10000001

bool prime[N];

int main()
{
int i, j;
for(i=2; i<N; i++)
if(i%2) prime[i]=true;
else prime[i]=false;
for(i=3; i<=sqrt(N); i++)
{ if(prime[i])
for(j=i+i; j<N; j+=i) prime[i]=false;
}
for(i=2; i<100; i++)//由於輸出將佔用太多io時間，所以只輸出2-100內的素數。可以把100改為N
if( prime[i] )printf("%d ",i);

return 0;
}

裝了vc的同學上機跑一下這兩個程序試一試。這個差別，絕對是天上地下。前面那個程序絕對是n分鍾黑屏的說。

另外，對於這樣的篩法，還可以進一步優化，就是bool型數組裡面只存奇數不存偶數。如定義prime[N],則0表示
3，1表示5，2表示7，3表示9...。如果prime[0]為true,則表示3時素數。prime[3]為false意味著9是合數。
這樣的優化不是簡單的減少了一半的循環時間，比如按照原始的篩法，數組的下標就對應數。則在計算30以內素
數的時候3個步驟加起來走了15個單位時間。但是用這樣的優化則是這樣：
則由於只存3 5 7 9 11 13 15 17 19 21 23 25 27 29，只需要14個單元
第 1 步 把14個單元賦為true (每個單元代表的數是2*i+3,如第0單元代表3，第1單元代表5...)
第 2 步開始：
i=0; 由於prime[0]=true, 把 [3], [6], [9], [12]標為false.
i=1; 由於prime[1]=true, 把 [6], [11]標為false
i=2 2*i+3>sqrt(30)演算法結束。
這樣優化以後總共只走6個單位時間。
當n相當大以後這樣的優化效果就更加明顯，效率絕對不僅僅是翻倍。

出了這樣的優化以外，另外在每一次用當前已得出的素數篩選後面的數的時候可以一步跳到已經被判定不是素數的
數後面，這樣就減少了大量的重復計算。（比如我們看到的，i=0與i=1時都標了[6],這個就是重復的計算。）
我們可以發現一個規律，那就是3（即i=0）是從下標為[3]的開始篩的，5（即i=1）是從下標為[11]開始篩的（因為[6]
已經被3篩過了）。然後如果n很大的話，繼續篩。7（i=2）本來應該從下標為[9]開始篩，但是由於[9]被篩過了，而
[16]也已經被5（i=1）篩過了。於是7（i=2）從[23]（就是2*23+3=49）開始篩。
於是外圍循環為i時，內存循環的篩法是從 i+(2*i+3)*(i+1)即i*(2*i+6)+3開始篩的。
這個優化也對演算法復雜度的降低起到了很大的作用。
相比於一般的篩法，加入這兩個優化後的篩法要高效很多。高興去的同學可以試著自己編寫程序看一看效率。我這里
有程序，需要的可以向我要。不懂得也可以問我。

上面的素數篩法是所有程序設計競賽隊員都必須掌握的，而後面加了兩個優化的篩法是效率很高的演算法，是湖南大學
huicpc39同學設計的（可能是學來的，也可能是自創的。相當強悍）。在數量級更大的情況下就可以發現一般篩法和
優化後的篩法的明顯區別。

另外，台灣的ACMTino同學也給我介紹了他的演算法：a是素數，則下一個起點是a*a,把後面的所有的a*a+2*i*a篩掉。

這上面的所有的素數篩選的演算法都可以再進一步化為二次篩選法，就是欲求n以內的素數，就先把sqrt(n)內的素數求
出來，用已經求得的素數來篩出後面的合數。

我把一般的篩選法的過程詳細的敘述了一遍，應該都懂了吧？後面的優化過程及不同的方法，能看懂最好。不是很難的。

相關知識：

最大公約數只有1和它本身的數叫做質數（素數）——這個應該知道吧？-_-b
至今為止，沒有任何人發現素數的分布規律，也沒有人能用一個公式計算出所有的素數。關於素數的很多的有趣的性質或者科學家的努力
我不在這里多說，大家有興趣的話可以到網路或google搜一下。我在下面列出了一個網址，上面只有個大概。更多的知識需要大家一點一點
地動手收集。
http://www.scitom.com.cn/discovery/universe/home01.html
1.高斯猜測，n以內的素數個數大約與n/ln(n)相當，或者說，當n很大時，兩者數量級相同。這就是著名的素數定理。
2.十七世紀費馬猜測，2的2^n次方+1，n=0，1，2…時是素數，這樣的數叫費馬素數，可惜當n=5時，2^32+1就不是素數，
至今也沒有找到第六個費馬素數。
3.18世紀發現的最大素數是2^31-1，19世紀發現的最大素數是2^127-1，20世紀末人類已知的最大素數是2^859433-1，用十進製表示，這是一個258715位的數字。
4.孿生素數猜想：差為2的素數有無窮多對。目前知道的最大的孿生素數是1159142985×2^2304－1和1159142985×2^2304＋1。
5.歌德巴赫猜想：大於2的所有偶數均是兩個素數的和，大於5的所有奇數均是三個素數之和。其中第二個猜想是第一個的自然推論，因此歌德巴赫猜想又被稱為1+1問題。我國數學家陳景潤證明了1+2，即所有大於2的偶數都是一個素數和只有兩個素數因數的合數的和。國際上稱為陳氏定理。

⑺ 關於ACM競賽

ACM考的是演算法設計,編程,理解能力.
基本上ACM的題目都是英文的,所以你的英文要到火候,這個lz
應該沒問題吧.

還有最主要的就是演算法了,你可以去肯"演算法導論"這本牛書.

第三就是編程能力,ACM競賽中,時間也是一項衡量指標,怎樣在最快的時間內解決問題,編譯通過,並且運行正確.

最後,我覺得考慮問題的全面性也是很重要的,ACM的題目,很多都會有臨界情況,如何讓你的程序能夠通過這些臨界值的檢驗,很考察一個人思考問題的全面性的.

⑻ 參加ACM大賽應該准備哪些課程

課程：

（1）基本演算法: 二分,分治，貪心

（2） 離散數學離散數學動態規劃

（3） 搜索演算法：深度優先 搜索，廣度優先搜A*演算法 ，阿爾法貝塔剪枝

（4）數據結構:線段樹, 樹狀數組，並查集,Trie圖

（5）圖論問題：最小生成樹 最短路 強連通分量、橋和割點

（6）網路流演算法：基本的網路流演算法，Dinic演算法，帶上下界的網路流，最小費用流

（7）計算幾何：線與線求交，線與面求交，求凸包，半平面求交等

（8） 離散數學，高等數學，線性代數，初等數論，計算幾何

（9）計算機專業英語

（10）C++；基礎的遞歸、枚舉演算法

(8)acm常用演算法擴展閱讀：

1.參賽隊伍最多由三名參賽隊員組成。

2.競賽中命題10題左右，試題描述為英文，比賽時間為5個小時，前四個小時可以實時看到排名，最後一小時封榜，無法看到排名。

3.競賽可以使用的語言：Java, C, C++, Kotlin 和 Python。

4.重點考察選手的演算法和程序設計能力，不考察實際工程中常用的系統編程，多線程編程等等；

5.選手可攜帶任何非電子類資料，包括書籍和列印出來的程序等，部分賽區會對選手攜帶的紙質資料做限制。

6.評委負責將結果（正確或出錯的類型）通過網路盡快返回給選手，除此之外不提供任何額外幫助；

7.每個題目對應一種顏色的氣球，通過該題目的隊伍會得到對應顏色氣球。每道題目第一支解決掉它的隊還會額外獲得一個「FIRST PROBLEM SOLVED」的氣球。

⑼ 演算法設計比賽做什麼演算法好

應該是ACM吧
就是給你8-10道演算法題目，5個小時，做出來多的題目數越多，排名越靠前，如果題目數一樣多的看用的時間。
時間的計算方法如下：
例如你A題用了20分鍾AC，然後B題有用了30分鍾AC（此時是比賽開始50分鍾），又用了30分鍾AC了C題，那麼你的時間（penalty ）是
20 + 50 + 80 = 150分鍾

比賽中常用的演算法有
1。動態規劃
2。搜索
3。貪心
4。圖論
5。組合數學
6。計算幾何
7。數論
等

推薦到
http://acm.pku.e.cn
http://acm.zju.e.cn
http://acm.h.e.cn
http://acm.timus.ru
這幾個OJ上練習

比較好的題目分類（POJ上的）
1。這個是我最喜歡的
初期:
一.基本演算法:
(1)枚舉. (poj1753,poj2965)(2008-10-27Done 位運算+寬搜)
(2)貪心(poj1328,poj2109,poj2586)
(3)遞歸和分治法.
(4)遞推.
(5)構造法.(poj3295)
(6)模擬法.(poj1068,poj2632,poj1573,poj2993,poj2996)
二.圖演算法:
(1)圖的深度優先遍歷和廣度優先遍歷.
(2)最短路徑演算法(dijkstra,bellman-ford,floyd,heap+dijkstra)(2008-08-29Done)
(poj1860,poj3259,poj1062,poj2253,poj1125,poj2240)
(3)最小生成樹演算法(prim,kruskal)
(poj1789,poj2485,poj1258,poj3026)
(4)拓撲排序 (poj1094)(2008-09-01Done)
(5)二分圖的最大匹配 (匈牙利演算法) (poj3041,poj3020)
(6)最大流的增廣路演算法(KM演算法). (poj1459,poj3436)
三.數據結構.
(1)串 (poj1035,poj3080,poj1936)
(2)排序(快排、歸並排(與逆序數有關)、堆排) (poj2388,poj2299)
(3)簡單並查集的應用.
(4)哈希表和二分查找等高效查找法(數的Hash,串的Hash)
(poj3349,poj3274,POJ2151,poj1840,poj2002,poj2503)
(5)哈夫曼樹(poj3253)(2008-09-02Done)
(6)堆
(7)trie樹(靜態建樹、動態建樹) (poj2513)(2008-10-23Done 並查集、歐拉)
四.簡單搜索
(1)深度優先搜索 (poj2488,poj3083,poj3009,poj1321,poj2251)
(2)廣度優先搜索(poj3278,poj1426,poj3126,poj3087.poj3414)
(3)簡單搜索技巧和剪枝(poj2531,poj1416,poj2676,1129)
五.動態規劃
(1)背包問題. (poj1837,poj1276)
(2)型如下表的簡單DP(可參考lrj的書 page149):
1.E[j]=opt{D+w(i,j)} (poj3267,poj1836,poj1260,poj2533)
2.E[i,j]=opt{D[i-1,j]+xi,D[i,j-1]+yj,D[i-1][j-1]+zij} (最長公共子序列)
(poj3176,poj1080,poj1159)
3.C[i,j]=w[i,j]+opt{C[i,k-1]+C[k,j]}.(最優二分檢索樹問題)
六.數學
(1)組合數學:
1.加法原理和乘法原理.
2.排列組合.
3.遞推關系.
(POJ3252,poj1850,poj1019,poj1942)
(2)數論.
1.素數與整除問題
2.進制位.
3.同餘模運算.
(poj2635, poj3292,poj1845,poj2115)
(3)計算方法.
1.二分法求解單調函數相關知識.(poj3273,poj3258,poj1905,poj3122)
七.計算幾何學.
(1)幾何公式.
(2)叉積和點積的運用(如線段相交的判定,點到線段的距離等). (poj2031,poj1039)
(3)多邊型的簡單演算法(求面積)和相關判定(點在多邊型內,多邊型是否相交)
(poj1408,poj1584)
(4)凸包. (poj2187,poj1113)(2008-08-29Done)
中級:
一.基本演算法:
(1)C++的標准模版庫的應用. (poj3096,poj3007)
(2)較為復雜的模擬題的訓練(poj3393,poj1472,poj3371,poj1027,poj2706)
二.圖演算法:
(1)差分約束系統的建立和求解. (poj1201,poj2983)(2008-09-05Done)
(2)最小費用最大流(poj2516,poj2516,poj2195)
(3)雙連通分量(poj2942)
(4)強連通分支及其縮點.(poj2186)
(5)圖的割邊和割點(poj3352)
(6)最小割模型、網路流規約(poj3308, )
三.數據結構.
(1)線段樹. (poj2528,poj2828,poj2777,poj2886,poj2750)
(2)靜態二叉檢索樹. (poj2482,poj2352)
(3)樹狀樹組(poj1195,poj3321)
(4)RMQ. (poj3264,poj3368)
(5)並查集的高級應用. (poj1703,2492)
(6)KMP演算法. (poj1961,poj2406)(2008-09-16Done)
四.搜索
(1)最優化剪枝和可行性剪枝
(2)搜索的技巧和優化 (poj3411,poj1724)
(3)記憶化搜索(poj3373,poj1691)

五.動態規劃
(1)較為復雜的動態規劃(如動態規劃解特別的施行商問題等)
(poj1191,poj1054,poj3280,poj2029,poj2948,poj1925,poj3034)
(2)記錄狀態的動態規劃. (POJ3254,poj2411,poj1185)
(3)樹型動態規劃(poj2057,poj1947,poj2486,poj3140)
六.數學
(1)組合數學:
1.容斥原理.
2.抽屜原理.
3.置換群與Polya定理(poj1286,poj2409,poj3270,poj1026).
4.遞推關系和母函數.

(2)數學.
1.高斯消元法(poj2947,poj1487, poj2065,poj1166,poj1222)
2.概率問題. (poj3071,poj3440)
3.GCD、擴展的歐幾里德(中國剩餘定理) (poj3101)
(3)計算方法.
1.0/1分數規劃. (poj2976)
2.三分法求解單峰(單谷)的極值.
3.矩陣法(poj3150,poj3422,poj3070)
4.迭代逼近(poj3301)
(4)隨機化演算法(poj3318,poj2454)
(5)雜題.
(poj1870,poj3296,poj3286,poj1095)
七.計算幾何學.
(1)坐標離散化.
(2)掃描線演算法(例如求矩形的面積和周長並,常和線段樹或堆一起使用).
(poj1765,poj1177,poj1151,poj3277,poj2280,poj3004)
(3)多邊形的內核(半平面交)(poj3130,poj3335)
(4)幾何工具的綜合應用.(poj1819,poj1066,poj2043,poj3227,poj2165,poj3429)
高級:
一.基本演算法要求:
(1)代碼快速寫成,精簡但不失風格
(poj2525,poj1684,poj1421,poj1048,poj2050,poj3306)
(2)保證正確性和高效性. poj3434
二.圖演算法:
(1)度限制最小生成樹和第K最短路. (poj1639)
(2)最短路,最小生成樹,二分圖,最大流問題的相關理論(主要是模型建立和求解)
(poj3155, poj2112,poj1966,poj3281,poj1087,poj2289,poj3216,poj2446
(3)最優比率生成樹. (poj2728)
(4)最小樹形圖(poj3164)
(5)次小生成樹.
(6)無向圖、有向圖的最小環
三.數據結構.
(1)trie圖的建立和應用. (poj2778)(2008-10-26Done 矩陣A^n)
(2)LCA和RMQ問題(LCA(最近公共祖先問題) 有離線演算法(並查集+dfs) 和 在線演算法
(RMQ+dfs)).(poj1330)
(3)雙端隊列和它的應用(維護一個單調的隊列,常常在動態規劃中起到優化狀態轉移的
目的). (poj2823)
(4)左偏樹(可合並堆).
(5)後綴樹(非常有用的數據結構,也是賽區考題的熱點).
(poj3415,poj3294)
四.搜索
(1)較麻煩的搜索題目訓練(poj1069,poj3322,poj1475,poj1924,poj2049,poj3426)

(2)廣搜的狀態優化:利用M進制數存儲狀態、轉化為串用hash表判重、按位壓縮存儲狀態、雙向廣搜、A*演算法. (poj1768,poj1184,poj1872,poj1324,poj2046,poj1482)
(3)深搜的優化:盡量用位運算、一定要加剪枝、函數參數盡可能少、層數不易過大、可以考慮雙向搜索或者是輪換搜索、IDA*演算法. (poj3131,poj2870,poj2286)
五.動態規劃
(1)需要用數據結構優化的動態規劃.
(poj2754,poj3378,poj3017)
(2)四邊形不等式理論.
(3)較難的狀態DP(poj3133)
六.數學
(1)組合數學.
1.MoBius反演(poj2888,poj2154)
2.偏序關系理論.
(2)博奕論.
1.極大極小過程(poj3317,poj1085)
2.Nim問題.
七.計算幾何學.
(1)半平面求交(poj3384,poj2540)
(2)可視圖的建立(poj2966)
(3)點集最小圓覆蓋.
(4)對踵點(poj2079)
八.綜合題.
(poj3109,poj1478,poj1462,poj2729,poj2048,poj3336,poj3315,poj2148,poj1263)

2。這個每個分類的題目比較多，適合作為第一個分類的擴展
說明：遞推算動歸， 離散化算數據結構， 並查集算數據結構， 博弈算動歸， 麻煩題一般都是不錯的綜合題， 最短路算圖論，數據的有序化算排序
麻煩題：1697, 1712, 1713, 1720, 1729, 1765, 1772, 1858, 1872, 1960, 1963, 2050, 2122, 2162, 2219, 2237,
簡單題目：1000, 1003, 1004, 1005, 1007, 1046, 1207, 1226, 1401, 1504, 1552, 1607, 1657, 1658, 1674, 1799, 1862, 1906, 1922, 1929, 1931, 1969, 1976, 2000, 2005, 2017, 2027, 2070, 2101, 2105, 2109, 2116, 2136, 2160, 2190, 2232, 2234, 2275, 2301, 2350, 2363, 2389, 2393, 2413, 2419, 推薦：1063, 1064, 1131, 1140, 1715, 2163,
雜題：1014, 1218, 1316, 1455, 1517, 1547, 1580, 1604, 1663, 1678, 1749, 1804, 2013, 2014, 2056, 2059, 2100, 2188, 2189, 2218, 2229, 2249, 2290, 2302, 2304, 2309, 2313, 2316, 2323, 2326, 2368, 2369, 2371, 2402, 2405, 2407, 推薦：1146, 1147, 1148, 1171, 1389, 1433, 1468, 1519, 1631, 1646, 1672, 1681, 1700, 1701, 1705, 1728, 1735, 1736, 1752, 1754, 1755, 1769, 1781, 1787, 1796, 1797, 1833, 1844, 1882, 1933, 1941, 1978, 2128, 2166, 2328, 2383, 2420,
高精度：1001, 1220, 1405, 1503,
排序：1002, 1318, 1877, 1928, 1971, 1974, 1990, 2001, 2002, 2092, 2379, 2388, 2418, 推薦：1423, 1694, 1723, 1727, 1763, 1788, 1828, 1838, 1840, 2201, 2376, 2377, 2380,
搜索容易：1128, 1166, 1176, 1231, 1256, 1270, 1321, 1543, 1606, 1664, 1731, 1742, 1745, 1847, 1915, 1950, 2038, 2157, 2182, 2183, 2381, 2386, 2426, 不易：1024, 1054, 1117, 1167, 1708, 1746, 1775, 1878, 1903, 1966, 2046, 2197, 2349, 推薦：1011, 1190, 1191, 1416, 1579, 1632, 1639, 1659, 1680, 1683, 1691, 1709, 1714, 1753, 1771, 1826, 1855, 1856, 1890, 1924, 1935, 1948, 1979, 1980, 2170, 2288, 2331, 2339, 2340,
數據結構容易：1182, 1656, 2021, 2023, 2051, 2153, 2227, 2236, 2247, 2352, 2395, 不易：1145, 1177, 1195, 1227, 1661, 1834, 推薦：1330, 1338, 1451, 1470, 1634, 1689, 1693, 1703, 1724, 1988, 2004, 2010, 2119, 2274,
動態規劃容易：1018, 1050, 1083, 1088, 1125, 1143, 1157, 1163, 1178, 1179, 1189, 1208, 1276, 1322, 1414, 1456, 1458, 1609, 1644, 1664, 1690, 1699, 1740, 1742, 1887, 1926, 1936, 1952, 1953, 1958, 1959, 1962, 1975, 1989, 2018, 2029, 2033, 2063, 2081, 2082, 2181, 2184, 2192, 2231, 2279, 2329, 2336, 2346, 2353, 2355, 2356, 2385, 2392, 2424, 不易：1019, 1037, 1080, 1112, 1141, 1170, 1192, 1239, 1655, 1695, 1707, 1733, 1737, 1837, 1850, 1920, 1934, 1937, 1964, 2039, 2138, 2151, 2161, 2178, 推薦：1015, 1635, 1636, 1671, 1682, 1692, 1704, 1717, 1722, 1726, 1732, 1770, 1821, 1853, 1949, 2019, 2127, 2176, 2228, 2287, 2342, 2374, 2378, 2384, 2411,
字元串：1488, 1598, 1686, 1706, 1747, 1748, 1750, 1760, 1782, 1790, 1866, 1888, 1896, 1951, 2003, 2121, 2141, 2145, 2159, 2337, 2359, 2372, 2406, 2408,
貪心：1042, 1065, 1230, 1323, 1477, 1716, 1784,
圖論容易：1161, 1164, 1258, 1175, 1308, 1364, 1776, 1789, 1861, 1939, 1940, 1943, 2075, 2139, 2387, 2394, 2421, 不易：1041, 1062, 1158, 1172, 1201, 1275, 1718, 1734, 1751, 1904, 1932, 2173, 2175, 2296, 網路流：1087, 1273, 1698, 1815, 2195, 匹配：1274, 1422, 1469, 1719, 2060, 2239, Euler：1237, 1637, 1394, 2230, 推薦：2049, 2186,
計算幾何容易：1319, 1654, 1673, 1675, 1836, 2074, 2137, 2318, 不易：1685, 1687, 1696, 1873, 1901, 2172, 2333, 凸包：1113, 1228, 1794, 2007, 2187,
模擬容易：1006, 1008, 1013, 1016, 1017, 1169, 1298, 1326, 1350, 1363, 1676, 1786, 1791, 1835, 1970, 2317, 2325, 2390, 不易：1012, 1082, 1099, 1114, 1642, 1677, 1684, 1886,
數學容易：1061, 1091, 1142, 1289, 1305, 1306, 1320, 1565, 1665, 1666, 1730, 1894, 1914, 2006, 2042, 2142, 2158, 2174, 2262, 2305, 2321, 2348, 不易：1067, 1183, 1430, 1759, 1868, 1942, 2167, 2171, 2327, 推薦：1423, 1450, 1640, 1702, 1710, 1721, 1761, 1830, 1930, 2140,

⑽ acm競賽的演算法總共有那些范圍 求大牛概括......

初級:
一.基本演算法:
(1)枚舉. (poj1753,poj2965)
(2)貪心(poj1328,poj2109,poj2586)
(3)遞歸和分治法.
(4)遞推.
(5)構造法.(poj3295)
(6)模擬法.(poj1068,poj2632,poj1573,poj2993,poj2996)
二.圖演算法:
(1)圖的深度優先遍歷和廣度優先遍歷.
(2)最短路徑演算法(dijkstra,bellman-ford,floyd,heap+dijkstra)
(poj1860,poj3259,poj1062,poj2253,poj1125,poj2240)
(3)最小生成樹演算法(prim,kruskal)
(poj1789,poj2485,poj1258,poj3026)
(4)拓撲排序 (poj1094)
(5)二分圖的最大匹配 (匈牙利演算法) (poj3041,poj3020)
(6)最大流的增廣路演算法(KM演算法). (poj1459,poj3436)
三.數據結構.
(1)串 (poj1035,poj3080,poj1936)
(2)排序(快排、歸並排(與逆序數有關)、堆排) (poj2388,poj2299)
(3)簡單並查集的應用.
(4)哈希表和二分查找等高效查找法(數的Hash,串的Hash)
(poj3349,poj3274,POJ2151,poj1840,poj2002,poj2503)
(5)哈夫曼樹(poj3253)
(6)堆
(7)trie樹(靜態建樹、動態建樹) (poj2513)
四.簡單搜索
(1)深度優先搜索 (poj2488,poj3083,poj3009,poj1321,poj2251)
(2)廣度優先搜索(poj3278,poj1426,poj3126,poj3087.poj3414)
(3)簡單搜索技巧和剪枝(poj2531,poj1416,poj2676,1129)
五.動態規劃
(1)背包問題. (poj1837,poj1276)
(2)型如下表的簡單DP(可參考lrj的書 page149):
1.E[j]=opt{D[i]+w(i,j)} (poj3267,poj1836,poj1260,poj2533)
2.E[i,j]=opt{D[i-1,j]+xi,D[i,j-1]+yj,D[i-1][j-1]+zij} (最長公共子序列)
(poj3176,poj1080,poj1159)
3.C[i,j]=w[i,j]+opt{C[i,k-1]+C[k,j]}.(最優二分檢索樹問題)
六.數學
(1)組合數學:
1.加法原理和乘法原理.
2.排列組合.
3.遞推關系.
(POJ3252,poj1850,poj1019,poj1942)
(2)數論.
1.素數與整除問題
2.進制位.
3.同餘模運算.
(poj2635, poj3292,poj1845,poj2115)
(3)計算方法.
1.二分法求解單調函數相關知識.(poj3273,poj3258,poj1905,poj3122)
七.計算幾何學.
(1)幾何公式.
(2)叉積和點積的運用(如線段相交的判定,點到線段的距離等). (poj2031,poj1039)
(3)多邊型的簡單演算法(求面積)和相關判定(點在多邊型內,多邊型是否相交)
(poj1408,poj1584)
(4)凸包. (poj2187,poj1113)