acm演算法模板

1. ACM題目求解題思路

有N個石子,每個石子重量Qi；按順序將它們裝進K個筐中；求一種方案，使得最重的筐最輕。 分析：本題乍一看很容易想到動態規劃。事實上的確可以用動態規劃解決，稍加分析我們很快得到一個簡單的演算法。用狀態f(i,k)表示將前i個石子裝入k個筐最優方案，g(i,j)表示i-j中最重的石子，則可以寫出狀態轉移方程：g(i,j)=max {g(i,j-1),Qj}f(i,j)=min max {f(k , j-1), g(k+1 , i)} | 1<=j<=k邊界條件：g(i,i)=Qi,f(1,1)=g(1,1)很明顯，這個演算法的時間復雜度為O(N3),空間復雜度為O(N2)，並不十分理想。經過一些優化可以將復雜度降為O(N2)，不過這樣思維復雜度驟然加大，且演算法本身仍不夠高效。現在已經很難在原動態規劃模型上做文章了，我們必須換一個思路。按一般的想法，順序將石子裝入筐，即先把石子放入第一筐，放到一定時候再改放第二個筐，第三個筐……但由於筐的重量沒有上限，我們無法知道放到什麼時候可以停止，轉而將石子放入下一個筐。此時，問題的難點已經顯露出來，是不是有方法可以化解呢？我們不妨針對上面的難點，加入一個參數P，改求一個判定可行解問題：每個筐石子重量和不能超過P，是否可以用K個筐裝下所有石子。首先經過分析不難發現，如果當前筐的石子總重量為T1，即將處理的石子重量為T2，若T1+T2 ≤P，則我們仍將該石子放入當前框，這是顯而易見的。由此可以得出貪心演算法，按順序把石子放進筐，若將石子放入當前筐後，筐的總重量不超過P，則繼續處理下一個石子；若重量和超過P，則將該石子放入下一個筐，若此時筐的數目超過K，則問題無解，否則處理完所有石子後就找到了一個可行解。以上演算法時間復雜度O(N),空間復雜度O(N)，這都是理論的下界。現在我們已經解決了可行解問題，再回到原問題。是不是可以利用剛才的簡化過的問題呢？答案是肯定的。一個最簡單的想法是從小到大枚舉P，不斷嘗試找最優解為P的方案（這就是剛才的可行解問題），直到找到此方案。這就是題目的最優解。估算一下上面演算法的時間復雜度。令T=∑Qi，則最壞情況下需要枚舉T次才能找到解，而每次判斷的時間復雜度為O(N)，因此總的時間復雜度為O(TN)，故需要做進一步優化。下面考慮答案所在的區間。很明顯，若我們可以找到一個總重量不超過P』的解，則我們一定能找到一個總重量不超過P』+1的解，也就是說，可行答案必定可以位於區間[q,+∞]（其中q為本題最優解）。因此，我們自然而然的聯想到了二分，具體方法為：在區間[1,T]內取中值m，若可以找到不超過m的方案，則嘗試區間[1,m-1];若不能，嘗試區間[m+1,T]。不斷重復以上步驟即可找到問題的最優解。分析一下採用二分法後演算法總的時間復雜度：由於每次除去一半的區間，則一共只需判斷log2N次，而每次判斷的時間復雜度為O(N)，因此這個演算法總的時間復雜度為O(NlgT)。一般而言，這個復雜度可以令人滿意的，並且實際使用中效果非常好。但該復雜度同權值有關，不完全屬於多項式演算法，我們可以繼續求得一個多項式演算法（該演算法與本文核心內容無關，只作簡單探討）。首先，此問題的答案必定為某一段連續石子的和，而段數不超過n2，因此，我們最多隻要判斷log2N2=2log2N次即可。現在新的問題是如何找到第m大的段。首先，以每個石子開頭的所有段，例如：3 2 1 2，以2開頭的所有段：2；2 1； 2 1 2， 由於每個石子的重量都大於0，因此總和一定是遞增的。現在有n個遞增段，如何快速的找到第k大的數呢？設各段長度為L1,L2,…,LN,中點分別為M1,M2,…,MN，我們每次詢問各段中點的大小，若L1/2+L2/2+..+LN/2>k，則找到權值最大的中點，刪去其後的數（下圖中紅色部分），否則找到權值最小的中點，刪去其前面的部分（下圖中黑色部分），可以證明刪去的一定不是所求的數。 註：上圖中每個各格子代表一個數。 由以上可知每次可以去掉某一段的1/2，因為有n段，故總共需要去O(Nlog2N)次，每次找最小最大值可以用堆實現，復雜度僅為O(lgN)，因此總的時間復雜度為O(lg2N)，而由上文我們知道找中值的操作總共有log2N次，故這個演算法的時間復雜度為O(Nlg3N)。 至此我們終於得到了一個多項式級別的演算法，當然這個演算法實現起來比較麻煩，實際效果也不甚理想，不過具有一定的理論價值，在此不做過多討論。 回顧本題解題過程，首先我們得到了一個動態規劃演算法，由於很難再提高其效率，因此我們另闢蹊徑，尋求新的演算法。在分析過程中我們發現由於筐的重量沒有上限，因此很難確定將多少石子放入同一個筐內。為了解決此難點，我們加入了參數P，改求可行解問題。參數的加入實際上就是強行給筐定了一個上界。正是由於這無形之中多出的條件，使得問題立刻簡單化，於是我們很自然的得到了貪心演算法。而最終使用二分法降低了演算法的時間復雜度，成功地解決了問題。 由上面的例子我們得到了此類解法的一般步驟，通常分為兩步：Ⅰ.首先引入參數P，解決子問題：能否找到一個不優於P的方案Ⅱ.從小到大枚舉P，判斷是否有優於P的方案，直到找出原問題的最優解 一般地，參數搜索可以通過二分法或迭代降低時間復雜度，由於迭代法證明比較復雜，所以本文更多的討論二分法。 這個方法的應用比較廣泛，通常情況下和上例一樣求最大（小）值盡量小（大）的題目都可以採用此方法，比如下面的例子。神秘的山：有n個隊員攀登n個山峰，每個隊員需要選擇一個山峰，隊員們攀登的山峰各不相同，要求最後一個登頂的隊員用的時間盡量短。 分析：本問題分為兩個部分解決：1．求出每個隊員攀登到各個山峰所需的時間；2．找一個最優分配方案。 第一部分屬於幾何問題，我們可以枚舉每個隊員攀登山峰的位置再做簡單的判斷（題目規定攀登點必須為整點，這就為枚舉提供了條件），這樣就可求得隊員們攀登上各個山峰所需的時間。下面重點討論第二部分。首先將我們的數據構圖，很明顯，我們得到的是一個二部圖，假設有3個隊員3個山峰，每個隊員攀登的時間如下 山峰1山峰2山峰3隊員1132隊員2222隊員3133 則我們可以構圖，每條邊附上相應的權值： 現在的任務就是在圖中找一個匹配，匹配中權值最大的邊盡量小。這個問題是否可以直接套用一些常見的模型呢？比如最大匹配或是最佳匹配？經過分析不難發現在這個問題中它們都是不足以勝任的，因此我們不得不做新的嘗試。 上文提到過要求極大（小）值盡量小（大）的題目往往先定出上界比較容易下手，那麼這題也採用類似的思路。引入一個參數T，先求一個判定可行解的子問題：找一個方案，要求最後登山的隊員所用時間不超過T。 改變後的題目有什麼不同之處呢？如果隊員i攀登上山峰j所需的時間超過T，則可以認為他在規定時間內不能攀登上山峰j，我們就可以把這條邊從圖中刪去。例如在上例中找一個不超過2的方案，經過一次「篩選」，保留的圖如下。 經過這次過濾保留下來的邊都是「合法邊」，我們只需要在這個新的二部圖中找一個完備匹配即可，一個完備匹配唯一對應著一個可行方案。而找完備匹配可以借用最大匹配的演算法，因為如果一個二部圖的最大匹配數等於N，則找到了一個完備匹配，否則該圖中將不存在完備匹配。（上圖中的紅色表示一個完備匹配），那麼這一步的時間復雜度為O(NM)，而在本題中M=N2，因此我們可以在O(N3)的時間內判斷出是否存在一個方案滿足最後等上山頂的隊員時間不超過T。 最後，再用二分法枚舉參數T，找到最優解。由於答案必定為某個隊員攀登上其中一個山峰的時間，因此我們開始的時候可以將所有數據排序，這樣最終的時間復雜度為O(N3lgN)。引入參數後求可行解的子問題與原問題最大的區別在於定下上界以後，我們很自然的排除了一些不可取條件，從而留下了「合法」條件，使得問題變的簡單明了。. 上面的例子在增加了上界之後，排除了一些無效條件，其實它的作用絕不僅局限於此，有些時候，它能將不確定條件變為確定條件，比如下面的例子，最大比率問題：有N道題目,每道題目有不同的分值和難度,分別為Ai,Bi；要求從某一題開始, 至少連續選K道題目,滿足分值和與難度和的比最大。 分析：最樸素的想法是枚舉下標i』,j』，得到每一個長度不小於K的連續段，通過累加Ai』->Aj』，Bi』->Bj』求出比值，並找出比最大的一段。這樣做的時間復雜度很高，由於總共有N2段，每次計算比值的時間是O(N)，則總的時間復雜度到達O(N3)，不過計算比值時，可以採用部分和優化，這樣能把復雜度降至O(N2)，但仍然不夠理想。我們需要追求更出色的演算法，先考慮一個簡單的問題——不考慮難度（Bi），僅僅要求分值和最大（當然此時分值有正有負）。這個簡化後的問題可以直接掃描，開始時為一個長度為K的段，設為Q1,Q2,…Qk， 每次添加一個新數，若Q1+Q2+..+QL-K小於0，則把它們從數列中刪去，不斷更新最優解即可。這樣我們就能在O(N)的時間內找到長度不小於k且和最大的連續段。 之所以能成功解決簡化後的問題，是由於該問題中每個量對最終結果的影響是確定的，若其小於0，則對結果產生不好的影響，反之則是有益的影響。那麼原問題每個參數對最終結果的影響是不是確定的呢？很遺憾，並不是這樣，因為每個題目有兩個不同的參數，他們之間存在著某些的聯系，而這些聯系又具有不確定性，故我們很難知道它們對最終結果是否有幫助。想解決原問題，必須設法消除這個不確定因素！那麼有沒有辦法將這些不確定的因素轉化成確定的因素呢？此時，引入參數勢在必行！那麼我們引入參數P，求一個新的問題：找一個比值不小於P的方案。這個問題實際就是求兩個下標i』,j』，滿足下面兩個不等式j』-i』+1≥k ①(Ai』+Ai』+1....+Aj』)/(Bi』+Bi』+1…+Bj』) ≥ p ②由不等式②=>Ai』+Ai』+1....+Aj』 ≥p(Bi』+Bi』+1…+Bj』)整理得(Ai』-pBi』)+(Ai』+1-pBi』+1)…+(Aj』-pBj』) ≥0可以令Ci=Ai-pBi，則根據上面不等式可知問題實際求一個長度不小於k且和大於０的連續段。由之前的分析可以知道我們能在O(N)的時間內求出長度不小於k且和最大的連續段，那麼如果該段的和大於等於０，則我們找到了一個可行解，如果和小於０，則問題無解。也就是說，我們已經能在O(N)的時間內判斷出是否存在比值不小於P的方案，那麼接下來的步驟也就順理成章了。我們需要通過二分法調整參數P，不斷逼近最優解。計算一下以上演算法的時間復雜度，設答案為T，則該演算法的時間復雜度為O(NlgT)，雖然這並不是多項式級別的演算法，但在實際使用中的效果非常好。引入參數後，由於增加了一個條件，我們就可以將不確定的量變為確定的量，從而解決了問題。三． 總結 本文主要通過幾個例子說明了參數搜索法在信息學中的應用，從上文的例子可以看出加入參數一方面能大大降低思維復雜度，另一方面也能得到效率相當高的演算法，這使得我們解最解問題又多了一中有力的武器。當然，任何事物都是具有兩面性的。參數搜索在具有多種優點的同時也有著消極的一面。由於需要不斷調整參數逼近最優解，其時間復雜度往往略高於最優演算法，且通常依賴於某個權值的大小，使得我們得到的有時不是嚴格意義上的多項式演算法。文章中還總結了使用此方法解題的一般步驟，在實際應用中，我們不能拘泥於形式化的東西，必須靈活應用，大膽創新，這樣才能游刃有餘的解決問題。

