什么是USACO競(jìng)賽，USACO比賽機(jī)制/選擇語(yǔ)言

　　在USACO基本指南中，您將了解到更多關(guān)于什么是USACO，比賽機(jī)制，選擇語(yǔ)言，以及如何為比賽做準(zhǔn)備。此外，還有關(guān)于程序速度的細(xì)節(jié)和為什么這很重要，以及比賽策略、技巧和竅門(mén)。

　　競(jìng)賽策略，技巧指南

　　賽前準(zhǔn)備：準(zhǔn)備一些模板，用于復(fù)制/粘貼，以讀取輸入和寫(xiě)入輸出。準(zhǔn)備一些常用算法的模板作為參考。使用你自己的模板，避免抄襲別人的模板! 在點(diǎn)擊開(kāi)始按鈕之前，將 您的IDE或編程環(huán)境設(shè)置好。

　　競(jìng)賽調(diào)試：在比賽中，程序可能會(huì)崩潰，產(chǎn)生錯(cuò)誤的輸出，因此，學(xué)生熟悉調(diào)試界面是至關(guān)重要的。由于錯(cuò)誤往往是編譯錯(cuò)誤、崩潰、超時(shí)或錯(cuò)誤的答案，學(xué)生可以使用這個(gè)大綱來(lái)開(kāi)始調(diào)試。

　　競(jìng)賽編譯：如果學(xué)生找不到哪一行不能編譯，試著使用二進(jìn)制搜索方法刪除代碼部分。使用具有自動(dòng)導(dǎo)入庫(kù)的IDE，并熟悉自動(dòng)完成的鍵盤(pán)快捷鍵。檢查異常類(lèi)型(空指針、除以0、無(wú)限遞歸、內(nèi)存不足?)如果沒(méi)有異常，嘗試上傳避免可能的錯(cuò)誤的代碼，并使用二進(jìn)制搜索方法找出可能崩潰的代碼區(qū)域。

　　競(jìng)賽超時(shí)：注意數(shù)組實(shí)例化的問(wèn)題。盡量在程序開(kāi)始時(shí)就把所有東西實(shí)例化。試著計(jì)算運(yùn)行了多少操作。如果有必要，可以使用變量。嘗試用標(biāo)準(zhǔn)的預(yù)分配數(shù)組代替List或Map這樣的數(shù)據(jù)結(jié)構(gòu)。對(duì)于更高層次的問(wèn)題，檢查是否可以進(jìn)行動(dòng)態(tài)編程或記憶化。

　　競(jìng)賽復(fù)查：檢查你的代碼與正確答案之間的間距和格式是否一致。檢查整數(shù)溢出的情況。檢查是否有NaN或未定義的整數(shù)運(yùn)算。如果有時(shí)間，試著做你自己的自定義輸入，并將輸出與你的預(yù)期輸出進(jìn)行比較。你甚至可以比較作為中間計(jì)算的具體數(shù)值。

　　USACO

　　如何準(zhǔn)備USACO考試

　　USACO是一個(gè)高難度的競(jìng)賽。雖然它針對(duì)的是高中生，就算專(zhuān)業(yè)的軟件工程師也會(huì)感受到競(jìng)賽的難度。學(xué)生應(yīng)該安排每周練習(xí)幾個(gè)小時(shí)以取得競(jìng)賽好成績(jī)。即使是低級(jí)別的比賽，也經(jīng)常需要參加幾次才能通過(guò)一個(gè)級(jí)別。

　　盡早開(kāi)始準(zhǔn)備是晉級(jí)成功的關(guān)鍵。雖然比賽的對(duì)象是高中生，但是越來(lái)越多的初中生開(kāi)始學(xué)習(xí)編程，準(zhǔn)備競(jìng)賽，為大學(xué)申請(qǐng)做裝備。要了解更多USACO 對(duì)升學(xué)的幫助，可以查看我們的USACO常見(jiàn)問(wèn)題。

