2010年1月31日 星期日

UVa 382 Perfection

Special case 1 = DEFICIENT

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

2010年1月30日 星期六

Bizarre Love Triangle - by Frente!




中譯歌詞

Bizarre Love Triangle (Everytime i see you falling)


Every time I think of you
I get a shot right thought
Into a bolt of blue
It's no problem of mine
But it's a problem I find
Living the life that I can't leave behind

There's no sense in telling me
The wisdom of a fool won't set you free
But that's the way that it goes
And it's what nobody knows
And every day my confusion grows

Every time I see you falling
I get down on my knees and pray
I'm waiting for the final moment
You'll say the words that I can't say


I feel fine and I feel good
I feel like I never should
Whenever I get this way
I just don't know what to say
Why can't we be ourselves like we were yesterday

I'm not sure what this could mean
I don't think you're what you seem
I do admit to myself
That if I hurt someone else
Then I'll never see
Just what we're meant to be

Every time I see you falling
I get down on my knees and pray
I'm waiting for the final moment
You'll say the words that I can't say

Every time I see you falling
I get down on my knees and pray
I'm waiting for the final moment
You'll say the words that I can't say

UVa 10929 You can say 11

解題策略

數學常識老梗題,快速判斷11的倍數,把奇數位和偶數位相減,結果必為11的倍數。

注意

請通過這個心機測資 00011

UVa 10591 Happy Number

解題策略

所有的Happy Number從第二步開始就一定會降到729以下,也就是999999999的各位數平方和。
所以建個表來儲存計算過的結果完全可行。

我採用的方法比較極端,預先建好一張size=1000的表。
這樣保證找尋Happy Number的過程一定不會超過兩步,有點作弊就是了。

閒聊

一次AC 科科,也不是什麼很難的題目啦。

2010年1月29日 星期五

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

偶然發現一個不錯的網站

http://chowkafat.net/Mathtopic.html

「點算組合學」是本人喜愛的數學分支之一,本專題將以循序漸進,由淺入深的方式介紹「點算組合學」的基 本知識和解題技巧。由於本人學識有限,本專題只擬介紹該學科最基礎的知識,包括「排列和組合」、「容斥 原理」、「母函數」、「遞歸關係」等題目。 
本專題旨在介紹筆者所認識的「點算組合學」的有趣知識,因此著重對該學科最基礎定理的直觀理解,而無意 包羅該學科的所有定理,亦無意進行嚴謹的數學推導。讀者如欲對該學科有更深入的認識,可參閱相關的教科 書。

作者用了一系列的文章,清晰淺顯的解釋了組合數學的精華

2010年1月28日 星期四

UVa 343 What Base is This?

一魚三吃
相似度85%的題目

目前是單純的暴力法,應該有辦法把算過的結果cache起來。

2010年1月27日 星期三

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