演算法導論acm

① 關於acm與數學的一些問題

1.計算機裡面的「數學」與傳統數學還是有區別的。傳統數學主要圍繞「有窮和無窮」、「離散和連續」、「概率」來展開，而計算機裡面的「數學」主要則是「演算法的可行性分析」，也就是說，給你一個問題，那麼要怎麼樣將它符號化，且能用計算機表示出來，用計算機表示出來了後，用怎麼樣的演算法去解決他。所以，你要學指導方法，可以去看些演算法可行性的書籍。
2.編程主要是培養可行性。因為計算機的計算能力很強，但是他也只是個計算機，不會自動計算，他需要人類定義些計算規則。編程，就是找一些規則，使計算機能計算出想要的東西。
3.你學的是高級語言（如C C++ C# java VF等），他們不在內存上操作（匯編語言在內存上工作）。計算機的每一次計算的時間與計算機的配置有關，我們能做的，只是用比較好的演算法去減少時間。
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、計算幾何——計算幾何相比於其它部分來說是比較獨立的，就是說它和其它的知識點很少有過多的結合，較常用到的部分包括——線段相交的判斷、多邊形面積的計算、內點外點的判斷、凸包等等。計算幾何的題目難度不會很大，但也永遠不會成為最弱的題。

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初學者！

③ 你好，我是新手，不太了解這些，想請教下，DP 是什麼意思，還有關於ACM，您有什麼好的方法嗎

DP是動態規劃。。是acm中一個非常非常重要的演算法。。
我們老師說 不會DP和搜索 永遠是菜鳥。。。
DP是一種思想，就是把復雜的問題 分解成很多簡單子問題，解決了所有子問題就相當於解決了大問題。。。
關於acm。。
先學一門語言。。完了去各大OJ刷水題（就是做簡單題，幾乎不牽扯演算法的題。），鍛煉邏輯思維，鍛煉思維的縝密，鍛煉代碼能力。。
我們老師說先刷500道水題在學演算法。= =~！ 覺得有點……。。
（就是告訴我們先多刷水題。。。）
水題杭電OJ 很多（11頁和16頁有中文水題，適合新手）。。http://acm.h.e.cn
水題刷的差不多了，在學 演算法，數據結構。。
演算法 先看 演算法導論。。之後再看看劉汝佳的 黑書（演算法藝術與信息學競賽）。
黑書 對新手來說很難，所以先看 演算法導論。。。
要是把這兩本書看好了 那你也算是一隻牛了。。
關鍵還是刷題。。

④ ACM 的正確入門方式是什麼

如下：

第一階段：先刷水題，水題，就是幾乎不牽扯演算法。需要自己想方法解決。這樣的題，一是鍛煉邏輯思維和思維的嚴謹，二是鍛煉代碼能力。一般做到200題左右。

第二階段：漸漸的學一些簡單的演算法。第二階段刷到400題。

第三階段： 在第二階段的基礎上繼續糾結演算法。 這時候可以看演算法導論了。學習數據結構。繼續刷題。刷到600左右。

介紹

ACM是一個世界性的計算機從業員專業組織，創立於1947年，是世界上第一個科學性及教育性計算機學會，目前在全世界130多個國家和地區擁有超過10萬名的會員。ACM是全世界計算機領域影響力最大的專業學術組織。

⑤ 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需要學什麼

其實acmer們都是自己訓練的啊，這種東西只能自己學哈~先從基本的開始吧，把c/c++練熟了，java要掌握一些。然後就是演算法上的東西了。演算法的學習是比較痛苦的，書建議看演算法導論，演算法藝術與信息學競賽，具體數學，柔性字元串匹配，然後是去各大oj上訓練做題，推薦poj，zoj，hdoj，還有各種比賽。下面是詳細的訓練方法~

訓練方法。現在這個賽季基本就算結束了，所以可以從自身能力開始提升，先把演算法掌握的全面一些。模擬，數學，計算幾何，圖論，數據結構，動態規劃，搜索，字元串匹配，貪心，這些知識都要進行學習。如果來不及的話，盡量保證，每一塊知識都能有兩個人覆蓋到，這樣三人組隊，可以保證穩定發揮。個人訓練可以自己做題，按各個知識點來。也可以穿插著去做做比賽，topcoder的srm和codeforces都很不錯，還有zoj的月賽。這都是平時練習的好機會。

