USACO通關·總結·推薦題目

[對應 Cowboy 版]

從08年11月到09年三月，USACO Training 全部通關。

USACO給人的感覺與Vijos、Rqnoj、Zerojudge等完全不同。USACO的題目都是很少、很精的內容，整個題庫的運作都給人十分嚴謹的感覺。記得有一次RK很快就回覆了我的信件把我的一道源代碼發回給我。覺得USACO應該是一個專業的團隊在維護的。

這段時間真的是很拼命地在刷題。簡單的說，這段時間許多個noons和evenings都在USACO旁度過~不是想upset那些為jz的新晚玩命弄了好久的人，我那晚上就沒去看新晚在刷題。（當然那是有客觀原因和主觀原因的，不只是USACO的原因，那天心情特別遭，然後就不適合去看聯歡的場面了~）後來還是勉強弄了學校的video隨便看了一兩段比較受歡迎的節目。包括春晚我也沒看。這個就沒再怎麼看了。所以……也沒有玩女生。[color: #d1dce9;]

總結一些讓我impression很深的題目：

[這個只是我個人印象深刻，一般來說前面的題目你就只當是一樂，後面的題目就真的很經典。]

Your ride is here [ride] 我注冊過3個號，這道題寫過3遍，但別的號就沒再做下去了。

Greedy Gift Givers [greedy]& The Clocks [clock] & SuperPrime Rib

一道做出二次AC。在Vijos上同樣拿USACO的程式AC了。

Packing Rectangles [packrec]

很WS的題目。寫了我很久，其實只是相對當時的題目。USACO總是認為難的只有algorithm而實現都是很簡單的。所以這樣的題目都……

Checker Challenge

用了位運算，後來啊zgdAC時我才知道原來可以用樸素的方法加上對稱性剪枝AC【這個是原文的Hint，都怪我只看翻譯】

The Castle [castle]

第一道Floodfill，給我印象很深，不是因為題目好。第一次聽這個種子填充法是在初二~

Bessie Come Home [comehome]

第一次寫非Dijkstra的最短路

Shaping Regions [rect1]

同樣卡了我很久~最後在_gXX關於矩形切割的做法啟發下AC。同樣是和啊cong一樣的。AC掉這個之前我先跳到後面了，第一次跳。

Contact [contact]

用了位運算的統計，自以為第一道寫的可以作標程的題目，雖然我的程式用cong師兄的觀點是太長到WS的，不優美的。

Magic Squares [msquare]

很喜歡，很久之前看過。AC了之後推薦給啊yaolao，然後成了基礎班的題目。

Shopping Offers [shopping]

很巧妙的背包轉換。媲美    [鬱悶的金明]。

Camelot [camelot]

同樣卡了很久~很囧的啊lyk說這道題啊——SPFA嘛~暈，老是把有名的演算法掛在嘴邊，但是那個只是initialization而已【cong】。

Closed Fences [fence4]

計算幾何，其實我不能完美ac，有反例的，但是爲了判斷這樣的反例又會TLE。以後有時間再重新來看。

Electric Fence [fence3] 迭代加精演算法 [不要胡思亂想]

Fence Rails [fence8] 很強的搜索+剪枝。

Cryptcowgraphy [cryptcow] 很強的搜索，這道就是我除夕夜在做的題目。

Drainage Ditches [ditch] 第一次網路流。我的第一次~我怎麼沒去Forever F*** 過去呢？我到現在都沒F***過啊~後面的題目就F***不過了。

Cowcycle [cowcycle] 我怎麽覺得標程也會超時？這道題實際資料比題目描述水很多。

The primes [prime3] 搜索。編譯開關。

Pollutant Control [milk] & Telecowmunication [telecow] 很類似的題目。求網路的割集。這個還F***就不行了~：（

T T

Starry Night [starry] 我因為一個很普通的錯誤加上對錯誤資訊的錯誤理解，導致我快崩潰了。

All Latin Squares [latin] 樸素+ 置換理論剪枝。

自己理解了置換理論、學習了題解寫的。我的常數還是比較大，編譯開關我愛你。

Electric Fence [fence9] 皮克定理，三年級的知識。我寫過題解。我很傻很天真的想~其實很簡單，搞不懂為啥題解要什麽模擬退火。

Wisconsin Squares [wissqu] 只有一組資料【樣例】。

Milk Measuring [milk4] 巧妙的DFSID+DP。

Network of Schools [schlnet] 第一次接觸強連通分量。

Bigbarn [bigbrn] & A Rectanglar Barn [rectbrn] 放假集訓的時候sinya和slxg教我的。其實我用了同樣的懸線法AC，當然bigbrn可以用比較簡單的方法DP。

Betsy’s Tour [betsy] 很早之前就看過黑書的分析。剪枝不容易想，但是介紹過之後很好寫，雖然我的pascal常數還是很恐怖~編譯開關，我愛編譯開關。

Picture [picture] 不錯的題目。沒有用線段樹。

Hidden Password [hidden] 最小尾碼。我一直看錯題。用了比較法【類似KMP】【最小表示法】和二分法兩種方法AC。

Twofive [twofive]很強的IOI題目。記憶化搜索。真的我看題解都不知道怎麼實現。代碼太優美了。

Postal Vans [vans]很早看過野牛的solution。我參考了他對曲線的分類，但自己推導出DP方程。[和野牛差不多，不過我很快就加好了高精和優化Ac。]

Cowxor [cowxor] 這是我第六章第二次A的題目。其實大概在1月的時候就AC了。Sinya說用什麼排序二叉樹之類的，然後我使用字串的trie作字典。同樣Hash Table什麼應該也可以。這個題目難度只是在於規模。