學好信競-淺談信息學競賽考場策略及程序測試
- 2019 年 10 月 7 日
- 筆記
主題
本文作者是江蘇省常州高級中學吳翼同學發佈的信息學競賽江蘇省論文。內容對於大家備考十分有幫助，特分享給同學們，希望在中秋假期給大家的學習增加一點動力！
考場策略和程序測試是信息學競賽中非常重要的環節，很多優秀的選手在很多比賽中總是會在這兩個環節上犯下這樣和那樣的錯誤，導致得到的分數和實力不成正比，最後留下了無盡的遺憾。本文將探討一些這兩個環節上值得注意的地方，提出一些可行的方法，分享一些經驗，以此希望幫助選手們在比賽中發揮水平，減少失誤，告別遺憾。
前言
信息學競賽本身是一個美好的東西，她包含着奮鬥、努力、追求、成長、汗水和收穫。一個選手從與其接觸，到了解，再到熱愛，無數的時間與之為伴；同樣，信息學也給予了我們太多：給予了友情，老師的關懷，太多的希冀、責任和無數難以忘懷經歷。
可是，太多的時候，信息學競賽總是透着那麼多的憂傷，似乎她帶來的美輪美奐的精彩總被那些無可奈何的淚水和發自內心的懊悔所掩蓋。
遺憾——如此悲情的字眼的不停出現，似乎把本該光鮮的信息學競賽抹上了灰色。
遺憾，那麼傷痛，尋根溯源，筆者希望以此文，讓大家發揮水平，讓這個詞語永遠的離大家而去。
一、簡介
1、什麼是考場策略?
一場信息學競賽，比賽時間從 3 個小時到5 個小時不等，題目從 3 題到 4 題不等。在這樣的一個長時間的過程里，如何分配時間，如何對待手上的題目，用什麼方式和順序對待手上的題目等等一系列的決策問題，我們稱之為考場策略。
2、什麼是程序測試?
程序測試就是在寫完程序後，利用各種方式檢驗程序正確性的過程。
3、二者有什麼關係?
概要的說，考場策略包含了程序測試這一個環節，因而本文中，對於考場策略我們討論的是一個總攬全局的安排，而程序測試討論的則是具體的實施方法。
可以說，考場策略的制定在程序測試之前，而程序測試又能影響到考場策略的實施。
二、考場策略
一個完整的測試包括審題，思考，做題，檢驗這幾個環節，我們將分開討論這幾個步驟。
1、審題
【建議 1】一場測試應該花至少 30 分鐘來審題，並做相關筆錄。
1.1重要性
很多同學覺得這花去的時間太多了，大大佔用了之後的解題時間。但是無數的事實告訴了我們審題的重要性，無數的遺憾正是由審題開始的。
【實例 1】 NOI2008 Day1 party 具體題目略。
事實:
此題是NOI2008 day1的第一道題，也是最容易拿分的題目，此題有50%的小數據，因此使用暴力枚舉算法能夠至少拿到 50 分。而悲劇也正從這一刻開始了。
注意題目中這樣一句話：「輸出文件party.out包含兩個數，第一個數為最大可能的面具類數，第二個數為最小可能的面具類數。」也就是說，假設輸出的兩個數為A和B，那麼應該滿足A>=B。
題目描述清晰。可是，現場江蘇省隊11人中，僅四人看對這一條件，其他7人均將小的那一個先輸出，再將大的那一個輸出。因此7人最高分僅30分。其中一人損失近 70分。
原因分析:
客觀原因：
1、樣例中輸出的兩個數是一樣的，並沒有體現需要題目描述;
2、以往所有的題目都是先輸出小的再輸出大的，而這一次比較特殊。
主觀原因:
據事後交流，所有人都沒有花足夠的時間在審題這一環節上，而是花了更多的時間在算法思考和程序設計上。對題目的理解過分依靠直覺和以往經驗。
【實例2】APIO2009 convention 具體題目略。
事實:
注意題目中有這樣對方案的描述：「首先，將租借給客戶數量最多的策略最為候選，將所有的公司按照他們發出請求的順序編號。對於候選策略，將策略中的每家公司的編號按升序排列。最後選出其中字典序最小的候選策略作為最終的策略。」
這段描述一共有三句話，本屆江蘇省隊11人中有6人(包括筆者)都看清楚了第一句話和最後一句話，但都沒有注意到第二句話，因而此題均為0分。
而此題有50%的小數據，即用替代算法也可得到50%的分數。此外，事實證明利用錯誤的貪心算法也可以得到50分左右的分數。以筆者為例，筆者如果此題加上50分則將得到國際金牌，其遺憾不言而喻。
原因分析:
客觀原因:
1、這道題目描述比較冗長，這一句條件並不是很顯眼，並且去掉這個條件仍然是一道複雜度相同的問題;
2、樣例和題目舉的例子中均未體現這一個條件。
經過交流，所有看錯此題選手，均是由於題目描述的冗長，為了節省時間，未能仔細斟酌文字描述，而是直接通過題目的例子來理解題目，因而主觀的忽略了這一個條件。
分析一下上述兩個例子，可以發現一些共性。
大家的目的都是為了快速的理解題目，都是過多的相信了經驗和習慣，都是只關注題目所給樣例。可見，發生這種悲劇的原因都屬無視了審題這一環節的重要性!
到這裡顯然筆者已經不用再重申審題環節的重要性了。
不要因為某一次成功的因為經驗或者小聰明節省了幾分鐘的寫程序的時間而沾沾自喜，這樣的做法如果成為了習慣，那麼遺憾將是必然的。
1.2標記法
為了解決這一問題，筆者總結了一些方法，稱其為標記法，基本的方式都是用筆在紙制題目上進行標記。
關鍵字：對於題目中的一些關鍵字，將其圈出
所謂關鍵字就是比較級，最高級等形容詞，和一些關鍵的名字。
序號：對於一些定義冗長的描述，每一步的限制都標上序號，從而明確對題目的理解
建議是做到每一個標點後都要做一定的標記，這樣避免漏掉一些描述。當然也可以不用每個標點後都寫數字，如果兩個短句都在說同一個事情，那麼可以用一個點，或者一個三角來表示後一個短句的步驟和上一個短句相同。
回顧：不斷回顧重點細節
對於一個一下子難以看懂的描述，建議先做一個標記，比如問號，看完後再對這些打問號的地方重新審視，可以寫一些對這些地方的理解。
形象和抽象：將形象的問題抽象，對抽象的問題形象
對於一個形象的問題，我們往往需要對其進行抽象，進行數學建模；而對於一個過於抽象的問題(比如CTSC2009 day1 sequence)，我們則需要進行形象的思維。
建議將這些經過分析的東西寫在題目描述的旁邊或者後面。
比如對於上面提到的實例2中的那句被大家忽略的描述，就可以如此標記：(1)首先，將租借給客戶(a)數量最多的策略最為候選，將所有的公司按照他們(b)發出請求的順序編號。(2)對於候選策略，將策略中的每家公司的(c)編號按(d)升序排列。(3)最後選出其中字典序最小的候選策略作為最終的策略。{這裡要排兩次序，問題的關鍵是如何處理第二次排序的最優性問題!}
不難發現，如果嚴格按照上述方法進行標記，是不會漏掉這一個條件的，或許這會浪費一些時間，但是挽回的損失是巨大的。
1.3把握尺度
那是不是把試卷寫的越滿就越好呢?筆者觀點是否定的。
要標記，但是也不是要讓所有記號將白色的考卷染成黑色；同樣的，考卷也不是草稿紙，筆者認為，過分的標記只會讓紙面變得混亂不堪，反而影響閱讀，同樣也過於形式。
標記法的目的是為了加深對題目的印象，做到一次審題效率最大化，是審題的輔助，並不是一個形式化的東西。
使得自己恰好完全理解，使得自己不會遺漏條件，不會主觀臆斷。這是使用標記法的原因，也是自己把握的尺度。適當即可，一切是為了向遺憾說再見。
2、思考
【建議2】審題之後，對每一道題目都應該進行較為深入的思考。建議進行20~30分鐘左右的思考，同時不可淺嘗輒止，讀過便罷。
2.1重要性
這裡的「思考」並不是指如何分析一道題目或建立數學模型之類，這不是本文討論範圍。
而除此之外，「思考」還能有什麼門道呢?答案是肯定的。
【實例3】CTSC2009 day2
CTSC2009day2 有傳統題world和garden，以及提交答案題puzzle。
puzzle是經典的N2數碼問題。world和garden筆者第一眼都沒有想到很直接的做法，而puzzle則應該是手動做一些模擬之後利用A*搜索解答。
於是筆者花了幾乎所有的時間做了提交答案題，而幾乎沒有怎麼做另外兩道題，最後此題拿到45分——而這確實是一個比較不錯的分數。
但是事實上除puzzle之外的兩道題，現場都有很多的滿分和高分，而puzzle的現場最高分不過是一個70分，絕大多數的人都是20~30左右。
筆者除puzzle外，僅得10分。
筆者用自己慘痛的經歷說明了思考的重要性。
很多時候很多簡單的題目往往套着複雜的外衣，而複雜的題目則往往有着簡單的表象，還有的時候，有一些題需要一些分析才能得到問題的本質，如果貿然跳過，則永遠會覺得此題讓人一頭霧水，進而影響到了考場上策略的安排。
可以說對每道題目都進行一定程度的思考，是考場策略正確實施的重要環節，也是重要保證。
摸清楚題目的脈路，是一切的基礎。
對於實例3中的情況，筆者犯的最大的錯誤就是根據以往的經驗，主觀的認為CTSC的傳統題都是基本不可做的，加之world一題有着非常抽象冗長的描述，再由於N2數碼問題過於經典，所以筆者武斷的認為這次傳統題都不可做，最後犯了嚴重的策略錯誤。
顯然，如果能夠每道題都仔細思考一番，就能發現world一題搜索的本質，也就不會發生如此的遺憾。
2.2冷靜的判斷
上文說道，思考需要仔細。而何為仔細?是否想到算法就可以了呢?也不是，想到了一個算法並不能直接予以肯定，而是要先否定他，想想有什麼漏洞，或者想想是否有更好的方法，莽撞的立刻動手寫題往往會浪費更多的時間。
【實例4】NOI2007 day2
NOI2007day2有一道令人記憶深刻的數據結構題necklace，此題標準做法是線段樹。而更容易想到的是，對於這種連續區間問題有着超強適應能力的splay。
考場上XXX在思考的過程中很快想到了利用splay解決這個問題，並迅速開始了編碼。最終利用3個小時，終於寫出了一個350行的正確代碼。
但是由於時間的過多使用，導致另外兩道題的時間不夠用，而這道數據結構題，由於專註於splay，並沒有再深入的思考而沒有意識到可以使用更加簡單和快速的線段樹，導致最終此題也因超時的緣故僅僅比樸素算法多了10分。
day2的成績最終導致XXX和金牌差之毫厘。
試想，如果能在考場上對另外兩題多思考一下，進行正確的評估和定位，並對已有的算法多進行審視，懷疑和分析，結果也許就會好的多了。
冷靜和深入是思考的要求。
3、做題
這裡的做題也並不是說如何寫程序，如何實現模型，這些不是本文討論內容。這裡的做題主要討論的是用什麼順序做題，用什麼的心理期望來做題，如何分配時間來做題。
3.1先易後難
現在的題目普遍有比較多的部分分可以拿，而很多的時候即使想出完美算法，實現這些完美算法未必在考試時間內能夠完成，那是應該節約時間拿到一些部分分，還是花時間思考和實現完美算法呢?對於難度相當的兩道題，是應該先做哪一道呢?這是一個值得琢磨的問題。
【實例5】CTSC2009 day1
CTSC2009day1一共三道題目，分別是傳統題trique，sequence，和提交答案題locate。trique是類似漢諾塔類的最優值問題，sequence是複雜的動態規劃(貪心)。trique有20%的分數非常簡單，sequence有30%的小數據，locate有一個數據是求帶權中位數。
XX在考試中選擇了先做trique，並用很短的時間寫了一個暴力程序對自己的程序進行檢測，但是發現小問題不斷，於是便進行不斷的改進，最終思考3個多小時也未能得出正確結論。慌亂之中，隨手寫了剩下兩題的小數據。最終只有trique得到50分，其餘兩道均0分。
相對於XX，另一人在考試中一開始便寫了trique的20%的送分數據，以及sequence的 30%的小數據，並花了較多的時間利用調整做提交答案題locate。最終得分是30+60+30，沒有一道題的得分進入前十，但是總排名卻在前十之列。
CTSC2009是一次非常經典比賽，可以說這次比賽對選手策略的運用提出了很高的要求。從上面不難看出，對於一次考試的題目，絕對不能一開始盯着一道題花大量的時間。對於花很多時間先做難題，如果做不出，則必然對心情是一種極大的打擊，非常容易影響考試狀態，而即使做出了(實例4中NOI2007day2XXX的表現)，也會因為時間上的緊張影響到其他題目的解答。
【建議3】合理安排順序，遵循4個字：先易後難。這句話說的輕巧，如果分辨題目是難還是易呢?所以說先一步進行一定深度的思考是合理制定考場策略的前提。在進行一定思考之後，應該對不同的題目不同規模和性質的數據進行解題時間的評估。
【建議4】經過合理的預估，對於明確估計能夠在半個小時之內編寫完畢並且調試成功的題目(或者題目對應的部分數據)，應該立刻將其完成。
對於自己並不自信能在半個小時之內寫出對付一道題目的部分數據的正確程序，那麼樣的部分數據就不應該定義為簡單了。
寫完了簡單的，再寫有一些初步的算法需要繼續思考，或者需要大量編程量的題目。
此時，有人便會提出疑議，會不會因寫簡單程序而佔用了寫出得分更多算法的程序能夠用時間?
其實這是不會的，原因有二：
第一點，是這裡的簡單是在充分的自信下定義的。在考試開始的時候，如果能夠正確而快速的寫出一個能夠得分的程序，不但是對自信的提高，也是讓自己更好的進入考試狀態;
第二點，如果一道題目，最簡單直接的拿基礎分的程序都需要比較長的時間，那麼此題必然是一個比較難的題。通過上面的討論我們知道，這種比較難的題不宜在一開始做，而應放在後面做。如果開始時間緊張，寫暴力程序也是避免出現意外，避免出現最後得較多分的程序未能成功寫出而拿不到分的情況。
3.2杜絕模稜兩可
很多人又要說，如果對於一種算法，並不能通過題目得知具體的得分情況，該如何處理?
這種情況顯然是普遍的，很多人由於嫌惡暴力算法得分不高，不願意觸及，而更願意相信一些通過靈感的來的算法(比如一些詭異貪心)。實際情況是怎麼樣的呢?
【實例6】NOI2006
「這次 NOI 我只有兩題接近滿分。一道是平衡樹的題目(90分)，一道是提交答案題(92分)。其他的題目我接近0分。有些題目會告訴你百分之多少的測試點的規模是多少，小的規模的程序也許會很容易編，但是只能拿一點分，比如40 分，抓住這點分!只要我能夠抓住這 40 分，我就可以進國家集訓隊了，我就可以拿NOI 金牌了!可是，當時的我，想了一個可以「對付」所有數據的貪心算法(所謂「對付」，就是說可以不超空間和時間地出解)，這樣得分的幾率是很小的，小到遠遠不到 40%，我就拿了0 分!這次NOI，我能拿這樣的 40 分的機會，我錯過了 2 個!」 ——摘自陳明騁NOI2006總結
NOI2006江蘇沒有一個人獲得金牌，可以說江蘇隊取得的成績與隊員的能力完全不成正比，留下的也是無盡的遺憾。此處直接引用原句，從中不難發現深深的遺憾。即使有一個沒有明確得分估計的算法，筆者仍然有如下建議。
【建議5】一定要寫所有確定的，能夠得到一定分數的基本算法。
一個所謂比較「詭異」的算法，如果能取得比較高的分數自然是好事，而如果不能，寫一個能夠得分的程序，則絕對是一個保險的做法。
4、檢驗
這是一個往往被忽視的環節，下面說兩個真實而悲壯的例子。
【實例7】CTSC2009day2
仍然是CTSC2009 day2，只是這裡要說的主角不是筆者。考試內容可以參看實例3。
首先說說XXX，由於吸取了WC2009自己所犯的重大策略失誤，XXX在的做題思考的發揮上非常完美。在day1的比賽中，穩定發揮，並將總成績提高到前十；而在day2中，XXX很快看出world是一道搜索題，並在一個小時內解決world。此後同樣在不長的時間裏得出了garden 的正確算法，並完成了一個400行的代碼，剩下的時間還有一個小時左右。此後XXX將所有的時間放在了最麻煩的提交答案題puzzle上。
與XXX相似，在day1的提交答案題locate上拿到94分高分，並因此總成績一躍上升為第二的b，也很快想出了garden的做法，並將最後的所有時間花在了puzzle上。只是很可惜，最後的結果很悲劇。
a的得分是100+14+0，b的得分是0+22+0，a的garden寫錯了一個小的地方，b則是將文件名打錯。最終a位列第8，b位列第10，都遺憾的沒有能夠進入面試環節——如果那兩個錯誤不發生，他們都將進入面試。
可以看到，在實例7中，a和b雖然在審題、思考和做題環節都非常出色，但是都是由於忽視了檢驗這一環節，導致未能發現程序中微小的錯誤，導致最後巨大的遺憾。
【建議6】檢查是必須，這是一個必須的步驟，不能主觀的迴避。
即使實力強如a和b，也會犯如此低級的錯誤，在重大的比賽中要告別遺憾，必須重視檢查這一環節。
每道題目都要檢查，以筆者的角度推薦寫完立刻檢查，因為此時的印象最深刻，效果最好，同時檢查完畢後就排出了這道題目對後面比賽的影響，更容易讓人在後面的時間裏面集中精力。
同時在最後的半個小時左右的時間裏，筆者建議不要再寫程序，如例子中a和b，搶這一點時間不過為了爭得20分左右的分數，可謂丟了芝麻剪了西瓜。
筆者認為，在最後的時刻搶一些分數會導致非常的緊張，除非之前的檢查工作非常細緻和到位，推薦最後一定要把所有的題目仔細的靜態閱讀一遍，順一遍思路。
試想如果a和b能多檢查，悲劇就不會發生了。
5、說明
本文的題目是《談比賽發揮》，誠然，上述的內容並沒有說明如何得高分，如何超水平發揮，如何戰勝別人，但是，上文卻講述了一個最基礎的東西，只有先保證不輸，才能有底氣的考慮如何戰勝別人。
三、如何測試程序
1、概述
測試程序是非常重要但卻經常被忽視的一個環節，很多時候想到了正確算法，但是往往因為小的錯誤而功虧一簣，扼腕嘆息，為時晚矣。
上文中我們已經說到了測試的重要性，而如何高效的測試程序，有一些什麼注意的要點?下面我們就要談談具體如何測試程序。筆者認為，程序的測試工作分為兩個部分：靜態查錯和製作測試數據。
2、靜態查錯
這裡先引用吳景岳的一段話: 「在編程之後不要急着運行調試，而是把自己的程序仔細看看，有什麼錯誤，這也被稱作「靜態查錯」。因為很多錯誤在運行調試中是很難被發現的，比如常量定義、數組大小、變量名打錯……。靜態查錯還能夠發現算法實現過程當中的一些小問題。」
靜態查錯是測試程序的第一步，也是關鍵的一步。尤其對一些寫了很長時間，代碼量又非常大的題目，經過長時間的編碼，人非常容易由於注意力的不集中而犯下很多低級的錯誤。靜下心來重新想一遍算法，仔細分析一遍程序，是能夠發現很多的問題的，認真的靜態查錯也能讓之後的調試工作減少非常多的工作量。
【建議7】靜態查錯，最重要的是心靜。
心靜，即不可以因為剛剛寫出一道難且複雜的題目而過份沉浸在成功的喜悅之中。靜態查錯，應該是把程序當成閱讀來對待，認真的分析每一種情況，不能憑主觀印象而粗枝大葉的掃幾次，這樣的查錯是沒有意義的。
很多OI選手非常依賴調試器，這樣不但非常不科學，而且往往很低級的錯誤需要極長的繁複的過程才能找出。這樣在考場非常容易造成急躁的情緒，最後使效率越來越低。
總之，靜態查錯是一種必備的，不可缺失的能力。
3、製作測試數據
從大體上說，測試數據分為三種，小數據、大數據和極限數據。
除了寫腳本，C語言的選手可以使用system()以及sprintf()函數在程序內直接寫測試腳本，這樣由於腳本和程序同步，更加方便。
#include<iostream>
using namespace std;
const char P[]="sample";
const char T[]="sample2";
chars[100];
int check() {
…//內容省略，根據情況編寫即可
}
int main()
{
int test=0;
while(1) {
cout<<">TEST#"<<++test<<endl;
cout<<">Making…"<<endl;
system("./maker");
sprintf(s,"./%s",T);
system(s);
cout<<">Running…"<<endl;
sprintf(s,"./%s",P);
system(s);
cout<<">Judging…"<<endl;
if(check())cout<<" Passed!"<<endl; else {
cout<<"Wrong!"<<endl; while(1);
}
}
}
這段程序的基本框架也是不變的，也可以預先準備。
另外，寫這種很自由的程序其實也是一種調劑，比如筆者在這種腳本程序時，總喜歡在自己的程序測試幾百組數據正確後在屏幕上輸出一個笑臉o(^-^)o 來對自己予以肯定。
測試策略
這裡主要是想說明下面的這個問題。
從上面的描述中可以看出，隨機數據並利用程序或者腳本對程序進行大規模測試的方法非常的便捷高效，那麼是不是就可以忽略手工測試數據的生成呢?
答案肯定是否定的!
【建議 8】製作測試數據時，手動構造和程序構造在允許的情況下都是不可忽略的。
【實例 8】BOI2008 Mafia
BOI2008Mafia這道題是求一組網絡最小割的方案，筆者由於疏忽誤將所有與源相連的滿載邊均判斷為割集，並輸出為了方案。筆者進行了隨機數據的測試，並通過了官方數據的所有5 個回饋點(feedback)，筆者此時自信滿滿的提交，結果測試結果是 0 分(由於 BOI 數據採用捆綁測試，而所有回饋數據都是非獨立的)。
【實例9】江蘇差額選拔2008day3cactus
此題筆者寫程序時，由於程序比較複雜，在某處循環少寫了一層數組下標，但是靜態查錯筆者並沒有能夠發現問題。由於錯誤很小，筆者才考場上測試了 800 組比較小規模的隨機數據都沒有發現錯誤。而提交之後，測試結果是40 分，筆者賽後再次測試了 200組規模大一點的數據，就發生了錯誤。
從上述兩個關於筆者的真實事例中，不難發現幾個問題。
1、首先，隨機數據非常不穩定，對於很多細小的錯誤，很多時候，當時運不濟的時候並不能隨機出很好的數據;
2、其次，可以發現數據規模越大，隨機的效果越好，因此對於小數據，筆者強烈建議一定要仔細思考，考慮各種情況，出幾個數據，很多的時候，當隨機很難構造好的數據的時候(尤其是圖論問題，由於圖的種類過多，隨機的生成的圖往往過於「樸素」)，手動構造數據將變得更為重要;
3、最後筆者再次提醒，千萬不要相信題目所給出的樣例和回饋，有的時候，片面的樣例和回饋甚至會產生不良的誤導。
4、此外，利用製作的測試數據測試完畢後，筆者建議再回顧一遍程序，檢查是否將所有注釋，或者改變的數組範圍和常數等等都標記正常，防止出現文件忘記打開之類的遺憾的錯誤。
四、實踐
有了如上理論，我們來找一次比賽實踐一下。我們假設參賽的選手以基本的動態規劃，搜索，和例如強連通分支，最短路等基礎的圖論技巧以及比較熟練的程序實踐基礎。
應用 NOI2008
Day1:
首先審題，第一道是 party，利用標記的方法發現題目要求先輸出大的再輸出小的，並加以符號標明。然後是design，審題的時候發現題目有加粗的字體，馬上關注，經過思考發現是一棵樹。首先發現可以搜索，能夠拿到 20 分，但是數據提示標準算法是O(NlogN)級別的。最後一題 employee，題目很清楚，發現有30%的數據規模很小。
開始思考，首先是 party。可以想到，題目與最大公約數和最小公倍數有關，但是沒有明確的想法。思考用搜索來解決這個題目，發現似乎可以通過搜索的方法來確定面具種類。發現數據中說明 50%的數據可以用O(NM)的算法解決，於是想到可以暴力枚舉答案。深入思考可以發現我們並不需要知道面具具體的種類，而只要知道相對關係即可，於是可以在O(M)的時間內進行答案可行性判斷，總的複雜度恰好為O(NM)。
接着轉到 design，根據樹的性質發現是樹形動態規劃，但是似乎有難度，而且由於需要枚舉孩子的選擇情況，只想到 O(N4)複雜度的算法，可以拿 30~40 分左右。繼續思考如何優化，但是發現此題思考時間已經半個小時了，立刻停止，迅速轉到下一題。
經過深入思考，感覺 employee 可能和網絡流有關係，但是自己不會，迅速放棄。此時時間過去一個半小時。
開始決策，覺得 employee 寫暴力搜索會比較好寫，於是花半個小時寫employee 的搜索，經過 10 分鐘的測試，發現通過。然後開始寫 party 的50%的算法，寫程序花了近 40 分鐘，手動測試 20 分鐘，發現正確。
時間還剩兩個小時不到，仔細回顧一下 design 的決策方程，覺得時間不允許自己想出更好的算法了，思考20分鐘，考慮周全後開始寫程序，寫了一個小時，並測試20 分鐘後通過。時間還剩半個小時不到，檢查各道題目，並最後將employee 加了一個剪枝條件。
測試得分 50+40+30=120 分，比較理想。
Day2:
第一題 trans 發現描述很麻煩，花了比較多的時間看，進行標記，着重看這句話：「從任何物流基站都可將物資運往控制基站」，經過分析，發現控制基站必然在環上。但是並沒有發現什麼好性質，但看到測試數據的條件列的很清晰，應該可以拿到幾個特殊數據的分數。第二題 candy，是數據結構，暴力似乎可以拿30 分左右的分數。最後一題提交答案題 match，題目描述很清晰，但是求期望自己不大會，應該可以利用提供的評分程序match_check 用類似測試自己程序的寫 C++腳本程序的方式來幫助自己的隨機化程序計算。
開始思考，先看情況最多的 trans。發現目標函數可以用高斯消元法列方程求解，但是似乎複雜度過高，而自己思考一段時間後並沒有得到好的方法。通過觀察數據發現，test1 規模小可以直接枚舉，test3直接解方程即可，由於之前審題發現控制基站在環上，因此test4 和 test5 也可以通過枚舉和解方程來解決。總的來說，這道題代碼量比較大，但是能拿 40 分的分數。然後是 candy，想了15 分鐘沒有什麼好的想法，決定採用得 30 分的替代算法。最後是 match，想到是提交答案的題目，於是打開數據觀察，發現test1 和 test2 可以暴力搜索，test6,8,9 似乎有規律，於是開始分析，但是發現快半個小時了，並沒有得到什麼好的結論。時間過去一個半小時，開始制定策略。
由於提交答案題的前兩個數據的搜索程序最簡單，很快寫好並開始了搜索。然後考慮到隨機化是提交答案題的通用方法而且也比較好寫，於是很快寫了一個非常暴力的隨機比賽排列順序的隨機化程序。此時時間過去 2個多小時。
開始寫第一題的高斯消元法，由於高斯消元法本身並不難寫，程序的嵌套也只是複製而已。寫程序用去 40 分鐘左右，手動 10 分鐘測試高斯消元函數，測試完畢後寫隨機程序繼續測試高斯消元函數是否正確——檢測的方法很簡單，把解得的解代回原方程計算即可。
時間還剩不到 2 個小時。開始寫candy 的暴力程序，發現比較複雜，但是還是能夠調試成功，由於程序比較直接，靜態查錯並手動測試程序正確性。
時間還剩 1 個小時，最後回顧一下candy 和 trans 兩道題目，然後開始查看提交答案題隨機化程序生成的解答，最後逐一利用 match_check 檢驗完畢。考試結束前再次檢查文件名數組大小等關鍵環節，最後提交。測試結果 40+30+60=130。
最終，加上筆試 100 分，總分350 分，獲得金牌第 18 名，進入國家集訓隊。
不難看出，其實水平並不需要超強，只要不犯錯誤，不留遺憾，一個有一定算法基礎和代碼能力的選手也能夠進入國家集訓隊——雖然排名不是很高。
總結
說了這麼多，還是得說：文中所說的策略也好，方法也好，只能是告別遺憾，而不能迎接驚喜。
所謂遺憾，就是說對於一定的水平，沒有能夠發揮出來，沒有得到這樣水平應該得到的肯定，這樣的情況才叫遺憾，而如果沒有能夠想到某種算法，或者別人超常發揮了，而我沒有，別人想到了怪異的方法拿了高分，而我沒有，其實這不能算遺憾，因為我發揮出了水平，而別人是超水平發揮。
比賽最重要的還是實力，要有一顆平常心，要正確的認識自己，超水平發揮要靠運氣，機遇等等許多因素，可遇而不可求——我想休斯頓火箭的球迷肯定贊同我這樣說法：你必須要求T-mac 每場比賽拿下兩雙，但是你絕對不能奢求T-mac 在火箭每次落後的時候都上演 35 秒 13 分的奇蹟——事實也是這樣：T-mac 只得2 分之後遭到了無數的批評，而當年姚明倒下，T-mac一個人與爵士眾將纏鬥，最終火箭失敗後，T-mac並沒有得到太多的責備—— 當然，不會有別人來怪罪我們，只有我們自己的內心會留下深深的遺憾。
考場上要做到正常發揮，不留遺憾，一定要做到專註。
吳沛凡在 NOI2008 就因為過份的考慮升學問題而留下無盡的遺憾，他後來說道：「什麼心態會出現浮動?為什麼細節會出錯?這都是由於對自己的懷疑引起的。因為懷疑自己的實力，所以心不定；因為懷疑自己的能力，所以才對細節不自信。考場上我的想法其實是完全不必要的，而且由於出現在考場上更加影響了我的發揮。」
陳明騁在 NOI2006 後曾留下豪情的感嘆：「人家愛考多少考多少，我在進行精彩的個人表演。」是啊，我們都在進行着精彩的個人表演，走到這裡，無論成敗，不都是要為自己而鼓掌的么?
很多的時候我們因為未來的未知而焦躁，而緊張，而煩憂，不能迴避，只能直面。也許，那會產生很多的害怕和膽怯。筆者的一個老師曾對筆者說過：「未來永遠是未知的，如果因為未來的未知而恐懼，那麼就不斷的問自己我到底恐懼什麼，問到自己啞口無言的時候，自己就會得到釋然。」
再次引用陳明騁的話：「競爭中的人，總會遇到「不能失敗」的仗。這時候，責任心會催發你的鬥志。我覺得，這比在心理上迴避比賽後果的嚴重性要好。我經常在NOIP 之後的選拔中發揮大失水準，就是因為我一直想靠主觀迴避比賽後果的嚴重性來換取心態的輕鬆。其實，這是不可取的。難道直面世界很困難嗎?」是的，難道真的那麼困難么? 心態這個東西是如此的複雜，以至於筆者不能再多說些什麼了。
筆者執筆此文，就想總結筆者自己和前輩的錯誤與經驗來幫助更多的人，讓更多的人引以為戒，在腦子空白的時候，不至於不知所措；讓大家多琢磨琢磨這些經驗的東西，感悟那些和這些話；讓大家在將來的比賽中發揮出水平。希望此文，不再讓以後的人們無所適從，不再讓以後的人們抱憾，能讓以後的人們每次比賽都能發揮水平，能夠真正的告別遺憾。
版權聲明：本文版權歸原作者吳翼所有，由於無法聯繫到作者，如作者有意願聯繫 我們願意提供稿費和禮品。同時歡迎同學們將更多有意義的文章分享給我們，幫助更多的OIer一起成長！