2. 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方面有所收獲。

3. acm總是超時，有簡單演算法嗎

當然有，首先求整除9的個數不需要一個個試，求含有9的也可以按位數遞歸。
//求某個正整數中，小於自身，且含有數字9或能被9整除的正整數的個數。
/*思路分析：
求含有數字9的總數 + 能被9整除的總數 - 既含有數字9又能被9整除的個數
具體思路：從高位到低位求含有數字9的范圍 - 此范圍內能被9整除的個數
還要 + 此范圍外的低位范圍內的結果（進行遞歸調用），
最後加上所有能被9整除的正整數個數。
如此可將大整數n劃分
*/
如下圖我先寫求整除9的函數，為保證字函數正確性，寫了一個暴力演算法進行比對。如下圖

#include<iostream>
usingnamespacestd;
#include<stdlib.h>
#include<time.h>
//求某個正整數中，小於自身，且含有數字9或能被9整除的正整數的個數。
/*思路分析：
求含有數字9的總數+能被9整除的總數-既含有數字9又能被9整除的個數
具體思路：從高位到低位求含有數字9的范圍-此范圍內能被9整除的個數
還要+此范圍外的低位范圍內的結果（進行遞歸調用），
最後加上所有能被9整除的正整數個數。
如此可將大整數n劃分
*/
//暴力驗證演算法
intsumOfDivided9_B(inta,intb){ //求介於a到b(不含b)之間的能被9整除的個數
intsum=0;
for(;a<b;a++){ //暴力演算法做驗證
if(0==a%9)sum++;
}returnsum;
}
//求介於a到b(不含b)之間的能被9整除的個數，（用戶需保證a<b）
intsumOfDivided9(constint&a,constint&b){
return(b-1)/9-(a-1)/9; //即1~b-1減去1~a-1
}
intmain(){
srand(time(0)); //隨機數種子
intcount=0; //錯誤的個數
for(inti=0;i<100;i++){
inta=rand(),b=a+1+rand()%10000; //隨機生成范圍，最多10000個數
intsum_B=sumOfDivided9_B(a,b); //暴力演算法
intsum_Q=sumOfDivided9(a,b); //快速演算法
if(sum_B!=sum_B){
cout<<"WRONG! ";
count++;
}elsecout<<"RIGHT√ ";
cout<<"(a="<<a<<")%9="<<a%9<<" (b="<<b<<")%9="<<b%9<<
" 暴力="<<sum_B<<" 快速="<<sum_Q<<endl;
}
cout<<"WRONGtotal="<<count<<endl;
system("pause");
}

