2008年9月30日 星期二

[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+題目解答,有基本的題目分類。
Nothing is Everything
少量UVa Source,品質不錯
小璋丸UVa解答 Java版
JAVA解題的強者。
摸索C語言
英雄出少年,解題高手,以Zero Judge為主。
朱色虫居
少量UVa解答,品質不錯
YT's ACM
高手解題夥伴YT的站
Kaipeng Liu's Column
大量UVa解答
Eddy's Blog
來自對岸的強者,解題不分國家呀。

2008年9月26日 星期五

[ACM] 加速法

觀念

有修過OS應該都知道,因為執行IO動作會牽涉到interupt、system call 等等機制,花掉非常多的時間。所以對大部分的ACM題目來說,減少IO的次數是加速的好方法。

關鍵點 : 「減少IO次數」


  1. Buffered Input: 不要用scnaf() 或者cin,用fgets一次讀進來,再parse字串。
  2. Buffered Outout: 先用StringStream輸出至memory,最後再一次印出。
  3. Buffered大小約在5000Byte左右,不要太小,也不要太大,導致Memory要做Swapping或paging。

其他小方法:

1. CPU通常會對4Bytes運算做最佳化(現在的32bit系統,應該也是對4Byte資料做運算最快),所以處理資料盡量用4Bytes當一個單位。

2. 但是超過一定的資料量大小,通常長度超過十萬的陣列,那麼整個陣列的體積反而影響比較大,這時能用char, short 比較快。