USACO計算機奧賽2月月賽考試試題分析

USACO計算機奧賽2月月賽考試試題分析

本次 USACO 月賽賽題的特點分析。實際上，這已經(jīng)是不知道第幾次打破常規(guī)套路的 USACO 月賽了：雖然各組晉級得分依然穩(wěn)定在 700~750 之間，但不僅題目難度不按題號順序而遞增，而且就連同組別的賽題都不會拒絕同質(zhì)化。

這一現(xiàn)象同時出現(xiàn)在了青銅組和白銀組的賽題中：青銅組的第 1 題和第 3 題，思路甚至是代碼實現(xiàn)，都是高度類似的;而白銀組的第 1 題和第 2 題，都涉及到二分查找這一經(jīng)典的思想方法。

最后，關(guān)于 USACO 系列賽事的賽題難度。這其實對于已經(jīng)了解了 USACO 賽事的讀者來說，算是一個老生常談的問題了——從青銅組到黃金組，絕大多數(shù)賽題所涉及的知識點，一般不會超過國內(nèi) CSP-J 考察知識點范圍太多，往屆的賽題，可能直到黃金組才涉及到一些國內(nèi)提高組階段的圖論算法的編碼。而本次的賽題，除了白金組和黃金組的第 2 題，涉及到樹形動態(tài)規(guī)劃這一算法，其余的 8 道題在知識點層面上，絕未超過 CSP-J 的考察范圍。甚至可以說，多知道一些算法，對于解題甚至沒有好處：比如白銀組的第 3 題，了解過一些圖論算法的讀者，可能會以為那道題需要 Bellman-Ford 算法尋找圖中的負環(huán)，但實際上，該題僅需在學(xué)而思課程中 Z3 上學(xué)期階段學(xué)習到的 BFS 算法即可解決。

所以，要將所有低級組別的賽題拿到滿分，只需要學(xué)習過幾個對應(yīng)的知識點就夠了嗎?完全不夠。因為這就涉及到了 USACO 系列賽題與國內(nèi)信息學(xué)競賽，尤其是 CSP-J 的一個很大不同：尤其是對于初學(xué)信息學(xué)競賽的入門者而言，USACO 賽題是沒有像 CSP-J 第一題那樣的送分題的，每一道題都需要參賽者對問題做適當?shù)姆治雠c變形，未必能剛讀完題就馬上產(chǎn)生非常明確的思路。而在緊張的比賽節(jié)奏中，將精力更多放在讀題和問題分析，而非編碼中，雖然是進階學(xué)習者比較適應(yīng)的節(jié)奏，但初學(xué)者往往會對這樣的比賽節(jié)奏感到焦慮，從而亂了陣腳。其實這樣的題，用大家平常經(jīng)常看到卻又略覺抽象的一句話來說，就是“重視考察思維”。實際上，信息學(xué)競賽試題的難點從文本閱讀和套路掌握，遷移至更加靈活的“具體問題具體分析”能力的考察，也是國內(nèi)競賽的一個趨勢。每一套令人拍案叫絕的 USACO 賽題，其實都是在提醒我們的選手自己。