本文正體字版由OpenCC轉換

雖然很貴，我還是花了3800元來參加“NOI2009特別夏令營”。經過這一星期的培訓，我有不少感觸。7天做了5套題，其中三套是紹興一中的同學出的，一套是呂瀟、陳鍵飛和任春旭出的，還有一套是CEOI。期間紹興一中的神牛有三天的難題討論。不得不承認，這些難題大部分對我來說太難了，以至於無法接受。最大的收穫還是考試的經驗，包括心態的調整，對難題的應付手段，以及考試選題的策略。這些經驗是極端重要的，對於NOI來說，甚至比硬實力更加重要。我覺得一場考試這麼幾件事要做：看題，選題，分析，編碼，調試，測試，騙分。

1、看題

拿到試卷以後的第一件事就是看題。看題不是看小說，要仔細閱讀。當然，閱讀也不宜過慢，刻意製造緊張的氣氛會極大地影響發揮。NOI的題目沒有赤裸裸的，都是精心包裝過的，閱讀就是解開這個包裝的過程。首先從題目名看起，認真閱讀問題背景，要明白題目在表達什麼意思。一邊閱讀，一邊在腦中建立一個簡單初步的模型。讀完題後立刻看數據格式，然後閱讀樣例，如果是圖論題，在紙上把樣例中描述的圖畫出來，手算一下樣例，這樣有助於加深理解題意。這時候不要着急開始想題，把題再讀一遍，第二遍看題可以適當加快，但不要放過細節。

2、選題

除非你是神牛級人物，否則像NOI這樣的比賽你是不可能把題全部想出來的，那麼選題就是十分重要的。把所有題先全部看完，對每道題進行簡要的思考，每個題不超過30分鐘，千萬不要陷進去，有思路後即可停止。當你有了全局性的認識以後，這時再開始選題。

選題意味着要決定深入思考哪個題，做哪個題，不做哪個題，先做哪個題，後做哪個題。深入思考，當然是是要思考已經有大致思路的題，在考場上想了半個鐘頭還沒思路的題，再想下去也很難想出來，即便是想出來了，浪費大量時間也是得不償失的。我認爲要先做把握大的題，什麼是把握大的題？也就是思路完整，算法熟悉，易於調試的題。這樣的題是拿分的關鍵，也是和別人拉開檔次的法寶，一般來說一場考試中能有一道就是大幸了。更多的時候，可能會發現沒有把握很大的題，這時不要着急，靜下心來選擇一道有思路的題深入思考。

如果確定用隨機類算法解決提交答案題，可以先考慮開始寫，這樣在剩下的幾個小時中都可以用來運行隨機程序，以獲得更好的解。

3、分析

有了思路，要開始具體分析一個題的算法。分析前首先要確定一個目標，我是要把這道題AC掉呢，還是拿部分得分足矣？這要看題目的數據規模，把腦中的思路簡要抽象成算法，分析算法的時間複雜度，確定目標，着手優化算法。最後，確定算法的每個細節，思考各種極端的和邊界的條件，把完整的想法轉化爲完整的算法，在紙上寫出算法的流程，準備編碼。

有時候，並不一定有拿滿分的思路的題就要寫完美的算法，尤其是複雜的數據結構題！這些題經常是一個陷阱，令選手陷入其中不能自拔。浩浩蕩蕩寫完二三百行程序，欲調試出而不能，而樸素的算法花費極少的時間拿到可觀的分數，孰輕孰重還要根據自己情況來衡量。

4、編碼

在外行人看來，彷彿變成編程序就是信息學競賽的全部，其實這是很小一部分，但卻是很關鍵的一部分。編碼細心與否，直接決定了下一步也就是調試的難度。看着自己在紙上寫出的流程圖，小心地把代碼寫出來。這一步不求快，但求穩，一定不要犯低級錯誤。建議寫完每個模塊後立即檢查每條語句與所想的是否符合，寫完整個程序後不要急於編譯，先把程序通讀一遍，確認無誤後再開始編譯調試。