　　USACO競(jìng)賽指南中，我們推薦的第一步是通過(guò)大量的練習(xí)來(lái)準(zhǔn)備比賽。學(xué)生應(yīng)該熟悉 USACO 常見(jiàn)的題目，在USACO網(wǎng)站上提交歷屆真題的答案。學(xué)生可以從練習(xí)或修改比賽結(jié)束后發(fā)布的解決方案開(kāi)始。這一點(diǎn)很重要，因?yàn)榧词故墙?jīng)驗(yàn)豐富的程序員也可能被一些獨(dú)特的要求(要求的文件名、輸出格式等)所影響。把歷史真題作為熱身練習(xí)，可以確保學(xué)生在比賽中能夠?qū)Ｗ⒏咝У慕獯鹂碱}。

　　其次，學(xué)生應(yīng)該在比賽中熟悉常見(jiàn)的算法。在我們的USACO 課程中都有涉及。例如搜索算法，如二進(jìn)制搜索，"動(dòng)態(tài)編程 "算法，圖形遍歷算法，洪水填充，前綴和，以及更多。學(xué)生們應(yīng)該準(zhǔn)備好在更高層次上組合多種這類(lèi)算法。關(guān)鍵是學(xué)生可以快速寫(xiě)出這些算法，不需要花費(fèi)過(guò)多都時(shí)間進(jìn)行程序調(diào)試或測(cè)試。由于考試時(shí)間只有4個(gè)小時(shí)來(lái)完成3道考題，這意味著每道題，只花一個(gè)小時(shí)來(lái)解答。理解考題和調(diào)試程序解決方案很花時(shí)間。爭(zhēng)取盡快寫(xiě)出一個(gè)程序算法，同時(shí)給自己留調(diào)試時(shí)間。解題過(guò)程中，學(xué)生可以學(xué)習(xí)一個(gè)問(wèn)題的多種解法。

　　堅(jiān)持不懈的學(xué)習(xí)過(guò)程才是競(jìng)賽的關(guān)鍵，最終都會(huì)有所收獲。

　　USACO考級(jí)程序速度

　　USACO的解答方案如果需要很長(zhǎng)的運(yùn)行時(shí)間來(lái)解決。一個(gè)低效的解決方案通常會(huì)超時(shí)，耗時(shí)，會(huì)影響考級(jí)最后總成績(jī)。一個(gè)程序可能只有足夠的時(shí)間在給定的2-4秒內(nèi)進(jìn)行10-100萬(wàn)次操作，必須選擇有效的程序操作。

　　1. 對(duì)于寫(xiě)在循環(huán)內(nèi)的循環(huán)，必須注意完成一個(gè)雙循環(huán)所需的時(shí)間是兩個(gè)范圍大小的乘積。由于10.000*10.000是1億，學(xué)生需要注意不要在較大的數(shù)據(jù)集上運(yùn)行雙循環(huán)。

　　2. 三重循環(huán)同樣以立方時(shí)間運(yùn)行

　　3. 一些算法或排列組合以指數(shù)時(shí)間運(yùn)行，因此只對(duì)個(gè)位數(shù)以?xún)?nèi)的輸入有效。

　　學(xué)習(xí)過(guò)數(shù)據(jù)結(jié)構(gòu)的學(xué)生會(huì)認(rèn)識(shí)到程序速度的衡量標(biāo)準(zhǔn)是 "計(jì)算復(fù)雜性 "或 "大O符號(hào)"。這些高級(jí)學(xué)生可以從記住一些常見(jiàn)算法的復(fù)雜性中受益，這些算法通常表示為

　　恒定時(shí)間

　　(log(n)) 對(duì)數(shù)時(shí)間

　　O(n) 線(xiàn)性時(shí)間

　　O(n*log(n)) 線(xiàn)性乘以對(duì)數(shù)，接近于線(xiàn)性時(shí)間

　　O(n*n) 二次方時(shí)間

　　O(n*n*n) 立方時(shí)間

　　O(x^n)  指數(shù)時(shí)間