競賽演算法

『壹』 演算法設計比賽做什麼演算法好

應該是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,

『貳』 演算法競賽的整體體系是什麼

演算法，都有自己的一套邏輯的。按邏輯計算即可。

『叄』 有哪些含金量高的演算法大賽可以參加

作為中興的老員工，這個時候我必須站中興了，咱們有最豐厚的獎金，最專業的評委，你，值得擁有！

『肆』 演算法競賽入門經典怎麼樣

從書本的編排上，就可以看出作者的確是用心在寫書。比如講，動態規劃一章，在介紹各種動態規劃基本問題時，我目前見過的所有演算法書都只給出最優值的那個值，而沒有考慮到競賽或其它需要時，對答案構造的需要。比如，如果一個題目真要你輸出字典序列最小的方案，可能會難倒很多人。而真正靠初學者自己要來領悟這樣一些方法，確實是需要不少時間的。諸如此類的用心書中還有很多，作者一個個演算法娓娓道來，卻又在初學者容易犯錯的地方給一些提示，感覺很好。 更難能可貴的是，作者作為ICPC WORLD FINAL銀牌得主，信息學國家隊教練，絲毫沒有架子，不會像高數、數分書上那麼多「顯然」、「很容易看出」之類直接來一個例子。但是，這並不說明行筆羅嗦，相反，更體現作者心思細膩，真去PKU做兩個題目就會發現，很多時候演算法正確是一方面，細節上不出錯又是一個方面，把"=="打成"="然後調一個多小時代碼，絕對是初學語言的時候常犯的錯誤。 但是，整本書沒有任何參考書目附於附錄，一來是對被參考書籍的作者的不尊重，二來不利於讀者進一步閱讀（比如動態規劃一章之後的習題推薦，基本全部來自於《programming challenge》一書的習題）。 總起來說，本書絕對值得一讀，即使是有演算法基礎的ACMER||OIer 期待後續兩本著作問世

『伍』 劉汝佳的《演算法競賽入門經典》該怎麼學

如果C++已經學會了，前面幾章可以快速過一遍主要看題，然後學後面的內容，幾何那一章NOIP應該不考。

根據實際情況選擇學習順序，至少把每一章的前幾節掌握，最好把例題重新做一遍，習題要看，要有思路，選擇幾題打成代碼。（時間充裕的話可以全寫），可以再買本訓練指南，這兩本書的主要內容掌握了，noip提高組就基本沒問題了。

介紹：

《演算法競賽入門經典(第2版)》是一本演算法競賽的入門與提高教材，把c/c++語言、演算法和解題有機地結合在一起，淡化理論，注重學習方法和實踐技巧。

全書內容分為12 章，包括程序設計入門、循環結構程序設計、數組和字元串、函數和遞歸、c++與stl入門、數據結構基礎、暴力求解法、高效演算法設計、動態規劃初步、數學概念與方法、圖論模型與演算法、高級專題等內容，覆蓋了演算法競賽入門和提高所需的主要知識點。

並含有大量例題和習題。書中的代碼規范、簡潔、易懂，不僅能幫助讀者理解演算法原理，還能教會讀者很多實用的編程技巧；書中包含的各種開發、測試和調試技巧也是傳統的語言、演算法類書籍中難以見到的。

『陸』 演算法藝術與信息學競賽：演算法競賽入門經典是C語言的，學java的想競賽的適合看嗎

你要參加比賽的話 不是很推薦用java去比賽。
首先編碼效率來說 c/C++要有優勢， 另外 C/C++效率 也快於java（雖然很多比賽都會給java放寬時限， 但都是基於C/c++ 標程來的）
我認識的競賽各種大牛中， 全是C/C++的 。當然高中這種是pascal（不過我沒用過，就不評論了）
java基本也都會， 某些java庫 在解決某些題目比較方便的時候才會用java。
語言 本身 很多都是共通的。如果LZ精通java的話， C/C++基礎的學習一下也不會太慢的
如果LZ想參加比賽 建議一定要學會C/C++，

『柒』 信息學競賽演算法和數據結構

其實書都是你抄我我抄你，最終來源都是集訓隊論文……

我們用的中學高級本，感覺不是很好，講得知識跨度很大……從回溯法到平衡樹……每個知識點就一道題……

奧賽經典還不錯，就是練習題太空了沒法實踐……

所以說還是需要結合一下……最好要有老師帶，當然有學長帶那是最好不過了……

『捌』 演算法競賽入門經典難么

《演算法競賽入門經典》是一本演算法競賽的入門教材，把C/C++語言、演算法和解題有機地結合在了一起，淡化理論，注重學習方法和實踐技巧。全書內容分為11章，包括程序設計入門、循環結構程序設計、數組和字元串、函數和遞歸、基礎題目選解、數據結構基礎、暴力求解法、高效演算法設計、動態規劃初步、數學概念與方法、圖論模型與演算法，覆蓋了演算法競賽入門所需的主要知識點，並附有大量習題。書中的代碼規范、簡潔、易懂，不僅能幫助讀者理解演算法原理，還能教會讀者很多實用的編程技巧。另外，書中包含的各種開發、測試和調試技巧也是在傳統的語言、演算法類書籍中難以見到的。
《演算法競賽入門經典》可作為全國青少年信息學奧林匹克聯賽（NOIP）的復賽教材及ACM國際大學。

『玖』 參加了國內的大數據，演算法競賽，可以得到什麼

不要抱著太功利的思想參加比賽。參加這種大型的比賽，獎勵或許很豐厚，也能夠讓自己的履歷好看點，但實際上我么你更應該看到，這場比賽給我們帶來怎樣的經歷，他能夠讓我們見識到更加開闊的世界，更多的新新聞，結識到更多有創意的人，這些寶貴的經歷才是帶給我最寶貴的財富。

『拾』 如何系統地學習 ACM 競賽方面的演算法

1）數據分析師：在擁有行業數據的電商、金融、電信、咨詢等行業里做業務咨詢，商務智能，出分析報告。

2）數據挖掘工程師：在多媒體、電商、搜索、社交等大數據相關行業里做機器學習演算法實現和分析。
3）科學研究方向：在高校、科研單位、企業研究院等高大上科研機構研究新演算法效率改進及未來應用。