跳到主要內容

發表文章

目前顯示的是 11月, 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 name re-build press "F8" into debug mode press "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