資訊競賽題目

Reference: 推薦-好題（轉貼）

一.動態規劃

參考資料：劉汝佳《演算法藝術與資訊學競賽》《演算法導論》
推薦題目：

1. 簡單
2. 中等，經典TSP問題
3. 中等，狀態壓縮DP
4. 中等
5. 中等，樹形DP。 可參考《演算法藝術與資訊學競賽》動態規劃一節的樹狀模型
6. 中等，《演算法藝術與資訊學競賽》中的習題
7. 中等，《演算法藝術與資訊學競賽》中的習題
8. 中等，《演算法藝術與資訊學競賽》中的習題
9. 中等，遞推
10. 中等，需要減少冗餘計算
11. 中等，四邊形不等式的簡單應用
12. 較難，狀態壓縮DP，《演算法藝術與資訊學競賽》中有解答
13. 較難，《演算法藝術與資訊學競賽》中有解答
14. 較難，需要配合資料結構優化
15. 較難，寫起來比較麻煩
16. 較難
17. 難，樹形DP
18. 難，狀態壓縮DP，題目很有意思
19. 難
20. 非常難

二.搜索

參考資料：劉汝佳《演算法藝術與資訊學競賽》
推薦題目：

1. 簡單，深搜入門題
2. 中等，廣搜
3. 中等，廣搜
4. 較難，廣搜
5. 難，IDA*，迭代加深搜索，需要較好的啟發函數
6. 難，可重複K最短路，A*。 可參考:解題報告
7. 難，深搜剪枝，《演算法藝術與資訊學競賽》中有解答
8. 難，《演算法藝術與資訊學競賽》習題
9. 難，深搜
10. 較難，《演算法藝術與資訊學競賽》中有解答
11. 很難

三. 常用資料結構

參考資料：劉汝佳《演算法藝術與資訊學競賽》《演算法導論》
線段樹資料、樹狀陣列資料 (關於線段樹和樹狀陣列更多相關內容可在網上搜到)
尾碼陣列資料：[1] [2]
推薦題目

1. 較難，線段樹應用，《演算法藝術與資訊學競賽》中有解答
2. 簡單，線段樹應用矩形面積並，《演算法藝術與資訊學競賽》中有解答
3. 較難，線段樹應用: [解題報告]
4. 難，二維樹狀陣列。
5. 中等，線段樹應用。
6. 難，堆的應用，《演算法藝術與資訊學競賽》中有解答
7. 中等，左偏樹，二項式堆或其他可合併堆的應用。
8. 左偏樹參考、二項式堆參見《演算法導論》相關章節
9. 中等，並查集
10. 中等，字典樹
11. 較難，多串匹配樹[參考]
12. 難，尾碼陣列
13. 較難，最長公共子串，經典問題，尾碼陣列
14. 很難，尾碼陣列: [解題報告]
15. 很難，資料結構綜合運用

四.圖論基礎

參考資料：劉汝佳《演算法藝術與資訊學競賽》《演算法導論》《網路演算法與複雜性理論》謝政
推薦題目:

1. 簡單，歐拉路
2. 中等，無向圖割邊
3. 較難，無向圖雙連通分支
4. 中等，最小度限制生成樹，《演算法藝術與資訊學競賽》中有解答
5. 中等，最小比率生成樹，《演算法藝術與資訊學競賽》中有解答
6. 簡單，最短路問題
7. 中等，差分約束系統，Bellman-Ford求解，《演算法藝術與資訊學競賽》中有解答
8. 簡單，Bellman-Ford
9. 中等，網路流
10. 較難，網路流
11. 中等，二部圖最大匹配
12. 較難，二部圖最大匹配
13. 中等，二部圖最大權匹配 KM演算法參考《網路演算法與複雜性理論》
14. 較難，二部圖最大權匹配
15. 中等，LCA（最近公共祖先）問題 參考Tarjan's LCA algorithm 《演算法導論》第21章習題
16. 較難，2-SAT問題 [參考]
17. 較難，2-SAT問題
18. 較難，最小樹狀圖 參考《網路演算法與複雜性理論》中朱-劉演算法

五.數論及組合計數基礎

1. 簡單，素數判定，大數分解 參考演算法導論相關章節
2. 較難，Burnside引理
3. 中等，解模方程組
4. 中等，經典問題，波利亞定理
5. 難，極好的題目，Burnside引理+模線性方程組
6. 較難，需要數學方法，該方法在《具體數學》第七章有講
7. 簡單，矩陣快速乘法