跳到主要內容

發表文章

目前顯示的是 十一月, 2009的文章

UVa 583 Prime Factors

解題策略這題要做質因數分解,只要先用篩法建好質數表,接下來就簡單了。
要注意的是這題的數字非常大,很接近 int 的上限,一個不小心就會溢位,要小心。

UVa 516 Prime Land

解題策略這題是考質因數分解,先把質因數分解表示法轉成數字,數字減一後,再轉回質因數分解表示法。

關鍵測資Input: 18 1 17 1 15 1 17 1 11 1 11 1 29 1 9 1 2 1 4 1 5 1 7 1 11 1 18 1 23 1 29 1 31 1 29 1 2 3 11 2 25 1 41 2 51 1 5 1 17 1 19 1 23 1 0 Output: 353 1 13 1 31 1 3 1 2 1 41 1 7 1 5 1 2 1 3079 1 7 4 5 1 449 1 2 1 3457 1 7 1 7 1 5 1 3 1 2 4 127 1 2 1 619 1 3 1 2 2
閒聊最近狂殺質數題。

UVa 10200 Prime Time

我一直以來使用的簡單質數檢驗法栽在這題,TLE
上網找了一下,發現2倍數可以先去掉不除
雖然只是簡單的小技巧,但效果很明顯
檢驗過程時間降了一半

就靠著這樣AC了

UVa 10533 Digit Prime

最近都在研究質數問題

本題因為IO量極大
原本只建了質數表,發現不夠快(TLE)
索性連DigitPrime累計表也建起來
dpCum[n]: 從0~n 累計總共有幾個Digit Prime
這樣每筆測資的時間就降到O(1)

這陣子學了不少質數的技巧
像是這題用的高速篩法

像這種百萬等級的問題,建表都很快
另一題大到十億左右,建表就太慢了

在Code::Blocks上使用GDB

Project's Build Option -> Compiler選項
Produce debugging symbols(-g) (打勾)
Strip all symbols from binary(-s) (不要勾)插入Break point左邊 "Watches" Tag -> right click "Add watches" -> 輸入 variable namere-buildpress "F8" into debug modepress "step into" to see the variable content step by step

UVa 101 The Blocks Problem

解題策略模擬機器手臂推方塊,典型的模擬題,乖乖照著命令的意思操作方塊,然後細心一點吧。

這題雖然有四個命令 [move/pile] a [onto/over] b,但是仔細觀察,就發現命令只分成兩種,一種是搬動方塊之前,要把目標上面的方塊都歸位(move/onto),另一種是整疊方塊直接跟著搬動(pile/over)。

以下的程式,move()是搬動方塊,clear_above()是歸位的動作。整個處理的主迴圈就長這樣:
// 指令格式 [move/pile] a [onto/over] b while( scanf("%s %d %s %d", cmd1, &a, cmd2, &b)==4 ) { // 排除不合理的命令 if(a==b) continue; if( in_the_same_stack(a,b) ) continue; // [move a] 把a上頭的方塊都歸位,[pile a] 則什麼都不做。 if( strcmp("move", cmd1)==0 ) clear_above(a); // [onto b] 把b上頭的方塊都歸位,[over b] 則什麼都不做。 if( strcmp("onto", cmd2)==0 ) clear_above(b); // 搬動方塊 move(a,b); }
閒聊把年以前寫的爛code重新整理了一番,把linked list換成vector,速度也小進: 0.030s -> 0.008s。

以下完整code。


UVa 10315 Poker Hand

寫這支程式比較像在做苦工,因為規則實在很繁瑣,當初我差點要寫不下去,後來轉念一想,就當作給自己一個挑戰,把繁雜的事情寫得有條有理。

這是我第一次嘗試將Unit Test應用在UVa題目上(拿來對付這種煩人題目剛好)。成果很不錯,只要有強大完整的Test Case在,根本就不用怕改爛程式碼,或者是改東邊炸西邊這種事情發生。所以我在後期也大膽的修正了兩次架構,目前看起來算滿意,整個程式架構相當清楚,而且一次就AC了。

附上我的TestCase
ps.我用的是GTest (Google C++ Testing Framework)

題外話,最近跟0.008秒有緣,我已經連三題0.008秒AC了 XDDDDD