2021年-2022年USACO美國計算機奧林匹克競賽

競賽|USACO計算機競賽全解 21-22年

引言

申請全球TOP大學無論是美國藤校還是英國G5都需要通過層層選拔，在眾(zhong) 多學生的申請資料中，如何才能脫穎而出？獲得全球重量級競賽金獎或者優(you) 異排名，幫助你成為(wei) 閃亮的那顆星。而伟德betvlctor1946的作用還不止於(yu) 此，在競賽的過程中拓展相關(guan) 領域的學術知識，讓參賽同學感受到學科的樂(le) 趣, 激發主動求學的好奇心，並能與(yu) 全球出類拔萃的學子們(men) 以公平的方式同台競技，以賽代學為(wei) 未來打下紮實基礎的同時升華學術背景。

如今進入一所你夢寐以求的頂尖大學的競爭(zheng) 程度比以往任何時候都要激烈。對於(yu) 國際TOP大學看重的不僅(jin) 僅(jin) 是一份漂亮的履曆、優(you) 異的常規成績或高GPA。招生官同時希望看到你的學術成就和豐(feng) 富的課外活動。這些活動可以包括優(you) 秀的暑期項目、學術比賽、誌願者項目和在你感興(xing) 趣的領域的實習(xi) 。USACO可以提升你申請任何一所大學的背景。那麽(me) 今天就請Simon老師來全麵剖析一下這項重量級賽事吧！

PART ONE--競賽介紹

--01 USACO計算機競賽的簡介

美國計算機奧林匹克(The United States of America Computing Olympiad)是為(wei) 美國中學生舉(ju) 辦的計算機編程比賽。USACO在學年期間為(wei) 學生提供四個(ge) 越來越難的水平的比賽:銅、銀、金和白金。USACO的參與(yu) 者提交五種語言之一的程序:C、c++、Java、Pascal和Python。參與(yu) 者通過在當前部門表現良好而晉級。為(wei) 期一周的夏季訓練營將從(cong) 24名決(jue) 賽選手中選出4名代表美國參加國際奧林匹克信息學競賽(IOI)。競賽|USACO計算機競賽全解 21-22年

【2021年全球賽季排行榜】

02 USACO計算機競賽的曆史

IOI國際信息學奧林匹克競賽是最負盛名的國際高中計算機競賽，由聯合國教育、科學及文化組織(教科文組織)於(yu) 1989年發起，是根據其他幾個(ge) 著名的國際高中奧林匹克競賽的精神設計的。1992年，威斯康星大學帕克賽德分校(University Of Wisconsin Parkside)的數學教授唐·皮勒(Don Piele)博士聽說了IOI，並成立了USACO，以便從(cong) 美國帶來一個(ge) 團隊來參加這次活動。參加1992年IOI的第一支美國隊是由國際計算機問題解決(jue) 大賽的頂尖個(ge) 人組成的。

在最初的20年裏，USACO由Don、主教練Rob Kolstad博士和一支敬業(ye) 的誌願者團隊領導，他們(men) 中的許多人都是過去IOI的前美國隊成員。唐和羅布從(cong) 管理USACO退休後，該組織目前由克萊姆森大學(Clemson University)計算機科學教授布萊恩·迪恩(Brian Dean)博士領導，並已經在USACO工作了20多年。

03 關(guan) 於(yu) IOI國際信息學奧賽

The International Olympiad in Informatics (IOI)國際信息學奧林匹克競賽是一項年度競賽項目，也是麵向中學生的國際科學奧林匹克競賽之一。這是繼國際數學奧林匹克之後的第二大科學奧林匹克競賽，參與(yu) 國家數量眾(zhong) 多。1989年在保加利亞(ya) 普拉維茨舉(ju) 行了第一次IOI。2021年的國際信息學奧賽則在新加坡舉(ju) 行。

競賽|USACO計算機競賽全解 21-22年

比賽包括兩(liang) 天的計算機編程/編碼和解決(jue) 算法性質的問題。要處理涉及大量數據的問題，不僅(jin) 需要程序員，還需要有創造性的程序員，他們(men) 可以想出程序員需要告訴計算機做什麽(me) 。最難的部分不是編程，而是背後的數學。IOI的學生以個(ge) 人為(wei) 基礎進行比賽，每個(ge) 參賽國最多有4名學生參賽。

PART TWO--競賽深度解析