比賽前一兩個月，要進行隊伍磨合。組隊做一些比賽，可以去hust的oj上自己掛比賽。注意分配幾時，然後讀題要仔細，分題的時候要清醒，千萬別覺得這個題可做，就直接搞，一定要和隊友商量。卡題的時候，切記不要沖動，亂交會導致罰時飆升啊，那樣很痛苦的。

然後熱身賽記得測一下longlong類型的輸出是用lld還是I64d，然後放平心態就可以了~

⑦ ACM 指導

acm是3人一組的，以學校為單位報名的，也就是說要得到學校同意，還要有2個一起搞的。其實可能是你不知道你們學校搞acm的地方，建議你好好詢問下你們學校管科技創新方面的人。建議你找幾個興趣相同的一起做，互相探討效果好多了，團隊合作也是acm要求的3大能力之一。
數據結構遠遠不夠的，建議你看演算法導論，黑書，oj的話個人覺得還是poj好，有水題有好題，而且做的人多，要解題報告什麼的也好找。我們就是一些做acm的學生一起搞，也沒老師，這樣肯定能行的。

基礎的話是語言，然後數據結構，然後演算法。
ACM有三個方向：演算法，數學，實現
要求三種能力：英文，自學，團隊協作
簡單的說，你要能讀懂英文的題意描述，要有一門acm能使用的編程語言，要會數據結構，有一點數學基礎，一點編程方面天賦，要有興趣和毅力（最重要），就具有做ACM的基本條件了。

做acm我推薦c，c++也可以，java在某些情況下好用，但是大多數情況的效率和代碼量都不大好，所以建議主用c++，有些題目用java

還有什麼問題，可以問我啊。

不好意思，沒見過用java描述的acm書籍，大多數是用偽命令，其他有的用的c，c++，老一些的用pascal。java只是用來做高精度的一些題的，個人覺得不用專門看這方面的書，java的基本部分學好就夠用了。所以我還是推薦主用c++，在高精度和個別題再用java。你可以找找java描述的演算法設計與分析，這個好像有

⑧ ACM初學者要學習的內容

ACM國際大學生程序設計競賽：知識與入門.pdf

鏈接: https://pan..com/s/19OY2FJUkk4RhW5WTsPkwfQ

《ACM國際大學生程序設計競賽:知識與入門》適用於參加ACM國際大學生程序設計競賽的本科生和研究生，對參加青少年信息學奧林匹克競賽的中學生也很有指導價值。

⑨ 高中生能看懂演算法導論嗎

演算法導論不是一本noi參賽選手應該看的書。理論性太強，學得慢、而且演算法不夠深刻。如果你只學習了語言，那麼ls推薦的《演算法藝術》也不適用，你想參加的應該是noip，noi是在noip上一個層次的全國比賽，到了noi水平應該看的是演算法藝術而不是演算法導論，《演算法藝術》在當當網上有買

不過現在關於noip的書幾乎都是用pascal語言寫的，我當時學的時候也是用pascal，現在轉了c＋＋。所以我推薦的書都是pascal寫的。。。《奧賽經典》和《全國青少年信息學奧林匹克教程》，如果你不習慣，可以選擇買大學的acm教程來看（acm是大學生的全球性信息學競賽，大學生幾乎都用c、c＋＋或者java，書多用c和c＋＋寫），配套做poj（1l推薦的那個網站～）

另外你可以關注一下noi、noip競賽官網 http://www.noi.cn
還有oier經常去的網站 www.oibh.org/bbs 可以上去問題、找資料

ps，數學知識也很重要，其他文化科可以放，數學已經要跟上～

祝成功～

⑩ acm初學者有參考書推薦嗎

買本奧賽輔導書吧，其他的書寫的精，但是不全。譬如數據結構書中有圖論、排序的一些演算法，但一般不會深入講數論、動態規劃之類。專講演算法的書還好一些。其實吃透往屆的試題是最好的。