[USACO][TEXT] Section 1.1 Contest Problem Types

哈爾˙伯奇 (Hal Burch) 先生在 1999 年春假進行了一項分析,並得出了一個驚人的發現:程式設計只有 16 種類型!此外,前 80% 的題目包含在 IOI 中,而這 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)

然而最具有挑戰性的是組合問題,只要是涉及迴圈 (排列組合、子集等)。儘管這些概念非常「明顯」,但這些問題很難獲得正確。
如果你能掌握 40% 的題型,你將可以在 IOI 獲得銀牌。如果掌握 80% 的題型無疑地可以獲得金牌。當然,所謂的「掌握」是很難的!我們將提供大量的題目以便磨練你的技能。

,