未完待續！

4. 我是用的是C語言，想在黑龍江省ACM大賽中拿三等獎,應該掌握那些演算法……

當中有幾百種計算機常用的演算法的框架和模板，如果你還在為演算法問題而困擾時，這資料會讓你廓然開朗，我也在學，很有用所以極力推薦給你.

框架部分目錄如下：

圖論

路徑問題

0/1邊權最短路徑

BFS

非負邊權最短路徑（Dijkstra）

可以用Dijkstra解決問題的特徵

負邊權最短路徑

Bellman-Ford

Bellman-Ford的Yen-氏優化

差分約束系統

Floyd

廣義路徑問題

傳遞閉包

極小極大距離/極大極小距離

EulerPath/Tour

圈套圈演算法

混合圖的EulerPath/Tour

HamiltonPath/Tour

特殊圖的HamiltonPath/Tour構造

生成樹問題

最小生成樹

第k小生成樹

最優比率生成樹

0/1分數規劃

度限制生成樹

連通性問題

強大的DFS演算法

無向圖連通性

割點

割邊

二連通分支

有向圖連通性

強連通分支

2-SAT

最小點基

有向無環圖

拓撲排序

有向無環圖與動態規劃的關系

二分圖匹配問題

一般圖問題與二分圖問題的轉換思路

