【正文】
lookout for processing data in reverse order or building an attack that looks at the data in some order or fashion other than the obvious. Simplification Some problems can be rephrased into a somewhat different problem such that if you solve the new problem, you either already have or can easily find the solution to the original one。 use this to rewrite and improve your game plan! Complexity Basics and order notation The fundamental basis of plexity analysis revolves around the notion of ``big oh39。 but you might be able to solve another from scratch in 45 mins. When do you go back to a problem you39。 Receipted from Translated by Starfish 原文: Crafting Winning Solutions A good way to get a petitive edge is to write down a game plan for what you39。 對稱 許多問題中存在著對稱(例如,無論你按哪一個方向,一對點(diǎn)之間的距離通常是相同的)。 預(yù)先計(jì)算 有時生成表格或其他數(shù)據(jù)結(jié)構(gòu)以便快速查找結(jié)果是很有用的。 當(dāng)你在處理有關(guān)排列組合之類的算法時,記住N個元素的排列有N!個,N個元素的組合或N個元素組成的集合的冪集的有2 n個。 經(jīng)驗(yàn)法則 在分析一個算法以計(jì)算出對于一個給定的數(shù)據(jù)集它可能要運(yùn)行多長時間的時候,第一條經(jīng)驗(yàn)法則是:現(xiàn)代(1999)計(jì)算機(jī)每秒可以進(jìn)行10M次操作。 復(fù)雜度 基礎(chǔ)和階符號 復(fù)雜度分析的基本原理圍繞著符號“大O”,例如:O(N).這意味著算法的執(zhí)行速度或內(nèi)存占用將會隨著問題規(guī)模的增倍而增倍。 重新編譯并再測試一次。(從“短”到“長”的次序?yàn)椋阂郧白鲞^的,容易的,不熟悉的,困難的) 編寫程序解決一個問題 —— 對每一道題而言,一次一道題 確定算法 構(gòu)造特殊情況的測試數(shù)據(jù) 寫出數(shù)據(jù)結(jié)構(gòu) 編寫并測試輸入子程序(編寫額外的子程序來顯示數(shù)據(jù)輸入的正確性) 編寫并測試輸出子程序 逐步細(xì)化:通過寫注釋來刻劃程序的邏輯輪廓 一個部分一個部分地填充并調(diào)試代碼 完成代碼使其正常運(yùn)轉(zhuǎn),并驗(yàn)證代碼的正確性(使用一般情況的測試數(shù)據(jù)) 試圖證明代碼錯誤(??原文是Try to break the code)——使用特殊情況的測試數(shù)據(jù)來驗(yàn)證代碼正確性 逐漸優(yōu)化——但足夠了即可,并且保存所有的版本(使用困難情況的(即運(yùn)行時間長的)測試數(shù)據(jù)來計(jì)算出實(shí)際運(yùn)行時間) 時間安排策略和“故障控制”方案 制定一個計(jì)劃決定在各種(可預(yù)測的?。┕收习l(fā)生時的行動;想象你可能遇到的問題并計(jì)算出你所希望做出的反應(yīng)。設(shè)計(jì)獲勝策略設(shè)計(jì)獲勝策略 一個好的取勝之道是制定在競賽中指導(dǎo)你行動的策略。核心問題是:“你何時花費(fèi)更多的時間在調(diào)試程序上,你何時放棄并繼續(xù)做下一題?”。 將文件以正確的文件名復(fù)制到正確的位置(軟盤)。一個有著O(N 2)的算法在問題的規(guī)模增倍時其運(yùn)行時間將會減慢4倍(或者消耗4倍的空間)。對于一個有五秒鐘時間限制的程序,大約可以處理50M次操作。 對N個元素排序的最少時間是O(NlogN)。這種方法叫做預(yù)先計(jì)算(在這里用空間換取時間)。對稱可以是2路的(??原文是2way),4路的,8路的或是更多的。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。ve abandoned previously? When do you spend more time optimizing a program, and when do you switch? Consider from here out forget prior effort, focus on the future: how can you get the most points in the next hour with what you have? Have a checklist to use before turning in your solutions: Code freeze five minutes before end of contest? Turn asserts off. Turn off debugging output. Turn on all optimizations. Make sure input and output are to correct filenames. Make sure the input and output formats are correct. Repile and test once more. Copy files to correct locations (floppy?) with correct names. Tips amp