USACO計(jì)算機(jī)奧賽2月月賽考試試題分析

USACO計(jì)算機(jī)奧賽2月月賽考試試題分析

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

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

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

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