acm競賽的演算法

A. 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，做好資料收集和整理工作

B. 什麼叫acm程序設計與演算法分析

acm程序設計與演算法分析
這不復雜,

C. 參加acm競賽，請問需要掌握哪些演算法請行家指點，謝謝

看你要到什麼層次了？
搜索，動態規劃，數論，組合數學，計算幾何，圖論，博弈，數據結構...

D. 請教做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+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)

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>構造樹的最小環

E. ACM常用的經典演算法

1.明白內存在演算法中的用處
2.二分查找 二分冥（a^b）
3.如果是計算機的，學數據結構的時候花點時間在二叉樹上
4.遞歸
5.廣搜 深搜 做點隱式圖的題目 順便學下狀態的hash
6.最短路（spfa dij floyd） 我感覺可以當做搜索的優化
7.簡單動態規劃 背包等
8.要是你喜歡幾何的話也可以看看幾何中的一些基礎知識 我感覺幾何比較難拿分

接下可以學下線段樹等一些數據結構（線段樹可以優化很多問題，二叉樹知道了，二分思想有了，線段樹的基本操作可以秒殺）

接下去可以深入動態規劃了。

接下去不歸路在向你招手。

F. acm要學習哪些演算法

最基本的、也是最核心的，掌握各種數據結構及其對應的高效演算法，比如線性結構（順序表、鏈表等）的查找、排序演算法，樹（二叉樹、搜索樹）的原理、基礎的遍歷、查找演算法，圖的原理、演算法、應用場景。
學完之後就可以開始到各種OJ刷題了。

G. ACM動態規劃問題（演算法競賽入門經典）

遞歸就不說了，明顯是需要棧的邏輯結構維護的。簡單說說對遞推和DP的個人見解，只供參考。

DP=狀態+狀態轉移方程
狀態的關鍵特點是無後效性，簡單地舉例：奧運會某項目淘汰賽1/N決賽，成績只跟以後的比賽有關，之前的成績不帶入（只考慮賽制）。如果你發現一個狀態後面階段決策需要用到前面階段的狀態信息，那麼這就不是一個標準的DP。比如：
A - B1 - C1 - D
\-- EX ------/
如果將EX歸為B段或C段，那麼EX-D或者A-EX就跨越了跳躍了一個階段，對於這個階段來說他後面的階段就用到了前面階段的狀態信息
當然這並不意味著不能採用DP演算法，對於上面的例子，可以將EX本身拆為B2 - C2就可以滿足DP條件了，對於連續狀態的DP，類似的調整更多。

狀態轉移方程是狀態到狀態的決策
簡單地說，就是貪心的那一部分，多條路你選擇一條路的過程

很多時候，遞推和DP難以區分，一般情況，狀態轉移決策明顯是「選擇」的時候，會當做DP，而如果計算比重較大，會當做遞推；狀態調整比較多時，可能認為是遞推；連續狀態可以歸為DP。
例：M*N的的帶權格子，從左上走到右下，每次只能向右或下移動一格，求權值加和最大（小）的路徑條數。

還有一個相關詞叫做「遞推規劃」，有興趣的話可以自己看下相關資料

解釋之後答案很明顯：DP要有狀態轉移方程。甚至可以說DP的關鍵就是狀態轉移方程。
你的第一個問題，希望你把書名報一下，我貌似沒有白皮的

H. ACM 中常用的演算法有哪些

排序（選擇，冒泡，快速，歸並，堆，基數，桶排序等）
遞歸，回溯
概率，隨機
公約數，素數
因數分解
矩陣運算
線性規劃
最小二乘
微積分
多項式分解和級數
圖論演算法：
哈夫曼樹（即最優二叉樹）
哈希表
Prim,Kruskal演算法（即最小生成樹演算法）
紅黑樹
a-B剪枝法
深、廣度搜索
拓撲排序
強連通分量
Dijkstra,Bellman-Ford,Floyd-Warashall演算法（最短路徑演算法）
計算幾何（線段相交，凸包，最近點對）

I. 關於ACM競賽

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

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

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

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