acm演算法競賽入門和進階指南

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

如下：

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

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

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

介紹

ACM是一個世界性的計算機從業員專業組織，創立於1947年，是世界上第一個科學性及教育性計算機學會，目前在全世界130多個國家和地區擁有超過10萬名的會員。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拿獎應該不成問題，至於什麼獎，就因人而異了.

⑷ 請問ACM的正確入門方式是什麼

一般的入門順序：0. C語言的基本語法(或者直接開C++也行，當一個java選手可能會更受歡迎，並且以後工作好找，但是難度有點大)，【參考書籍：劉汝佳的《演算法競賽入門經典》，C++入門可以考慮《c++ primer plus》，java選手可以考慮《think in java》or中文版《java編程思想》，請遠離譚浩強...】可以選擇切一些特別水的題鞏固以及適應一下ACM中常見的輸入輸出格式...例如杭電著名的100題 Problem Set。 一些進階的演算法以及復雜一些的數據結構（樹狀數組 線段樹 平衡樹 後綴數組 二分圖匹配 網路流 費用流 割點 橋 強聯通 雙聯通 最近公共祖先 四大DP(數位dp 區間dp 狀壓dp 概率dp) 博弈論SG函數 ）更高深的技巧，更復雜的數據結構（樹鏈剖分，動態樹，可持久化線段樹，DLX，後綴自動機，迴文樹，斜率優化/單調隊列優化/四邊形優化DP，插頭dp，莫比烏斯反演......）這部分最能體現人與人的差異了...智商碾壓一般就在這部分。而要想拿到金牌，一般來說這些知識都要盡可能掌握。也許你會覺得性價比很低，學這么多東西，才"有可能」拿到牌子，但是收獲的不一定是物質的牌子，還有學習過程的苦辣酸甜的經歷（例如各種WA TLE RE MLE 之後的一次AC），還有和基友一起並肩作戰切套題的同甘共苦，而且還鍛煉了自己的學習能力（善用網路，谷歌，維基網路）。

⑸ 《演算法競賽入門經典訓練指南》pdf下載在線閱讀，求百度網盤雲資源

《演算法競賽入門經典 訓練指南 升級版》（劉汝佳）電子書網盤下載免費在線閱讀

資源鏈接：

鏈接:

書名：演算法競賽入門經典 訓練指南 升級版

作者：劉汝佳

出版社：清華大學出版社

出版年份：2021-5-1

內容簡介：

《演算法競賽入門經典——訓練指南（升級版）》是《演算法競賽入門經典（第2版）》一書的重要補充，旨在補充原書中沒有涉及或者講解得不夠詳細的內容，從而構建一個更完整的知識體系。本書通過大量有針對性的題目，讓抽象復雜的演算法和數學具體化、實用化。

《演算法競賽入門經典——訓練指南（升級版）》共包括6章，分別為演算法設計基礎、數學基礎、實用數據結構、幾何問題、圖論演算法與模型以及更多演算法專題。全書通過206道例題深入淺出地介紹了上述領域的各個知識點、經典思維方式以及程序實現的常見方法和技巧，並在章末給出了豐富的分類習題，供讀者查漏補缺和強化學習效果。

《演算法競賽入門經典——訓練指南（升級版）》題目多選自近年來ACM/ICPC區域賽和總決賽真題，內容全面，信息量大，覆蓋了常見演算法競賽中的大多數細分知識點。書中還給出了所有重要的經典演算法的完整程序，以及重要例題的核心代碼，既適合選手自學，也方便院校和培訓機構組織學生學習和訓練。

作者簡介：

劉汝佳，2000年3月獲得NOI2000全國青少年信息學奧林匹克競賽一等獎。大一時獲2001年ACM/ICPC國際大學生程序設計競賽亞洲-上海賽區冠軍和2002年世界總決賽銀牌。2004年至今共為 ACM/ICPC亞洲賽區命題二十餘道，擔任6次裁判和2次命題總監，並應邀參加IOI和ACM/ICPC相關國際研討會。曾出版《演算法競賽入門經典》《演算法競賽入門經典——訓練指南》《編程挑戰》等暢銷書。

陳鋒，任職於廈門宇道信隆信息科技有限公司，擔任技術總監職務，專注於人工智慧以及演算法技術在金融科技領域的應用。同時擔任四川大學ACM/ICPC演算法競賽集訓隊特邀指導老師，榕陽編程NOI、NOIP指導教練。所帶學員多次獲得ICPC金/銀牌，進入NOI省隊等。曾出版《演算法競賽入門經典——訓練指南》《演算法競賽入門經典——習題與解答》《演算法競賽入門經典——演算法實現》等暢銷書。

⑹ ACM初學者要學習的內容

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

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

《ACM國際大學生程序設計競賽:知識與入門》適用於參加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進階指南

