溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
再沒有比算法更讓人頭疼的東西了吧！
前兩天參加了一個編程大賽http://www.ijiami.cn/newsInfo?id=519&v=2，有感于算法，所以整理了這篇關于編程競賽的10個算法。
動態規劃（DP）似乎占據了大部分的編程競賽題目，乃至三分之一。當然，DP也不是一個學一次就Ok的單一算法。
這還取決于你是否把數據結構與算法放在同一個等級中考慮。如果你想要在編程競賽中一展風采的話，當然，有些數據結構是你應該熟悉的。其中最重要的有范圍樹（Range Tree，也被稱為線段樹或區間樹）和樹狀數組（BITs），也被稱作Fenwick樹。除此之外，許多DP算法使用了一個前綴和數組（prefix sum array）。
能想到的最精華的單一算法如下所列，排名不分先后。絕大多數非動態規劃問題似乎都是各種ad hoc網絡與數據結構，所以你只需要練習練習以熟練掌握它們。
（再一次聲明，我僅列出了滿足如下性質的算法：有單一輸入集；計算輸入集的某個函數；不攜帶輸入值之間的狀態。這些性質將下面的算法與數據結構區分開來。由定義，數據結構要保留狀態以及算法的等級，還有像是DP這樣的算法技術，它們并沒有前者所計算的某個具體函數。）
1.Eratosthenes篩法，或另一種素數篩法
2.深度優先搜索
3.廣度優先搜索
4.Dijkstra算法
5.Floyd–Warshall 算法
6.Either Kruskal算法 或稱 Prim算法
7.一些拓撲排序的實現，比如使用DFS
8.凸包（我推薦單調鏈算法）
9.坐標壓縮
10.Edmonds–Karp，或者Ford–Fulkerson方法的另一種實現；亦或預流推進算法；又或者，如果你在準備ACM codebook，那么就Dinic算法。
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
