Section 4.1
2010.08.26 TEXT Optimization Techniques
2010.10.19 PROB Beef McNuggets 多重背包+裴蜀定理
2011.08.07 PROB Fence Rails DFS+剪枝
2011.03.24 PROB Fence Loops DFS / 最小環(Floyd)
2011.08.10 PROB Cryptcowgraphy DFS+剪枝+字符串處理
Section 4.2
2011.08.10 TEXT "Network Flow" Algorithms
2011.03.19 PROB Drainage Ditches 最大流(Edmonds-Karp)
2011.03.19 PROB The Perfect Stall 最大流 / 二分圖最大匹配(Hungary)
2011.08.10 PROB Job Processing 二分+貪心
2011.08.11 PROB Cowcycles DFS+剪枝
Section 4.3
2011.08.11 TEXT Big Numbers
2011.08.08 PROB Buy Low, Buy Lower DP+統計方案數+高精度
2011.08.12 PROB The Primes DFS+剪枝
2011.08.12 PROB Street Race DFS判斷連通性
2011.08.11 PROB Letter Game 枚舉+優化
Section 4.4
2011.08.13 PROB Shuttle Puzzle 數學 / BFS
2011.08.13 PROB Pollutant Control 最小割
2011.08.16 PROB Frame Up 拓撲排序
Section 5.1
2011.08.17 TEXT Convex Hulls
2011.08.17 PROB Fencing the Cows 凸包(Graham-Scan)
2011.08.16 PROB Starry Night Floodfill + 模擬
2011.08.13 PROB Musical Themes 二分 / DP
Section 5.2
2011.08.17 PROB Snail Trail DFS
2011.08.17 PROB Electric Fences 模擬退火 / 局部搜索 / 隨機化搜索
2011.08.17 PROB Wisconsin Squares DFS
Section 5.3
2011.08.17 TEXT Heuristics & Approximate Searches
2011.08.18 PROB Milk Measuring DFS-ID + DP / DP
2011.08.18 PROB Window Area 矩形切割 + 模擬
2011.08.18 PROB Network of Schools 強連通分量(Tarjan)
2010.08.19 PROB Big Barn DP
Section 5.4
2011.08.18 PROB All Latin Squares DFS+剪枝 / DFS+置換群
2011.08.19 PROB Canada Tour DP / DP+刷表法
2011.08.20 PROB Character Recognition 統計 + DP
2011.08.19 PROB Betsy's Tour DFS+剪枝 / SCDP
2011.08.18 PROB TeleCowmunication 最小割
Section 5.5
2011.08.21 PROB Picture 離散化 + 掃描 / 線段樹
2011.08.20 PROB Hidden Passwords 枚舉+優化 / 最小后綴
2011.08.21 PROB Two Five Cantor展開 + DFS
Section 6.1
2011.08.21 PROB Postal Vans DP / SCDP
2011.08.21 PROB A Rectangular Barn DP(懸線法)
2011.08.21 PROB Cow XOR 枚舉+優化
大致學習了這些東西:
1. DFS, 以及常見的優化技巧
2. 二分法轉化為判定性問題
3. <string>的使用
4. 離散化思想
5. Tarjan算法(強連通分量)
6. 懸線法求最大子矩陣
7. Hungary算法(棋盤覆蓋, 最小路徑覆蓋)
8. 拓撲排序的DFS實現
9. DP的刷表法實現(白書P172)
10. Edmonds-Karp算法
11. Graham-Scan算法求凸包, 水平線實現
個人以為對于NOIp來說, USACO Training Chapter4之后的內容的主要價值在于訓練調試能力, DFS+剪枝的題目非常多, 對于訓練暴搜來說是很好的教材. 算法上的話, Chapter4以后的NOIp新內容只有二分法和DFS優化技巧, 但是對于算法組合能力的要求有了進一步提升, 只有基礎非常扎實才能在短時間內AC題目.
不過目前的調試能力仍然有限, 不太復雜的DFS可能需要30 ~ 50min, 較為復雜的DFS可能需要2~3h甚至更長的時間才能調試通過. 對于NOIp來說還是太長了, 簡單DFS應該在20min內調試成功, 復雜一些也應該在1h內調試成功. 這方面還需要進一步訓練.
這次寫USACO Training跳過了4道題, 分別是1.4的某道矩形, 3.4.1的計算幾何, 4.4.2和5.4.5的兩道最小割. 如果日后打算參加GDKOI/GDOI的話, 再彌補網絡流/SCDP/高級數據結構(Trie/線段樹/SBT/樹狀數組)這方面的內容. Chapter5和Chapter6的幾道題還是很難理解題解, 也沒有掌握.
不管怎么說, 我比一年前還是強了很多.