2022年2月USACO競賽銀級的賽題難度解析！

美國計算機奧林匹克學術活動USACO 已經(jīng)是全美計算機含金量和競爭力最高的賽事之一。本賽季最后一次月賽USACO OPEN將在3月25日至28日舉行。2月賽已結(jié)束，今天對2022年2月USACO學術活動銀級的賽題難度解析！為學員們參加3月的OPEN組(3月25日-3月28日) 提供參考。USACO的關注度和參與度每年都在增加，難度也在逐漸提升！

距離3月月賽開始還有3周的時間，大家可以好好回顧總結(jié)一下之前兩場的題目，爭取在3月的比賽中取得突破性的結(jié)果！以下內(nèi)容是白銀級別的賽題解析，供同學們參考交流。

第1題

題目解析：

白銀級第一題可以直觀的看出，對于第i行里面的數(shù)，i后面的都不用考慮在內(nèi)，因為一開始拿到的就是i，不可能交換降級。所以我們可以從圖論的角度出發(fā)，左右分別建立節(jié)點，例如中的1-4，每次左邊的點可以根據(jù)喜好連接到右邊，最終我們需要盡可能匹配最多的邊（需要注意的是，每次選邊的時候，不能重復覆蓋點）。到這一步，題目轉(zhuǎn)化為二分圖的匹配問題，直接DFS求解。

第2題

題目解析：

第二題初步看似一個BFS搜索題目，每一個指令節(jié)點看做一個狀態(tài)，然后通過指令間的轉(zhuǎn)移，一步步到達重點。最多搜索層數(shù)為N層。但是這種方法會超越題目要求的內(nèi)存限制。本題應該通過二進制來表示所有指令的組合方式，通過一個數(shù)字表示一個狀態(tài)，然后將所有狀態(tài)序列計算出來并且按坐標排序，最后通過二分搜索來尋找查找需要的位置。需要注意的是，本題的二分搜索數(shù)組序列不再是單個數(shù)，而且坐標表示的序列，需要認為來定義優(yōu)先級。

第3題

題目解析：

第三題是模擬類題目，可以分析得出左邊的文件夾只能往下翻不能往上分。右邊的郵件可以往上翻，前提是將郵件挪動到左邊。可以一開始統(tǒng)計出需要搬運的郵件標號，例如1，2,3,4,5。每次遇到一個就搬到左邊。并且清空這個記錄。但是右邊遇到一個，需要搬運左邊的時候，要將左邊將下翻的前提是本郵件號前面的都已經(jīng)放置在左邊了，不滿足這個前提的話不能翻動左邊，只能接著翻動右邊。按照這種策略，最后判斷能否把所有郵件搬運到左邊，可以的話就是yes，否則就是no

想要獲取備賽計劃，考前查缺補漏、重點沖刺

快來掃下方二維碼咨詢，了解更多賽事信息及參賽經(jīng)驗分享~