USACO丨美國(guó)計(jì)算機(jī)奧林匹克競(jìng)賽攻略請(qǐng)查收

USACO（UnitedStates of America Computing Olympiad,美國(guó)計(jì)算機(jī)奧林匹克學(xué)術(shù)活動(dòng)）是美國(guó)最具認(rèn)可度的計(jì)算機(jī)學(xué)術(shù)活動(dòng)，面向全世界所有的高中信息學(xué)學(xué)術(shù)活動(dòng)選手。這個(gè)比賽開設(shè)目的是為了每年夏季舉辦的國(guó)際信息學(xué)學(xué)術(shù)活動(dòng)（IOI），選拔美國(guó)隊(duì)隊(duì)員（4名），相當(dāng)于國(guó)內(nèi)的NOIP比賽。

國(guó)內(nèi)的NOIP比賽主要以線下組織為主，基本上都是以學(xué)校為單位進(jìn)行組織的。而USACO則是以線上為主，學(xué)生可以直接在網(wǎng)上報(bào)名，并在線進(jìn)行解題。

含金量幾何

隨著STEM教育理念，及編程低齡化、普及化的發(fā)展，USACO的參賽人數(shù)和熱度越來越高。而編程的門檻相比數(shù)理化學(xué)習(xí)較高，USACO難度和含金量實(shí)際會(huì)略高于同類型的USAMO（美國(guó)數(shù)學(xué)奧賽），USNCO(美國(guó)化學(xué)奧賽)等學(xué)科奧賽。

對(duì)于未來美本留學(xué)申請(qǐng)理工科專業(yè)的高中生來說，USACO能夠獲得金或者白金級(jí)別的獎(jiǎng)項(xiàng)，絕對(duì)是提高競(jìng)爭(zhēng)力的大殺器。

以下是Quora(類似于知乎)上關(guān)于USACO等級(jí)對(duì)應(yīng)的數(shù)學(xué)奧林匹克學(xué)術(shù)活動(dòng)等級(jí)，很多偏理科的大學(xué)都會(huì)要求AIME（美國(guó)高中數(shù)學(xué)邀請(qǐng)賽）成績(jī)，如果你有對(duì)應(yīng)的USACO成績(jī)，大學(xué)也是認(rèn)可的。

從美國(guó)大學(xué)錄取規(guī)律來看，分量最重的比賽還是USACO,USAPHO，以及中國(guó)的官方奧林匹克學(xué)術(shù)活動(dòng)（如NOI）。

USACO參賽要求

這個(gè)比賽對(duì)參賽者沒有什么國(guó)籍要求，高中生都可以參加，只要在官網(wǎng)上注冊(cè)成功即可。最好一定要有編程語言的基礎(chǔ)。參加比賽是不需要任何報(bào)名費(fèi)的。

比賽可以接受的計(jì)算機(jī)語言有C++、Java、 Python、 C、 Pascal。

比賽規(guī)則

USACO每場(chǎng)比賽4-5個(gè)小時(shí)。可以在比賽規(guī)定時(shí)間開始后登陸USACO賬號(hào)，從在線打開試題后開始計(jì)時(shí)。一套試題中有三道題。選手需要在時(shí)間結(jié)束前通過網(wǎng)絡(luò)將寫好的程序提交，程序提交后官網(wǎng)會(huì)給出用testcase檢測(cè)程序的結(jié)果，并根據(jù)結(jié)果給出這一題的得分。可以使用C++，Java，Python，Pascal，和C中的任意一種編程。比賽對(duì)于程序的大小，運(yùn)行需要的內(nèi)存以及運(yùn)行的時(shí)間都有一些具體規(guī)定。

每次比賽，實(shí)力強(qiáng)的選手可以連續(xù)升級(jí)。在比賽窗口開放的三天時(shí)間內(nèi)，選手可以選擇任意時(shí)間開始比賽。開始比賽4小時(shí)內(nèi)，如果拿到了高分(接近滿分或滿分)，系統(tǒng)會(huì)提示直接晉級(jí)，可以在這三天內(nèi)繼續(xù)挑戰(zhàn)下一級(jí)，只要實(shí)力足夠，理論上一場(chǎng)考試可以升到滿級(jí)白金級(jí)。沒能拿到滿分的選手需要等到三天的賽程結(jié)束后，等待晉級(jí)分?jǐn)?shù)線，才能決定是否晉級(jí)，如果成功晉級(jí)，可以在一個(gè)月后的第二場(chǎng)繼續(xù)參賽晉級(jí)。

比賽時(shí)間

月賽：一般是每年12月開始進(jìn)行，會(huì)選擇四個(gè)周末舉辦主要的比賽，從周五到周一，在這個(gè)時(shí)間段內(nèi)學(xué)生可以選擇在任何時(shí)間比賽，通常來說每次學(xué)術(shù)活動(dòng)的時(shí)間為4個(gè)小時(shí)，但有時(shí)候是3個(gè)小時(shí)或者5個(gè)小時(shí)

