美國計算機奧林匹克競賽
![]() |
美国计算机奥林匹克竞赛(USA Computing Olympiad,USACO)是美国一项面向中学生的信息学竞赛,首次举行于1993年。
題庫訓練
USACO提供一個題庫可供全世界所有的信息學競賽選手進行訓練。題庫共有6個chapter,為六檔難度的試題。每一個chapter中一般有4~5個section,每一個section集中介紹某一類型的試題。在section的開頭一般會有一篇算法介紹,然後有4~5道試題。每一道試題都可以提交USACO服務器評測。與一般的在線評測系統不同的是,USACO不僅會告訴你評測結果,還會提供給你所有的測試數據。另外,在通過一道題之後,還會提供USACO自己撰寫的題解,只是在交上去之後,你的程序並不能被保存,所以不能從上面得到你的源代碼。
USACO的訓練題庫具有非常強的順序性。除非將某一個section中所有試題都通過,你無法得到下一個section的算法介紹和試題。這訓練了信息學競賽選手面對棘手的問題和錯誤時堅持不懈的品質,但也在某種程度上為選手造成了麻煩。
USACO極為重視對算法時間效率與優化水平的考察,很多試題必須要進行非常細緻的優化才能夠通過。幾個典型的例子如Checker Challenge, Cryptcowgraphy, Latin等。
當選手完成所有6個chapter的訓練之後,可以向USACO的總教練申請開放額外的訓練頁進行進一步的訓練。
比賽
一般來說USACO在每年的12,1,2,3,4月份會組織月賽[1],一月一次。其中4月份的比賽是US Open (公開賽)。每一場月賽都會有4組構成,分別是鉑金組,金組、銀組、銅組,難度依次遞減。進入更高一組一般有兩種方式:在10月份的資格賽中取得較好的成績,或者在某一次月賽中取得該組領先的地位。一般來說選手不會被降組。
通常情況下一次比賽的時間為3~4小時,選手需要完成3~4道題目。選手可以在該次月賽指定的時間範圍(通常是4天,覆蓋一個周末)中的任何一個時間打開題目,並在規定的時間內完成比賽並提交。注意先用一個帳戶打開題目閱讀,然後使用另一個帳戶打開題目提交被明確定義為作弊,在比賽結束之前泄露、發布題目也應該被認為是不妥當的。
每一次比賽的官方版本為英語版。一般在比賽頁面上還會出現其他語言的版本,它們是由已經參加本次月賽的選手進行翻譯的。USACO規則明確聲明它不對除英語外其他版本的正確性與準確性負責。因此選手應該儘可能使用英語版本。
月賽的題目與IOI試題類型大致相同,絕大多數為傳統試題,但也在極少數情況下出現過提交答案類型試題。鉑金組難度與中國省選、NOI相當,金組的試題的平均難度不及IOI試題,但比NOIP難度要高,部分試題可以達到甚至超過IOI試題的難度。銀組試題與NOIP提高組的試題難度相當而略低,銅組試題難度與NOIP普及組難度大致相等,有的難度更低。
月賽結束後1~2天你可以通過電子郵箱收到你的程序的評測結果。同時在比賽相應的頁面上你可以找到測試數據、題解、所有參賽選手的程序代碼、所有參賽選手的成績總表以及對比賽的簡要分析、統計與總結。
注意事項
USACO規則中明確規定「直接輸出答案」是作弊行為。換言之,選手在本機上計算得到答案,然後提交一個直接輸出答案的程序是不被允許的(這種技術一般被稱為「打表」)。但是這種行為在絕大多數中學信息學競賽與大學程序設計競賽中都是合法的。
根據USACO規則,程序的運行與結果必須完全是確定性的。換言之,在程序中使用時間函數初始化隨機種子是不被允許的。
選手在參加比賽時可以使用書上、互聯網上或者自己曾經寫過的代碼,無論代碼是否是由選手自己寫的。但是使用這些代碼的時候選手必須將其明確注釋出來,否則被認為是作弊。另外,除非特別聲明,選手必須獨立完成試題,任何其他人的幫助都是被禁止的。
USACO可以接受的語言包括C++, Java, Pascal, Python, C[2]。
參考文獻
外部連結
- USACO官方網站 (頁面存檔備份,存於網際網路檔案館)
- The USACO training pages (頁面存檔備份,存於網際網路檔案館)
- The USACO contest pages
- IOI官方網站 (頁面存檔備份,存於網際網路檔案館)
- Nocow-中文翻譯較好的網站,已經停止維護
- USACO Training Gateway Problems and Solutions 提供了詳細的解題的思考過程 對初學者非常有幫助 (頁面存檔備份,存於網際網路檔案館)
參見
|