什么是USACO競賽，USACO比賽機制/選擇語言

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

　　競賽策略，技巧指南

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

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

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

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

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

　　USACO

　　如何準備USACO考試

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

　　盡早開始準備是晉級成功的關(guān)鍵。雖然比賽的對象是高中生，但是越來越多的初中生開始學習編程，準備競賽，為大學申請做裝備。要了解更多USACO 對升學的幫助，可以查看我們的USACO常見問題。

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

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

　　堅持不懈的學習過程才是競賽的關(guān)鍵，最終都會有所收獲。

　　USACO考級程序速度

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

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

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

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

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

　　恒定時間

　　(log(n)) 對數(shù)時間

　　O(n) 線性時間

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

　　O(n*n) 二次方時間

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

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