公開賽（US Open)：每年4月舉行，題目比月賽要難。成績(jī)優(yōu)異者可獲得參加USACO訓(xùn)練營(yíng)的機(jī)會(huì)。（達(dá)到白金組可參加）

等級(jí)

青銅

參賽資格：一進(jìn)入U(xiǎn)SACO注冊(cè)賬號(hào)即為銅級(jí)。

考核知識(shí)：基礎(chǔ)數(shù)組、多重循環(huán)、復(fù)合判斷、枚舉算法。

難度等級(jí)：銅級(jí)考試只要基本編程常識(shí)，會(huì)至少一種編程語言。銅級(jí)的編程限制時(shí)間還是夠用的，大部分初次參賽的選手都能在第一次考試中晉級(jí)白銀級(jí)。

白銀

參賽資格：通過青銅級(jí)比賽的選手。

考核知識(shí)：基本數(shù)據(jù)結(jié)構(gòu)，貪心、遞歸、遞推等基本算法。

難度等級(jí)：從白銀級(jí)開始，選手需要尋找更好的算法才能使程序在規(guī)定時(shí)間內(nèi)跑完。

黃金

參賽資格：通過白銀級(jí)比賽的選手。

考核知識(shí)：堆、棧、樹、鏈表等高級(jí)數(shù)據(jù)結(jié)構(gòu)，動(dòng)態(tài)規(guī)劃等高級(jí)算法，算法時(shí)間和空間復(fù)雜度。

難度等級(jí)：需要有一定的算法基礎(chǔ)，理解一些抽象的方法（例：最短路徑，動(dòng)態(tài)規(guī)劃），并且對(duì)數(shù)據(jù)結(jié)構(gòu)有比較深的了解。

白金

參賽資格：通過黃金級(jí)比賽的選手。

考核知識(shí)：各類高級(jí)數(shù)據(jù)結(jié)構(gòu)，尤其是算法的時(shí)間和空間復(fù)雜度。

難度等級(jí)：需要有較高的編程能力，對(duì)算法有深入的了解。部分比賽問題最后的優(yōu)化方案，可能不只一個(gè)，得出的答案也不只一個(gè)。

如何準(zhǔn)備

官網(wǎng)上有一個(gè)訓(xùn)練題庫(kù)（https://train.usaco.org），可以登陸這個(gè)題庫(kù)并進(jìn)行注冊(cè)，在這上面進(jìn)行訓(xùn)練。同時(shí)，在官網(wǎng)上還能查看歷年真題，做一下這些題目，能對(duì)題目的類型有一個(gè)基本的了解

備考指南：

1沒有編程基礎(chǔ)的同學(xué)

建議從Python或者Java入手，上手較快。學(xué)習(xí)主要內(nèi)容為數(shù)據(jù)結(jié)構(gòu)，編程語法，配合一定強(qiáng)度的練習(xí)和老師講解，可以初步通過第一輪銅級(jí)的選拔。

2有編程基礎(chǔ)的同學(xué)

比如在讀AP計(jì)算機(jī)的高一高二同學(xué)，或者學(xué)習(xí)過Python的同學(xué)，可以從C/C++或者Python入手，學(xué)習(xí)算法知識(shí)，加強(qiáng)算法練習(xí)和真題訓(xùn)練。

3有相關(guān)參賽經(jīng)驗(yàn)的同學(xué)

參加過國(guó)內(nèi)NOIP的同學(xué)，目標(biāo)肯定是沖擊金級(jí)別及以上的獎(jiǎng)項(xiàng)，在有數(shù)據(jù)結(jié)構(gòu)和編程語法基礎(chǔ)的前提下，需要系統(tǒng)的學(xué)習(xí)一些常見算法，比如排序等等。同時(shí)大量練習(xí)官方的金、白金級(jí)別的真題。

選擇什么語言：

這是USACO官網(wǎng)的統(tǒng)計(jì)數(shù)據(jù)，可以了解到參加學(xué)術(shù)活動(dòng)人員所使用的語言排名為：C++> Java > Python > C > Pascal。

作為編譯型語言C++的運(yùn)行速度一定是完爆解釋型語言Python的，尤其是usacogateway里面有幾道題python基本不可能不TLE（TimeLimit Exceeded即時(shí)間超限）。但是正式比賽的時(shí)候python是2秒的最大時(shí)間，c++只有1秒，所以同樣的算法會(huì)是差不多的分?jǐn)?shù)。

另一方面Java是AP計(jì)算機(jī)專業(yè)課程中指定的編程語言，因此對(duì)于準(zhǔn)備留學(xué)，要讀AP課程的學(xué)生來說，Java是一個(gè)不錯(cuò)的選擇，不僅能夠參加USACO考試拿到背景提升證書，還能抵扣大學(xué)的學(xué)分。

至于C和Pascal作為舊時(shí)代的殘黨已經(jīng)可以忽略不計(jì)了。總的來說選擇自己熟悉的語言即可，而初學(xué)者或零基礎(chǔ)者建議使用JAVA，夯實(shí)基礎(chǔ)就是它最大的優(yōu)點(diǎn)。

翰林USACO課程體系流程圖