5、調試

首先用樣例（或自己構造的小數據）測試一邊程序，如果得出了期望的結果，可以繼續測試。否則一般會遇到這幾種情況，崩潰、超時、結果錯誤。崩潰問題一般是這幾種情況的後果：數組下標越界，訪問無效指針，棧溢出。如果算法可行，那麼超時很可能是由無窮遞歸或死循環造成的。可以使用輸出語句或調試器跟蹤到程序錯誤的位置，然後檢查有沒有語句邏輯錯誤。如果實在難以發現，可以使用輸出語句，或調試器單步進入進行跟蹤，發現異常的部分及時修改。找到結果錯誤原因，儘量不要一開始就是用單步調試，不妨把建模過程和程序每步的結果都輸出，這樣比單步更容易發現錯誤。

6、測試

調試和測試是交叉進行的，穩定測試無誤後，開始規模測試。首先要構造邊界、極端數據，因爲這些是較容易忽略的死角。接下來，可以考慮隨機數據對拍測試（非完美算法可以簡化此步）。首先寫一個樸素程序，要保證正確性，不求運行高效率，然後寫一個數據生成器。接下來生成數據，兩個程序分別運行，對比結果，反覆大量測試（對拍）。發現錯誤可以及時調試並修正，測試可以直到放心爲止。充分利用時間，還可以在思考下一道題的時候一邊進行着測試。

7、騙分

會的已經寫完的，不會的寫了非完美算法，你還有剩下的工作要做。充分利用NOI的規則，並不要求算法的完美性，只要能拿到分就是好方法——這一步被人稱爲騙分。

騙分，不是胡亂交一個程序，輸出0,IMPOSSIPLE甚至一個隨機數之類，而是有計劃，有預謀地搞。騙分的原則就是，儘量避免超時。爲什麼？超時就是0分，如果不超時地輸出一個結果，還有可能拿到分。一般來說，對於非完美算法的較大數據，較好的方法是貪心、卡時和隨機。

貪心法需要大膽的猜想，即使是有反例的錯誤猜想，稍作修改，即可用於應付大數據。畢竟出題人也未必能考慮的你想到的貪心算法，況且範例也是不容易構造的，畢竟隨機數據在NOI的測試數據中有相當的比重，貪心是很划算的。對於需要反覆迭代求最優值的算法（例如搜索），不妨採用卡時的方法。因爲可能有這種情況，我的程序要運行5秒，但實際上有可能在第1秒以內求出的最優解已經是全局最優解，剩下的4秒就是無用的。雖然讀取系統時間time和clock函數都是禁止直接使用的，我們大可不必真正卡“時”，只需限定一個迭代次數即可。隨機算法有點撞大運的感覺，其實不是這樣的，較好的隨機算法（例如模擬退火，遺傳算法）得到全局最優解的概率相當可觀。

8、意外

有時候在考場上會遇到意外，例如寫了半天，發現算法根本是錯誤的；調了好長時間都調不出正確結果，猶豫是否放棄；精神過於緊張，以至於體力不支；操作系統或環境出現意外錯誤等等。這些因素都會很大程度上影響發揮，但當我們真正要面對這些問題的時候，該怎麼辦？這是一個值得討論的話題，我很難給出一個合適解決方法，但這時候發揮最重要作用的是心態，良好的心態纔是制勝的最根本條件。

爲期一週的特別夏令營結束了，明天我將從杭州上車返回鄭州，中途可以去西湖玩一玩，保持健康良好的心態來迎接NOI。我的目標是在NOI上發揮出我真正的水平，不求金牌，因爲我清楚我的實力離金牌還有相當的差距，願所有看到這篇文章的同學們能夠有所幫助，在將要到來的NOI2009和年底的NOIP2009中取得優異的成績。

後話：等我正式退役以後，我會寫更多的內容，將我的一切經驗毫無保留地獻給所有在信息學競賽路上繼續奮鬥的同學們。

上次修改時間 2017-02-03