大一上學期：
必學：
1.C語言基礎語法必須全部學會
a)推薦「語言入門」分類20道題以上
b)提前完成C語言課程設計
2.簡單數學題（推薦「數學」分類20道以上）
需要掌握以下基本演算法：
a)歐幾里德演算法求最大公約數
b)篩法求素數
c)康托展開
d)逆康托展開
e)同餘定理
f)次方求模
3.計算幾何初步
a)三角形面積
b)三點順序
4.學會簡單計算程序的時間復雜度與空間復雜度
5.二分查找法
6.簡單的排序演算法
a)冒泡排序法
b)插入排序法
7.貪心演算法經典題目
8.高等數學
以下為選修：
9.學會使用簡單的DOS命令（較重要）
a)color/dir//shutdown/mkdir(md)/rmdir(rd)/attrib/cd/
b)知道什麼是絕對路徑與相對路徑
c)學會使用C語言調用DOS命令
d)學會在命令提示符下調用你自己用C語言編寫的程序，並使用命令行參數給自己的程序傳參（比如自己製作一個file.exe實現與命令基本功能一致的功能）
e)學會編寫bat批處理文件
10.學會Windows系統的一些小知識，如設置隱藏文件，autoRun.inf的設置等。
11.學會編輯注冊表（包括使用注冊表編輯器regedit和使用DOS命令編輯注冊表）
12.學會使用組策略管理器管理(gpedit.msc)組策略。
大一下學期：
1.掌握C++部分語法，如引用類型，函數重載等，基本明白什麼是類。
2.學會BFS與DFS
a)迷宮求解（最少步數）
b)水池數目(NYOJ27)
c)圖像有用區域(NYOJ92)
d)樹的前序中序後序遍歷
3.動態規劃（15題以上），要學會使用循環的方法寫動態規劃，同時也要學會使用記憶化搜索的方法。
a)最大子串和
b)最長公共子序列
c)最長單調遞增子序列(O(n)與O(n log n)演算法都需要掌握)
d)01背包
e)RMQ演算法
4.學會分析與計算復雜程序的時間復雜度
5.學會使用棧與隊列等線性存儲結構
6.學會分治策略
7.排序演算法
a)歸並排序
b)快速排序
c)計數排序
8.數論
a)擴展歐幾里德演算法
b)求逆元
c)同餘方程
d)中國剩餘定理
9.博弈論
a)博弈問題與SG函數的定義
b)多個博弈問題SG值的合並
10.圖論：
a)圖的鄰接矩陣與鄰接表兩種常見存儲方式
b)歐拉路的判定
c)單最短路bellman-ford演算法dijkstra演算法。
d)最小生成樹的kruskal演算法與prim演算法。
11.學會使用C語言進行網路編程與多線程編程
12.高等數學
13.線性代數
a)明確線性代數的重要性，首先是課本必須學好
b)編寫一個Matrix類，進行矩陣的各種操作，並求編寫程序解線性方程組。
c)推薦做一兩道「矩陣運算」分類下的題目。
以下為選修，隨便選一兩個學學即可：
14.（較重要）使用C語言或C++編寫簡單程序來調用一些簡單的windows API，或者在linux下進行linux系統調用，其目的是明白什麼是API（應用程序介面）。
15.網頁設計
a)學習靜態網頁技術(html+css+javascript)
b)較具有藝術細胞的可以試試Photoshop
c)php或其它動態網頁技術
16.學習matlab，如果想參加數學建模大賽的話，需要學這個軟體。
大一假期（如果留校集訓）
1.掌握C++語法，並熟練使用STL
2.試著實現STL的一些基本容器和函數，使自己基本能看懂STL源碼
3.圖論
a)使用優先隊列優化Dijkstra和Prim
b)單源最短路徑之SPFA
c)差分約束系統
d)多源多點最短路徑之FloydWarshall演算法
e)求歐拉路(圈套圈演算法）
4.進行復雜模擬題訓練
5.拓撲排序
6.動態規劃進階
a)完全背包、多重背包等各種背包問題（參見背包九講）
b)POJ上完成一定數目的動態規劃題目
c)狀態壓縮動態規劃
d)樹形動態規劃
7.搜索
a)回溯法熟練應用
b)復雜的搜索題目練習
c)雙向廣度優先搜索
d)啟發式搜索(包括A*演算法，如八數碼問題)
8.計算幾何
a)判斷點是否在線段上
b)判斷線段相交
c)判斷矩形是否包含點
d)判斷圓與矩形關系
e)判斷點是否在多邊形內
f)判斷點到線段的最近點
g)計算兩個圓的公切線
h)求矩形的並的面積
i)求多邊形面積
j)求多邊形重心
k)求凸包
選修
9.可以學習一種C++的開發框架來編寫一些窗體程序玩玩（如MFC,Qt等)。
10.學習使用C或C++連接資料庫。
大二一整年：
1.數據結構
a)單調隊列
b)堆
c)並查集
d)樹狀數組
e)哈希表
f)線段樹
g)字典樹
2.圖論
a)強連通分量
b)雙連通分量（求割點，橋）
c)強連通分量與雙連通分量縮點
d)LCA、LCA與RMQ的轉化
e)二分圖匹配
i.二分圖最大匹配
ii.最小點集覆蓋
iii.最小路徑覆蓋
iv.二分圖最優匹配
v.二分圖多重匹配
f)網路流
i.最大流的基本SAP
ii.最大流的ISAP或者Dinic等高效演算法（任一）
iii.最小費用最大流
iv.最大流最小割定理
3.動態規劃多做題提高（10道難題以上）
4.數論
a)積性函數的應用
b)歐拉定理
c)費馬小定理
d)威樂遜定理
5.組合數學
a)群論基礎
b)Polya定理與計數問題
c)Catalan數
6.計算幾何
a)各種旋轉卡殼相關演算法
b)三維計算幾何演算法
7.理解資料庫原理，學會SQL語句
8.學好計算機組成原理
9.學習Transact-SQL語言，學會使用觸發器，存儲過程，學會資料庫事務等。
10.圖論二
a)網路流的各種構圖訓練（重要）
b)最小割與最小點權覆蓋等的關系（詳見《最小割模型在信息學競賽中的應用》一文）
c)次小生成樹
d)第k短路
e)最小比率生成樹
11.線性規劃
12.動態規劃更高級進階
13.KMP演算法
14.AC自動機理論與實現
15.博弈論之Alpha-beta剪枝