調和的靈感

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

Blog 之後都不會再貼出完整的解題程式，原有的程式也會慢慢修正成只提供關鍵片段。 題目寫稍微多一些之後，我發現赤裸裸地丟上程式碼，用處比我想像中要小的多了。為什麼呢? 因為我自己都不會去看別人的程式碼呀，不是說讀程式碼沒用，如果一隻程式沒有遵循良好的規範，又沒有加上註解的話，那我盯著十秒左右發現無法理解就會放棄了。以我自己的經驗，分享解題的想法或者給一個有用的測資，對解題者幫助往往大得多了。 寫 ACM 的樂趣不就是那徘徊在TLE、RE 與 WA 之間的痛苦糾結嗎，我分享 ACM 題目的本意是要人享受 ACM 的樂趣，不是順了抄襲者的意呀。

http://zerojudge.tw 為了練習GIT 我把我寫的所有ZeroJudge解答都放上GitHub啦 請參考這個連結 http://github.com/yrchen/ZeroJudge/tree/chchwy 上面同時還有禹任跟俊諺的解答 NetLab ZeroJudge團 在這裡誠摯的歡迎您的加入 一同切磋程式技巧

Debug用 #ifndef ONLINE_JUDGE freopen("848_input.txt", "r",stdin); freopen("848_output.txt","w",stdout); #endif 進階版getch(), ungetch() (from K&R) // ungetch(): push a char to stack // getch(): if stack is not empty, pop a char // or get a char from stdin. int buffer[1024]; int top = -1; //stack pointer void ungetch(int c){ buffer[++top] = c; } int getch(){ if(top > -1) return buffer[top--]; else return getchar(); }

by gits Original Thread http://online-judge.uva.es/board/viewtopic.php?t=7292 Well, I'll assume you understand what the problem asks. You have to find the shortest sequence that yelds a profit (not the one with the greatest profit!). If there is more then one sequence with the same length, any of those is valid. Now, you can't just try with brute force (trying all combinations) because it'll be too slow and you'll get Time Limit Exceeded. However, there's a well known algorithm, Floyd-Warshall, which will find all the shortest paths between every node to the others in just O(n^3) time. You can find more info about F-W in the net. In my previous post I said how you have to change the general F-W algorithm to work for this particular problem... As for floating point errors, most numbers representation isn't totally acurate; for instance, 0.1 is usually stored as 0.10000000000000001. After some operations, the error may influence the final result. Again, sea...

=解題提示= 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 比較快。