【正文】 by Starfish 原文： Crafting Winning Solutions A good way to get a petitive edge is to write down a game plan for what you39。 正向 vs. 逆向 令人驚訝地，許多競賽題用逆向法解決比正面突破要好得多。 對稱 許多問題中存在著對稱（例如，無論你按哪一個方向，一對點之間的距離通常是相同的）。競賽題經(jīng)常要用到素數(shù)——生成一長串素數(shù)在程序中某處使用通常是很實用的。 預(yù)先計算 有時生成表格或其他數(shù)據(jù)結(jié)構(gòu)以便快速查找結(jié)果是很有用的。 解決方案的范例 產(chǎn)生器 vs. 過濾器 產(chǎn)生大量可能的答案然后選擇其中正確的（比如8皇后問題的解答），這樣的程序叫做過濾器。 當(dāng)你在處理有關(guān)排列組合之類的算法時，記住N個元素的排列有N!個，N個元素的組合或N個元素組成的集合的冪集的有2 n個。 640K確實是苛刻的內(nèi)存限制。 經(jīng)驗法則 在分析一個算法以計算出對于一個給定的數(shù)據(jù)集它可能要運行多長時間的時候，第一條經(jīng)驗法則是：現(xiàn)代（1999）計算機每秒可以進行10M次操作。 一種推算一個程序的O( ) 運行時間的方法是檢查它的循環(huán)。 復(fù)雜度 基礎(chǔ)和階符號 復(fù)雜度分析的基本原理圍繞著符號“大O”，例如：O(N).這意味著算法的執(zhí)行速度或內(nèi)存占用將會隨著問題規(guī)模的增倍而增倍。 盡量不要使用浮點數(shù)；如果你不得不使用，在所有使用的地方設(shè)置允許的誤差（絕對不要測試兩個浮點數(shù)相等） 對注釋的注釋： 不要寫得太長，簡潔的注解就可以了 解釋復(fù)雜的功能：++i。 重新編譯并再測試一次。 在你上交你的答案之前列出一個校驗表： 在競賽結(jié)束前五分鐘凍結(jié)代碼？（？？原文是Code freeze five minutes before end of contest?） 將所有的聲明關(guān)閉。（從“短”到“長”的次序為：以前做過的，容易的，不熟悉的，困難的） 編寫程序解決一個問題 —— 對每一道題而言，一次一道題 確定算法 構(gòu)造特殊情況的測試數(shù)據(jù) 寫出數(shù)據(jù)結(jié)構(gòu) 編寫并測試輸入子程序（編寫額外的子程序來顯示數(shù)據(jù)輸入的正確性） 編寫并測試輸出子程序 逐步細化：通過寫注釋來刻劃程序的邏輯輪廓 一個部分一個部分地填充并調(diào)試代碼 完成代碼使其正常運轉(zhuǎn)，并驗證代碼的正確性（使用一般情況的測試數(shù)據(jù)） 試圖證明代碼錯誤（？？原文是Try to break the code）——使用特殊情況的測試數(shù)據(jù)來驗證代碼正確性 逐漸優(yōu)化——但足夠了即可，并且保存所有的版本（使用困難情況的（即運行時間長的）測試數(shù)據(jù)來計算出實際運行時間） 時間安排策略和“故障控制”方案 制定一個計劃決定在各種（可預(yù)測的?。┕收习l(fā)生時的行動；想象你可能遇到的問題并計算出你所希望做出的反應(yīng)。 心理上的準(zhǔn)備也很重要。設(shè)計獲勝策略設(shè)計獲勝策略 一個好的取勝之道是制定在競賽中指導(dǎo)你行動的策略。 競賽中的策略 首先通讀所有的題目；草擬出算法，復(fù)雜度，數(shù)量，數(shù)據(jù)結(jié)構(gòu)，微妙的細節(jié)，… 集體討論所有可能的算法 —— 然后選擇最“笨”但卻可行的算法。核心問題是：“你何時花費更多的時間在調(diào)試程序上，你何時放棄并繼續(xù)做下一題？”。 將調(diào)試輸出關(guān)閉。 將文件以正確的文件名復(fù)制到正確的位置（軟盤）。 /* increase the value of i by 1*/ 這樣的注釋是毫無意義的。一個有著O(N 2)的算法在問題的規(guī)模增倍時其運行時間將會減慢4倍（或者消耗4倍的空間）。嵌套最深的（因而也是最慢的）循環(huán)支配著運行時間，同時它也是在討論O( ) 符號時唯一考慮的循環(huán)。對于一個有五秒鐘時間限制的程序，大約可以處理50M次操作。幸運的是，19992000賽季將是這個限制的最后一次起作用。 對N個元素排序的最少時間是O(NlogN)。那些只產(chǎn)生正確答案而不產(chǎn)生任何錯誤節(jié)點的叫做產(chǎn)生器。這種方法叫做預(yù)先計算（在這里用空間換取時間）。 分解（編程競賽中最困難的事） 雖然在競賽中經(jīng)常使用的基本算法不超過20種，但是某些需要將兩種算法結(jié)合才能解決的組合型問題卻是很復(fù)雜的。對稱可以是2路的（？？原文是2way），4路的，8路的或是更多的。以逆序處理數(shù)據(jù)或構(gòu)造一種基于某種非明顯的方式或順序檢索數(shù)據(jù)的突破策略時，要特別小心。re going to do in a contest round. This will help you script out your actions, in terms of what to do both when things go right and when things go wrong. This way you can spend your thinking time in the round figuring out programming problems and not trying to figure out what the heck you should do next... it39。 verify correctness (use trivial test cases) Try to break the code use special cases for code correctness Optimize progressively only as much as needed, and keep all versions (use hard test cases to figure out actual runtime) Time management strategy and damage control scenarios Have a plan for what to do when various (foreseeable!) things go wrong。ve abandoned previously? When do you spend more time optimizing a program, and when do you switch? Consider from here out forget prior