調和的靈感

=解題提示= 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+題目解答，有基本的...

觀念 有修過OS應該都知道，因為執行IO動作會牽涉到interupt、system call 等等機制，花掉非常多的時間。所以對大部分的ACM題目來說，減少IO的次數是加速的好方法。 關鍵點 : 「減少IO次數」 Buffered Input: 不要用scnaf() 或者cin，用fgets一次讀進來，再parse字串。 Buffered Outout: 先用StringStream輸出至memory，最後再一次印出。 Buffered大小約在5000Byte左右，不要太小，也不要太大，導致Memory要做Swapping或paging。 其他小方法： 1. CPU通常會對4Bytes運算做最佳化(現在的32bit系統，應該也是對4Byte資料做運算最快)，所以處理資料盡量用4Bytes當一個單位。 2. 但是超過一定的資料量大小，通常長度超過十萬的陣列，那麼整個陣列的體積反而影響比較大，這時能用char, short 比較快。

本題重新寫過，請看這裡 [UVa] 101 The Blocks Problem @2009.11.12

本書作者之一賴名宗曾說過一句話，我覺得非常棒：「（學習） 什麼時候有了正確的觀念和目標，就什麼時候入門了。」那麼本書最大特點，就是建立正確物件導向觀念。 我早些年曾經在網路上看過一篇文章叫「 不要從程式語言學習物件導向 」，第一次讀時我看不懂。對我來說，物件導向不就是那些 class、new、public  等等的語法嗎？不從程式語言學還能從哪裡學呢？大多數坊間書籍只從「程式語法」的角度切入物件導向，受此影響的人（包括我）自然也曾經以為學會了 JAVA 就已經摸透物件導向了。 這個困惑直到我讀完了「世紀末軟體革命」後才稍微解開，物件導向之所以長青不倒的原因，是因為背後有一套組織程式的世界觀: 「程式是為了模擬世界」，「程式由物件組成，物件之間互相發送訊息」，而語法不過是實現整個思考架構的最末節。這樣來看，本書的撰寫順序「先OO，後C++」，這個次序才真的能抓到物件導向思考的脈絡。 本書從背景遠因─軟體危機的歷史背景開始，引出物件導向思想發芽，背後的理念精神「電腦運算的是為了模擬真實世界」，然後介紹比較完整的物件導向理論，最後，才以這樣的知識基礎下介紹C++ OOP。此時來看 C++ 的OO部份，眼光高度就有差異了，也可以知道C++並沒有完美的實踐所有的OO精神。 從思想起源再到程式實踐方法，一路娓娓道來，深入淺出，故事跟插圖很多，程式碼卻很少，架構起一個堅實又不艱澀的的地基。大學寫程式寫了四年，但是要問我何時真正開始瞭解物件導向？ 我會說從讀過這本書開始。 另外這本書給我的感動並不只單純在技術上，這三位作者寫書的時候，都還只有20歲，文字語氣中或多或少都還帶著 BBS 上的那種大學生的說話口吻，就像賀元說，他們當初寫書的動機，也只是看了一些好書想要把想法分享給大家而已，但是這本書暢銷到隔了十年還能再出「復刻版」，讓我思考，也許我自己能做的更多，年輕人就該帶有一些瘋狂的想法然後瘋狂的行動。 侯捷的二版序八個字道盡我心中的感覺 『鷹揚年少、氣吞牛斗』。 本書有一些小缺點，像涵蓋的議題很大，想要包山包海，結果貪多嚼不爛，有些細節就模糊帶過。作者之一賴明宗現在是PTT CSSE版主，可以去朝聖一下。

strlen( ) 不算'\0' ，但是會算'\n'。所以strlen("hello") 結果是5，strlen("hello\n") 結果是6。換行符號也算一個char，很容易被遺忘。 宣告string的時候，通常用的格式 char[MAXLINE+1]，最後那個1，就是拿來放字串的結尾'\0'的。 從stdin讀字串的方法: cin>>s; 讀一個單字，遇到空格or換行停止，空格or換行不會存進字串s。 cin.getline(s, length) 讀一行，遇到換行才停。 fgets(s, sizeof(s), stdin) 最後那個'\n'也會被包含在輸入字串裡。 cin.getline(s,length)則不會包含'\n'

解題策略 很多人的第一題ACM，老老實實按照題目指示做就沒問題。把計算cycle length抽出來作一個獨立的函數的話，程式會清晰很多。 注意 這題有個隱陷阱，就是題目給的a,b值不一定是a小於b，也可能a大於b，十個人裡有九個半都是栽在這裡，請跑跑以下關鍵測資: 1  10 結果應該印出 1 10 20 10  1 結果應該印出 10 1 20

來貼蔡神的簽名檔XD Proof techniques #1: Proof by Induction. Q: 試用歸納法證明:飯永遠吃不飽. 1. 吃一粒米顯然不會飽 2. 假設吃了 n 粒米沒有飽 再吃一粒米顯然也不會飽, 就是說吃 n+1 粒米也不會飽 由此可推得米飯永遠吃不飽 ! QED. (QED translates from the Latin as "So what?")