最大匹配（OK）

有向圖的最小路徑覆蓋

0/1矩陣的最小覆蓋

完備匹配（OK）

最優匹配（OK）

穩定婚姻

網路流問題

網路流模型的簡單特徵和與線性規劃的關系

最大流最小割定理

最大流問題（OK）

有上下界的最大流問題

循環流

最小費用最大流/最大費用最大流

弦圖的性質和判定

組合數學

解決組合數學問題時常用的思想

逼近

遞推/動態規劃

概率問題

Polya定理

計算幾何/解析幾何

計算幾何的核心：叉積/面積

解析幾何的主力：復數

基本形

點

直線，線段

多邊形

凸多邊形/凸包

凸包演算法的引進，卷包裹法

Graham掃描法

水平序的引進，共線凸包的補丁

完美凸包演算法

相關判定

兩直線相交

兩線段相交

點在任意多邊形內的判定

點在凸多邊形內的判定

經典問題

最小外接圓

近似O(n)的最小外接圓演算法

點集直徑

旋轉卡殼，對踵點

多邊形的三角剖分

數學/數論

高精度計算

高數度加減法、乘除法

最大公約數

Euclid演算法

擴展的Euclid演算法

同餘方程/二元一次不定方程

同餘方程組

線性方程組

高斯消元法

解mod2域上的線性方程組

整系數方程組的精確解法

矩陣

行列式的計算

利用矩陣乘法快速計算遞推關系

分數

分數樹

連分數逼近

數論計算

求N的約數個數

求phi(N)

求約數和

快速數論變換

……

素數問題

概率判素演算法

概率因子分解

數據結構

組織結構

二叉堆

左偏樹

二項樹

勝者樹

跳躍表

樣式圖標

斜堆

reap

統計結構

樹狀數組

虛二叉樹

線段樹

矩形面積並

圓形面積並

關系結構

Hash表

並查集

路徑壓縮思想的應用

STL中的數據結構

vector

deque

set/map

動態規劃/記憶化搜索

動態規劃和記憶化搜索在思考方式上的區別

最長子序列系列問題

最長不下降子序列

最長公共子序列

一類NP問題的動態規劃解法

樹型動態規劃

背包問題

動態規劃的優化

四邊形不等式

函數的凸凹性

狀態設計

規劃方向

線性規劃

常用思想

二分

最小表示法

串

KMP

Trie結構

後綴樹/後綴數組

LCA/RMQ

有限狀態自動機理論

排序

選擇/冒泡

快速排序

堆排序

歸並排序（OK）

基數排序

拓撲排序

排序網路