跳到主要內容

讀書筆記: Art of Programming Contest for uva 開始解題之前的提醒

第一章主要是給打算要進入程式競賽的人一些小提醒。
關於解題
  • 新手一開始最好先挑簡單的問題解，並想辦法用短時間快速解掉。
  • 如果花了很多時間也不要氣餒，你只是練習的還不夠。
關於程式
  • 只挑"一個"語言深入鑽研，透徹了解該語言的各種細節，讓它成為你的武器。
  • 高手解題時，思考和規劃會先用掉 45% 的時間，而最後的 45% 時間用來測試和除蟲，實際上只用10%的時間 coding。
  • 學會用 I/O 轉向，就不需要每次都浪費時間用手輸入測資
    • #ifndef ONLINE_JUDGE
freopen("INPUT_FILE", "r", stdin);
freopen("OUTPUT_FILE", "w", stdout);
#endif
關於算法
  • 不要只滿足於一個解法，盡量嘗試用多種不同方法來解同一題。這樣你才有機會比較不同演算法之間的差異，或碰著原本不會遇見的錯誤。
  • 演算法是一串解決特定問題的步驟，多學學各種不同的演算法。
  • 比賽時盡量選最簡單的演算法，並且平時作熟，比賽的時候沒有時間設計複雜的演算法。
  • 現在的電腦很快，迴圈跑個一百萬次也不需要多少時間的，不要斤斤計較小地方。
把程式寫的簡明
  • 少用複雜的程式語句、少用動態分派記憶體、少用指標。
  • 把每個變數的名字都命名清楚，像 Right_Most ，不要用縮寫 rm。
標籤：

留言

張貼留言

這個網誌中的熱門文章

讀書心得: 你以為你以為的就是你以為的嗎?

當初想要接觸哲學的時候，挑上的第一本書就是「你以為你以為就是你以為的嗎?」，因為書名太好玩了。讀完後發現內容也一樣好玩，整本書的形式有點像坊間流行的心理測驗小書，每章的開頭都要讀者先做一組題目，後面接著就對你的答案做一番分析。 我自己的讀後感是，恩，這些題目對一個以前從未接觸過哲學的人來說太過犀利，第一次作答的時候，每翻過一頁都好像在呼自己巴掌，臉頰很燙。 「你以為你以為就是你以為的嗎?」書名念起來很拗口，但是很貼切，因為這些題目為的是要檢查我們腦袋內的想法是否一致，在邏輯上有沒有BUG。 我舉個例子，書裡有道題目「只要不傷害他人，任何人都有權自由追求自己的目標」要讀者回答同不同意，我認為這句話聽起來相當合理，所以勾了同意。過了幾題後，出現另一道題目是「為個人吸食而持有毒品的行為應予除罪化」，這次我的直覺是毒品這麼危險，怎麼可以除罪化呢，馬上勾不同意。 但是，我沒有發現這是刻意安排的陷阱，因為這兩句話其實講的是同一回事。 單純個人持有毒品，不散佈也不販賣，就不算傷害他人，那他就應該有自由追求自己的「吸食毒品」目標的權利，畢竟他只有傷害自己呀。這敘述聽起來有點危險，不過我必須承認一開始的確想的不夠清楚，我以為第一句話是真理，但馬上被反例打了自己的臉。 再舉一個例子，首先是「對藝術品的評斷，純粹是個人品味的問題」，接著是「米開朗基羅是史上數一數二的偉大藝術家」，這牽涉到評斷藝術的標準，不過你只能認同兩句話的其中之一。 書中我最有興趣的是「神明DIY工作室」與「信仰殺戮戰場」，這兩章擺明了直衝基督徒而來。當中有些問題圍繞著以下的敘述，如果你同意「神是全知、全能、又全然慈愛」，那該怎麼解釋世界上發生的許多苦難呢? 比如說被南亞海嘯淹沒的小女孩? 如果神沒辦法消除這些苦難，祂就不是全能。如果神沒辦法事先知道創造出來的世界會有這些苦難，祂就不是全知。如果神明知道有苦難，也有能力去掉，但是卻故意不做，那祂就不是全然慈愛。 我思考後的結論是，全然慈愛的神並不等於神希望世上的苦難越少越好，這些苦難都是在祂的允許下發生的。 書裡指出了一個基督徒的通病，被問倒了之後就嚷嚷「你不知道神是超越人所理解的嗎 」，但回頭又馬上賦予神非常明確地人的屬性。後來我也理解到這些尖銳的問題並不是故意要為難我對神的看法，而是逼迫我去反思一些比較深層的宗教議題，就像我...
6 則留言
閱讀完整內容

[ACM] 自己整理一些有用的網站

=解題提示= UVa官方論壇： 全世界UVa討論的集散地，當你題目解不出來時，第一件事就該來這裡搜尋該題目的討論串，通常會找到很多好心人提供的測資跟提示。 Methods to Solve 全世界最大的UVa解題提示網站，收錄的題目數量很多，品質也不錯。 Algorismist 這是一個關於演算法的維基網站，也有收錄 UVa 的解題提示，如果你有能力可以參與編輯條目，讓它變得更好。 UVa Toolkit 一般來講UVa題目頁上的範例測資都太簡單，聊勝於無。而 UVa Toolkit 這工具恰好補足了這方面的缺憾，你可以餵給它任何測資，並取得正確的對應輸出，對釐清題意很有幫助。 uHunt 非常非常好用的 UVa 解題工具網頁，可以很輕鬆的搜尋題目，安排自己解題的方向，瀏覽自己過去的解題紀錄等等。 =題目中譯= Lucky貓 著名的ACM題目中譯網，及解題提示。 Lucky貓Mirror站 同上，有難度提示。 ACM中譯 少量題目中譯。 ZeroJudge ZeroJudge是非常優秀的國產程式解題網，裡面有一區專門收錄UVa題目中譯。 =算法教學= DJWS的網路日誌 資源豐富的網站，整理了很多的算法教學，以及各種ACM競賽的資料。 C語言考古題 & C的解題 大量題目教學 Art of Programming Contest for uva 淺顯的ACM入門書，免費線上版。 NACOW 對岸關於程式設計與解題的wiki Infinite Loop 提供許多教學及ACM Tips, Sources。 =API Reference= Cplusplus.com 簡潔清楚的C/C++標準函式參考手冊，範例碼清楚實用，值得看看，我自己把這兒當後花園逛了。 =題目列表= ACM熱題排行榜 芭樂題排行榜，有哪些熱門題你還沒解過呢XD =討論論壇= NPSC補完計畫 針對NPSC的解題網站 OIBH 對岸關於資訊奧林匹亞競賽討論的論壇 algogeeks Google group about algorithms. =解題強者= 這部分網站就請各位審慎參觀了，大部分ACMer的程式碼都寫得不太好讀。 心如止水 350+題目解答，有基本的...
5 則留言
閱讀完整內容