--04 USACO計算機競賽的考試形式及計分方式

考試形式

USACO有四個(ge) 競賽 Divisions級別，Bronze, Silver, Gold,和Platinum。所有參賽者都是從(cong) 銅級賽區開始的。在每個(ge) 比賽賽周之後，如果參賽者有足夠高的分數就會(hui) 被“promoted”到下一個(ge) 級別--通常是600-800分(滿分1000分)。

你還可以在contest weekend中所有問題獲得滿分直接獲得晉升。每一組都比前一組困難得多。這通常需要相當多的學習(xi) 、訓練，試圖提升到一個(ge) 新的水平需要耗費的時間，每一個(ge) 等級長達一年或更長時間。

USACO在2015年增加了Platinum級別。在此之前，每一個(ge) division的難度都比現在大，大約相當於(yu) 今天的division“one step up”。例如，一般來說，“old Bronze”問題最接近“modern Silver”問題的難度。

計分方式

提交的3-4個(ge) 程序中的每一個(ge) 都要對10個(ge) 或更多的“test cases”進行測試——用已知的結果輸入程序中的數據集。您可以為(wei) 每個(ge) 給出正確結果的測試用例獲得學分。在一個(ge) contest weekend的比賽中，一個(ge) 組別的所有問題總共有1000分。如果您的程序運行時間太長，占用太多內(nei) 存，或者崩潰，那麽(me) 您將在測試用例中失去分數，因此代碼的效率是一個(ge) 因素!這在Silver及以上級別的賽組中尤其突出。

05 USACO計算機競賽的考試計時形式

比賽的計時形式是什麽(me) ？

在賽周的任何時候，進入網站並點擊按鈕啟動你的個(ge) 人比賽計時器，時間為(wei) 3-5個(ge) 小時。出發前你會(hui) 被告知確切的時間限製，通常是4小時。然後，選手將獲得競賽問題的訪問權限。

可以休息或提前停止，但一旦你在那個(ge) 周末點擊了“開始”按鈕，你的時間就會(hui) 一直在滴答作響，直到到期--不允許暫停。如果你隻是想檢查一下題目，那麽(me) 你可以隨意花時間嚐試它，想花多少時間就花多少時間。如果你的目標是做好，試著提前計劃一整段時間，這樣你就可以不分心地工作了。

比賽開始後會(hui) 發生什麽(me) ？

在啟動計時器後，會(hui) 被允許回答3-4個(ge) 問題(通常是3個(ge) )，選手必須在個(ge) 人時間窗口中解決(jue) 。每一個(ge) 都將提供一個(ge) 背景問題，必須編寫(xie) 一個(ge) 程序進行分析。在選手的時間窗口內(nei) 的任何時候，都可以通過網站提交您的程序進行測試。選手可以在的時間窗口內(nei) 自由切換或返回到任何問題，並繼續提交解決(jue) 方案，直到的時間截止或者選手覺得已經全部完美為(wei) 止。可以選擇在同一周末的任何時間使用新的計時器開始新部門的比賽。

06 如何選擇USACO計算機競賽的語言

USACO接受多種語言主要包括Java、C++和Python。Java和Python提交的時間限製是C++的兩(liang) 倍，因為(wei) 它們(men) 的運行時間更長。然而，USACO官方描述並不推薦使用Python，因為(wei) 它的運行速度往往比Java慢，而且在某些情況下，即使是問題的最佳解決(jue) 方案也可能無法在時間限製內(nei) 完成。

發布在USACO網站上的解決(jue) 方案供學生學習(xi) 如何使用C++來解決(jue) 包括大多數“training problems”在內(nei) 的老問題，但隨著時間的推移，Java已經變得越來越流行。

所以在為(wei) USACO編程時，有什麽(me) 特殊的Java注意事項是我應該知道的嗎？您可以導入與(yu) Java 8一起安裝的任何標準庫，例如java.util.*和java.io.*。您的Java文件必須使用“default package”；源代碼中不應該有“包”行。完成問題需要讀寫(xie) 文本文件。

關(guan) 於(yu) Division specific topics:

青銅級別除法問題通常可以使用數組(有時是二維數組，有時也可以使用類或ArrayList)來解決(jue) 。

白銀組競爭(zheng) 者應該熟悉java.util包中的標準數據結構，如List/ArrayList、Set/HashSet/TreeSet、Map/HashMap/Treemap、Deque/ArrayDeque和PriorityQueue，以及比較器/可比接口。

