發表文章

目前顯示的是 一月, 2010的文章

UVa 382 Perfection

Special case 1 = DEFICIENT 試著把一些特例抽出來做最佳化,結果反而更糟:( 所以還是回歸最一般的狀況來解了。

UVa 10929 You can say 11

解題策略 數學常識老梗題,快速判斷11的倍數,把奇數位和偶數位相減,結果必為11的倍數。 注意 請通過這個心機測資 00011

UVa 10591 Happy Number

解題策略 所有的Happy Number從第二步開始就一定會降到729以下,也就是999999999的各位數平方和。 所以建個表來儲存計算過的結果完全可行。 我採用的方法比較極端,預先建好一張size=1000的表。 這樣保證找尋Happy Number的過程一定不會超過兩步,有點作弊就是了。 閒聊 一次AC 科科,也不是什麼很難的題目啦。

[推薦] 組合數學系列教學 "點算的奧秘"

偶然發現一個不錯的網站 http://chowkafat.net/Mathtopic.html 「點算組合學」是本人喜愛的數學分支之一,本專題將以循序漸進,由淺入深的方式介紹「點算組合學」的基 本知識和解題技巧。由於本人學識有限,本專題只擬介紹該學科最基礎的知識,包括「排列和組合」、「容斥 原理」、「母函數」、「遞歸關係」等題目。   本專題旨在介紹筆者所認識的「點算組合學」的有趣知識,因此著重對該學科最基礎定理的直觀理解,而無意 包羅該學科的所有定理,亦無意進行嚴謹的數學推導。讀者如欲對該學科有更深入的認識,可參閱相關的教科 書。 作者用了一系列的文章,清晰淺顯的解釋了組合數學的精華

UVa 343 What Base is This?

一魚三吃 相似度85%的題目 目前是單純的暴力法,應該有辦法把算過的結果cache起來。

UVa 389 Basically Speaking

 一魚兩吃,跟355幾乎一樣的題目。 5分鐘AC。

UVa 355 The Bases Are Loaded

提醒自己,每次WA都要檢查的事情 1. Bounded Condition ex. 0 2. 變數有效範圍 ex. 是不是超出int的有效範圍,必須改用long long ? 不然很浪費時間 哭哭 這題的另外一個感想就是C++ string實在很難用, 從以前就這樣覺得,這次更加深我的印象。 關鍵測資 5 3 0 16 16 7FFFFFFFFFF 10 10 9999 上面這三個都是有效測資(not illegal)

UVa 294 Divisors

這題的加速關鍵就在於質因數分解 例如 360 = 2^3 + 3^2 + 5 那麼360的因數個數就是(3+1)*(2+1)*(1+1) 其實作到質因數分解就可以在UVa拿到AC了 不過ZeroJudge的測資顯然要嚴酷許多 所以我建了質數表增加質因數分解的效率。 我解題時相當程度上參考了Sagit's code http://www.tcgs.tc.edu.tw/~sagit/acm/view.php?id=294 簡潔易讀的寫法,相當佩服 這題我還有個心得就是gcc -O2 這個參數 對vector的速度影響非常大 我跑這個測資 1 999990000 1000000000 不加-O2: 3.5 sec 有加-O2: 0.8 sec 加了O2後就極為逼近原生array的速度,幾乎看不出效能損失 只要有O2,我以後就可以開心的用vector啦 :D