黃金組的競爭(zheng) 對手往往不得不對自己的數據結構進行編程。C++的運行速度確實比Java快，但USACO允許Java程序使用的時間是Java的兩(liang) 倍。使用Java應該不會(hui) 出現無法在合理時間內(nei) 完成的問題。建議使用一種適合學習(xi) 的語言。

對於(yu) 學習(xi) 美國AP課程的學生來說，這種語言通常是Java。其他比賽可能有不同的設置，可能需要使用其他語言。真正的知識在於(yu) 算法，而不是語言。學習(xi) C++是一個(ge) 很棒的推薦，如果您有時間和動力，鼓勵您這樣嚐試。

Java程序的內(nei) 存和時間限製是什麽(me) ？

對於(yu) Java，每個(ge) 輸入測試用例都被給予“大約”4秒的時間，盡管這在不同的問題或測試用例中可能有所不同。通常，對於(yu) 最壞的輸入場景，粗略估計您的程序需要10億(yi) 次或更多的“operations”會(hui) 花費太長時間，而1億(yi) 次或更少通常是可以的。介於(yu) 兩(liang) 者之間的任何地方取決(jue) 於(yu) 細節。

每個(ge) 輸入案例都有“大約256MB”的內(nei) 存可供運行。100萬(wan) 個(ge) 整數的數組僅(jin) 占用4MB內(nei) 存(4字節*100萬(wan) )。假設有一種合理的數據存儲(chu) 方法，時間限製幾乎總是內(nei) 存限製之前的限製因素。

PART THREE--競賽備賽指南--

07 USACO計算機競賽的報考指南

適合學生

任何對編程語言有中級知識的學生都可以參加比賽。可能學生會(hui) 覺得很難，但嚐試挑戰不會(hui) 有什麽(me) 壞處，可以按照自己的程度不斷挑戰提高！當參加比賽時，可能會(hui) 學到比你以前知道的更多的東(dong) 西，從(cong) 而在下一輪比賽中取得更好的成績。無論你的成績如何，你仍然可以在你的履曆或大學申請資料中體(ti) 現而超越競爭(zheng) 對手。

何時參加比賽

USACO 每年有 4 個(ge) 周末舉(ju) 辦主要比賽。在從(cong) 周五到周一的這些周末期間，學生可以選擇任何時間為(wei) 該賽周啟動他們(men) 的個(ge) 人計時器。每個(ge) 學生每個(ge) 周末的時間通常是 4 小時，但有時是 3 或 5 小時。

每年賽季時間會(hui) 有微調，但是大致差距不大.

如何參加比賽

事先在www.usaco.org網站上注冊(ce) 一個(ge) 免費賬戶。你不需要提前注冊(ce) 一個(ge) 具體(ti) 的比賽日期！一旦您擁有帳戶，您就可以參與(yu) 競爭(zheng) ，還可以通過您自己的門戶訪問所有培訓課程和資源。

在網站上創建帳戶後，請登錄您的帳戶。如果是比賽周末，你會(hui) 在首頁看到一個(ge) 開始按鈕！

比賽報名費用

USACO 是完全免費的，對任何人開放。隻需注冊(ce) 一個(ge) 帳戶並進行一些練習(xi) ，就可以開始了。

參賽形式

必須以個(ge) 人參賽者的身份參加比賽，並且在比賽期間不允許與(yu) 其他人合作。但是，您可以與(yu) 喜歡的任何人一起學習(xi) 和準備！比賽規則詳細說明了官方學術誠信準則。

競賽獎項

USACO是沒有“prizes”的，但學生通過的難度競賽會(hui) 獲得認可鑒定，這將使您的名字列在您晉級的周末的比賽結果中。這個(ge) 可以在任何大學申請的履曆上體(ti) 現出來成為(wei) 公認的成就。

08 USACO計算機競賽真題展示

USACO是一個(ge) “algorithmic”算法競賽，這意味著它需要想出創造性的、係統的方法來分析信息，而不僅(jin) 僅(jin) 是直接將程序的描述翻譯成代碼。

例如，“find the position of the largest number in a list”是一個(ge) 非常簡單的算法問題，但“write down the commands to draw a circle and then a square”就不是了。您可以查看過去的競賽問題以獲取一些示例。

【以下是一些USACO真題展示】

競賽|USACO計算機競賽全解 21-22年