本站遷移

因為我最近租用了網路空間以及網域,
故本站已遷移至新網站~
這邊的資訊已經正在進行搬移的工作~
希望各位可以到新網站去逛XD

New Website:
http://knightzone.org/

搜尋此網誌

2011年3月28日 星期一

[生活趣事/生活週記]3/20~3/26-吉他社學術例會-Echo回聲樂團

禮拜三去聽Echo回聲樂團拍的照片,
還蠻特別的一次體驗XD

[3/20](日)
早上去參加主日聚會,
中午在體育館附近念聖經,
一直到下午就去家教XD
然後就回家了~
似乎很平靜的過完一天!?

[3/21](一)
早上是離散數學、英文,
中午的貓咪果醬聚會改成探討未來發展的聚會XD
下午是程式設計,
上完後,就先弄獎學金的事情,
之後找教官談某個Project的事情,
接著我就和晉嘉兄跑去本部綜合大樓上Vocal班,
上完後就陪晉嘉兄去買肉串吃XD
然後就回家了~

[3/22](二)
上午是數位邏輯,
中午換新路哥哥載我到邵弟兄家,
新路哥哥騎車比聖別快很多>_<
剛開始不太習慣就是了~
這週讀了馬太五章,
提到很多種人都有福了,
我們應當操練成為這樣的人。
下午回家,
我媽在家裡,
我很累了就去睡,
結果睡過頭就沒去桌球= ="

[3/23](三)
早上晨興,
講到我們都可以從生命之泉源歡然取水,
很棒的體驗!
接著是自然探索課,
我還是搞不懂心得要交啥QQ
中午去聽了日文學程的說明會,
了解了一些規條,
接著就趕快趕去分部PC室,
然後就跟大家一起到B102上程式設計課。
晚上跟映竹搭車到本部,
去英文自學教室,
他後來先走,
我大概也只又待一下子就離開了,
然後到圖書館找書,
沒找到想要的,
接著就趕去綜合大樓,
去聽這次的例會,
也就是Echo回聲樂團來我們學校的Live Online,
很特別的一次體驗呢!XD

[3/24](四)
今天早上是邏輯概論,
將作業交出去了~XD
中午是照常貓咪果醬例會,
但是我們教學股也開會,
所以就先去教學股了解資工營的部份的狀況,
然後再去開例會,
開一下又趕去排演明天國文的戲。
下午是微積分,
聽了三個鐘頭結束後,
本來想去畫畫,
又想說作業好多,
而且我畫畫好爛= =
所以就回家去了。

結論是我趕作業趕到26:00= =...

[3/25](五)
早上是國文,
換我們這組演戲,
老師說我們演得很棒,
但是因為上次晉嘉兄那組晉嘉兄撞到頭,
所以還是只能獲得第二名,
第一名就被奪去了XD
不過也因此晉嘉兄沒去上課的事情就被發現了XDDDDDDD
接著是離散數學,
中場下課系主任來發問卷,
是要藉問卷來實施一個實驗,
就是可以讓部分同學不用來上離散數學,
自己找個時間去某間固定的教室看錄影帶來上課,
讓你可以挑有精神的時間去聽課,
感覺很棒的措施!
Ψω還說這是專門為他設計的XD

中午先交了一些獎學金要交的資料,
下午是數位邏輯還有實驗課,
我們還算早的就做完了,
然後我去繳交獎學金剩下來未繳交的資料,
也就是教授的意見,
因此我就上五樓去找蔣教授簽名,
然後就聊到TOI的事情,
聽到教授有去上課,
我才發覺TOI開始了XD
不知道元元、唯辰兄和盛文兄會不會保送呀XD~~

[3/26](六)
今天早上是生服社社課,
是上關於親的部份,
上完後,
聖別學長跟我談了申言是什麼,
我才比較明白申言XD

下午到晚上就在家裡玩瑪奇,
公會還遇到不太好的事件= =
就不多說了~

2011年3月21日 星期一

[生活趣事/生活週記]3/13~3/19 大三家聚

我通識課用的課本-多多鳥之歌,
講述關於島嶼分割所導致的物種獨特性與滅絕的書,
試著把它看完中XD

[3/13](日)
早上先帶河水和他的大學同學到師大的綜合大樓去上課,
接著趕去三會所參加全部不分區的主日聚會,
也是我第一次參加這種聚會XD
超多人!XD

中午和河水以及他的大學同學吃飯,
吃完我念了一下馬太福音,
接著下午就去家教,
不過家教的學生身體不適,
就沒有講太多。

晚上回家趕離散數學的作業...Orz
考慮是否要用紙寫,
去光華商場買了一疊A4紙,
有這疊真的讓我覺得超好用的XD

[3/14](一)
早上超早到,
這是為了要交離散數學的作業XD"
接著英文課,
教授說我們回去一定沒有做作業,
結果留了一點時間給我們做,
真是太棒了!XD
只是某晉嘉兄加上學期翹英文課共5次,
結果教授都沒點到他,
讓某庭書兄很氣憤XD

中午貓咪果醬聚會,
我們的團長晉嘉兄沒來,
我就教映竹和克里一些Ruby語言這樣。

下午程式設計,
還是睡著了(掩面)...

之後先回家,
然後到了快7點再趕到綜合大樓去上吉他社Vocal班的社課,
這個課超棒,
我超喜歡的XD

[3/15](二)
今天上午是數位邏輯的課,
接著聖別學長接我到邵弟兄家,
不過兩位家主人都不在,
我們就在邵弟兄家裡吃PIZZA,
讀了馬太四章,
告訴我們要多讀聖經,
這樣我們才能活用在生活上!

下午先去英語自學教室,
然後回家,
拿到了「多多鳥之歌」這本書!!
晚上接著又趕去男三舍的地下室桌球場打桌球,
我的基本動作又...Orz
球拍真的好想買新的呀!!!!!(吶喊

[3/16](三)
早上到弟兄之家晨興,
內容是要我們多接觸主!!

接著去上自然探索,
終於開始口頭心得報告了,
我的書才剛拿到還沒看呀~
不過還要很久才會輪到我。

中午趕去PC室,
晉嘉兄拿了一疊RGSS的程式碼給我,
我囧!
超大本的!
超難攜帶!

下午程式設計,
實在不知道該說什麼,
就只能說又睡著了Orz......

晚上去吃大三家聚,
去捷運大坪林那邊吃到飽的燒烤店,
還蠻好吃的!
某毓偉兄果然還是冰淇淋從頭吃到尾,
某庭書兄果然還是受不了誘惑XD(?

[3/17](四)
早上邏輯概論,
喉嚨開始不舒服...

中午貓咪果醬會議完後,
越來越不舒服= =

下午微積分,
不舒服到最高點...Orz

晚上到本部,和浩庭、安偉、映竹吃師大美食館,
還遇到吉他社的人XD
有阿緯(學長XD!!)、阿徹以及社長,
另外第四位似乎浩庭知道是誰!?
後來因為實在不舒服,就沒去動漫社社課了XD

[3/18](五)
一整天還是不舒服,
幸好國文不是我們這組要演戲,
不然我就......(汗
離散數學我實在又撐不住,
可是又要寫練習題,
真的很痛苦Orz...

下午數位邏輯,
還有實驗!XD
又碰到熟悉的東西了~
我們這組做的還算快,
做完後就離開了,
唯一沒事放學可以直接回家的,
就只有禮拜五晚上了XD!

[3/19](六)
早上還是不太舒服,
不過我還是去了生服社的社課,
還讓我吃了兩頓早餐XD
(出門前一頓,到教會一頓XD)
希望兒童品格營的籌備能夠非常順利呀>_<

下午晚上沒什麼事情,
瑪奇度過...耶!?

2011年3月20日 星期日

[UVa]105:The Skyline Problem

新站連結於http://knightzone.org/?p=1565

2011年3月19日 星期六

[UVa]10010:Where's Waldorf?

這題要注意的有幾個點:
1.尋找字串的時候雖然有八方位,
但是凡決定要走哪個方位後,
就只能朝著同一個方位走,
不能彎來彎去。
2.字母相等不分大小寫。
3.要以左上方為優先,
就要以斜線的方法來定X和Y,
相信被8皇后題目訓練過,
就會知道要用X+Y來搜尋XD

[C](0.008)

2011年3月18日 星期五

[UVa]679:Dropping Balls

這題我是用二進位的方式去表示,
假設今天有4層:
第一顆球會落在2進位的1000,也就是10進位的8的位置。
第二顆球會落在2進位的1100,也就是10進位的12的位置。
第三顆球會落在2進位的1010,也就是10進位的10的位置。
第四顆球會落在2進位的1110,也就是10進位的14的位置。
...以此類推。
各位會發現到答案其實就是2的(層數-1)次方加上2進位倒過來的(次數-1),
例如4層的第一顆球就是2^(4-1)+倒置(1-1)=8+0=8。
4層的第二顆球就是2^(4-1)+倒置(2-1)=8+倒置(001(2進位))=8+(100(2進位))=8+4=12,
這樣即可得解。

[C](0.052)

[UVa]11342:Three-square

這題請建表。
建表有兩個方式:
一個是像質數篩法那樣,
將a*a+b*b+c*c的那格填入答案。
另外一個是比較慢,也是下面的程式碼的作法,
直觀地真的去找每個數的答案,
但是要注意a,b,c的範圍避免TLE。

[C](0.568)

2011年3月17日 星期四

[UVa]10394:Twin Primes

建質數表得解。

[C](1.492)

2011年3月16日 星期三

[UVa]116:Unidirectional TSP

新站連結於http://knightzone.org/?p=2204

[UVa]10192:Vacation

LCS(Longest common subsequence)的問題。

[C](0.012)

[UVa]264:Count on Cantor

找出第幾斜排以及第幾斜排的最末項還有第n項的分母與分子這四者的關係,
即可得解。

[C](0.012)

[UVa]10405:Longest Common Subsequence

LCS(Longest common subsequence)的問題。

[C](0.048)

2011年3月15日 星期二

[UVa]10066:The Twin Towers

LCS(Longest common subsequence)的問題。

[C](0.008)

[UVa]10684:The jackpot

DP題,
利用另外一個陣列記錄到從前面連續到目前這格贏最多的錢是多少,
再找這裡面全部最多錢的即是答案。

[C](0.088)

[UVa]10258:Contest Scoreboard

照著題目說的做即可得解。
要注意,當某題目被AC後,
後面如果同組有再送同樣那題,
就不用再去增加那題的懲罰時間。
(不過個人不確定會不會有這種可能性就是了。)

[C++](0.016)

[UVa]11689:Soda Surpler

這題要注意的是:換完後的汽水罐,等喝完後還可以再換,所以不是只能換一次這樣。

[C](0.012)

[UVa]11661:Burger Time?

從頭開始搜尋,
一直不斷比較最後找到的D和R的間距是否為最小的即是解答。
(當然如果裡面有Z,那答案一定是0)

[C](0.356)

2011年3月14日 星期一

[UVa]11185:Ternary

利用平常轉換位數的方法來轉換成3進位。

[C](0.008)

[UVa]10963:The Swallowing Ground

直接檢查每個y的裂痕是否相等即可得解。

[C](0.016)

[UVa]10929:You can say 11

1.此題數字過大,需用字串存取,
轉成數值必須經過ASCII碼的換算。

2.判斷11的倍數:偶數位和與奇數位和之差需要是11的倍數。

3.判斷N是否為0,必須判斷N[0]=='0'和N[1]=='\0',不然會WA。

[C](0.016)

[UVa]11059:Maximum Product

直接Brute Force去尋找乘積最大的連續數字。

[C](0.012)

2011年3月12日 星期六

[幻想迷宮]第五關完工

第五關總算是完工了!
也算是除了隱藏關卡以外,全部關卡都完成了!
看來發佈日指日可待~
這關特色第一個是迷宮變得比前幾關來得複雜且長。
第二個特色就是......水上倉庫番!?
最後來個結尾XD

[UVa]10903:Rock-Paper-Scissors Tournament

趙著題目要求做即可得解。

[C](0.208)

[UVa]10812:Beat the Spread!

暴力法得解。

[C](0.012)

[UVa]10789:Prime Frequency

利用質數表和ASCII碼就可以快速解完此題。

[C](0.016)

[UVa]10673:Play with Floor and Ceil

首先,要先知道兩個括號的意義:
┌ ┐ => 取無條件進位(即是取ceil值)
└ ┘ => 取無條件捨去(即是取floor值)
接著p和q就刷過各種可能即可得解。

[C](1.528)

2011年3月11日 星期五

[UVa]10589:Area

計算點距離四邊點的距離是否都在a以內即可得解。

[C](0.112)

[UVa]10550:Combination Lock

此題感覺很簡單,
但是請你一定要想一想,
如果你順時針轉數字鎖的時候,
數字卻是會逆時針轉動的!= =
我被這個騙了三次......

[C](0.016)

[UVa]10499:The Land of Justice

如果是沒切的情形(1塊)利潤就是0%,
因為與原本的價格一樣。

分2塊的時候,表面積會比原本球的表面積多2塊半圓,
一塊半圓會佔利潤的25%(π*r/4*π*r=1/4=25%),
所以2塊的時候是50%的利潤。

分3塊的時候,表面積會比原本球的表面積多3塊半圓=>75%。
分4塊的時候,表面積會比原本球的表面積多4塊半圓=>100%。
以此類推......

[C](0.044)

2011年3月9日 星期三

[幻想迷宮]第四關完工

雖然說其實我兩天前就做完了,
而且也已經請河水(后羿射月亮)測試過了,
但今天才把一些Bug修訂完成。
第四關的特色在於不能把木板再度拔起來利用
對於要直接過關不拿盡頭的人來說,
木板數會是剛剛好的。
而對於要拿盡頭的人來說,
也得考慮先走哪的情形才不會卡關喔!

這關還出現了可以一次拿到兩塊木板的盡頭,
這是之前幾關沒有的,
這是為了補足要拿到所有盡頭的木板數。
(其實實際上全部一塊也是夠,
不過測試員認為還是多一點感覺比較不會刁難玩家XD)
最後當然是破關圖啦!(照例沒有拿到所有盡頭=D)
題外話:
出現了秘密的角色喔!
他會是誰呢?XD

[UVa]10473:Simple Base Conversion

利用C++的<iomanip>中的setbase()快速過關。=D

[C++](0.064)

[UVa]10370:Above Average

照著題目算即可得解。

[C](0.020)

[UVa]10340:All in All

利用兩個變數i,j,
i從t開始搜,
搜到與s[j]一樣就讓j++,
這樣到最後如果j與s字串的長度一樣,
即表示答案是Yes,
反之則是No。

[C](0.012)

[UVa]10300:Ecological Premium

只要把農場面積和環境等級相乘即是解答。

[C](0.016)

[UVa]10222:Decode the Mad man

先把鍵盤輸入成一個字元陣列,這樣比較好轉換。

[C](0.016)

[UVa]10209:Is This Integration ?

要算面積,
令邊長為a,
一塊斜線的面積為x,
一塊點狀的面積為y,
一塊格子狀的面積為z。

則首先
正方形的面積減去四分之一以a為半徑的圓的面積
= a*a - a*a*π/4 = y+2*z ->(1)

再來六分之一以a為半徑的圓的面積減去以a為邊長的正三角形(想想看在哪裡...)
= a*a*π/6 - a*a*sqrt(3.0)/4 = 假設為某個面積w(想想看在哪裡...) ->(2)

接著把四分之一以a為半徑的圓的面積減去六分之一以a為半徑的圓的面積
= a*a*π/4 - a*a*π/6 = y+z+w ->(3)

則z=(y+2*z)-(y+z+w)+w=(1)-(3)+(2)就出來了,
那麼y=(y+2*z)-(2*z)=(1)-2*z也出來了,
而x=a*a-4*y-4*z也跟著出來了!

[C](0.056)

2011年3月8日 星期二

[UVa]10141:Request for Proposal

照著題目要求的做即可。

[C](0.012)

[UVa]10107:What is the Median?

將數值一直由小到大插入陣列中,即可得其中位數。

[C](0.044)

[UVa]10082:WERTYU

先把鍵盤打成一個陣列,這樣比較好得解。

[C](0.016)

[UVa]10038:Jolly Jumpers

新站連結於http://knightzone.org/?p=1230

[UVa]10035:Primary Arithmetic

新站連結於http://knightzone.org/?p=1227

[UVa]10018:Reverse and Add

新站連結於http://knightzone.org/?p=1223

[UVa]913:Joana and the Odd Numbers

新站連結於:http://knightzone.org/?p=1220

[UVa]750:8 Queens Chess Problem

8皇后問題,利用backtracking得解。

[C](0.012)

2011年3月7日 星期一

[UVa]291:The House Of Santa Claus

利用backtracking把所有解都跑一遍即可。

[C](0.008)

[UVa]439:Knight Moves

八種可能的走法去BFS得解。

[C](0.012)

[UVa]532:Dungeon Master

三維的BFS即可得解。

[C](0.016)

[UVa]11195:Another n-Queen Problem

這題要用點bitwise運算的概念,
把原本用陣列記錄列、斜線的放置,
改成用bits來記錄。
由於有點複雜,
我稍微解釋一下程式碼。

y_board[i] = (1<<n)-1;
這裡是讓可以放置皇后的位置用1來記錄,
不可以放置皇后的位置('*')用0來記錄。
那y_board這個陣列是以row(y)來當索引值,
然後col的部份用bits來記錄。
if( s[j] == '*' )
  y_board[i] ^= (1<<j);
這裡就是讓*的位置用1來做XOR運算,
簡單來說就是把j位置的1改成0。
backtracking( n, 0, (1<<n)-1, (1;<<(2*n-1))-
1, (1<<(2*n-1))-1);
這邊把記錄x和記錄兩種斜線的bits丟進去backtracking,
並且x的n個位數都是1,表示目前都可以擺,
而斜線部分的2*n-1個位數也都是1,也表示目前都可以擺。
int nowslash1 = slash1 >> y;
int nowslash2 = slash2 >> (n-y-1);
將目前跑到那行row的斜線號碼全部抓出來,
例如8皇后的第一個row(row[0]),
x+y種類的斜線編號分別是
0+0=0,0+1=1,0+2=2,0+3=3......0+7=7,
也就是說用slash1 >> 0,
這樣即可讓slash1從個位數(2進位)開始的7個位數都剛好對應每一格。
而x-y+(2*n-1)種類的斜線編號分別是
0-0+15=15,0-1+15=14........0-7+15=8,
正好是從高位數(2進位)數過來0位數,
那為了推到個位數(2進位),
就變成slash2 >> 8-0-1,
這樣就可以讓高位數(2進位)的7個位數推到個位數(2進位)來。
int canputqueen = y_board[y] & x & nowslash1 & nowslash2;
用&看看每一格是否能夠放置皇后,
y_board[]檢查是否為*,
x檢查是否這個col被放置皇后,
nowslash1檢查是否這條斜線被放置皇后,
nowslash2檢查另外一種斜線是否被放置皇后,
如果全部都是1,就表示這格可以放置皇后。
while( canputqueen )
{
  xput = canputqueen & (-canputqueen);
  backtracking( n, y+1, x^xput, slash1^(xput<<y), slash2^(xput<<(n-y-1)) );
  canputqueen ^= xput;
}
第一行自己&負自己,可以得到二進位最低位的1,
而我就從這最低位的1開始放置皇后,
那麼x就要記錄放置皇后,
而slash1和slash2也要記錄放置了皇后,
最後再將這個1從canputqueen裡面去除,
再繼續把皇后放在下一個1的位置。
我不知道這樣是否有助於讓你了解這題,
如果還是不了解就底下留言問,
或是先自行推演看看,
或是問其他你認識的人討論這樣XD

這題我剛開始就直接backtracking,
結果時間就爆掉了= ="
後來看到討論都說要用bitmask,
我就用了,
然後一直RE,
結論是我沒加return 0; = =""""""

[C](0.956)

2011年3月5日 星期六

[UVa]10048:Audiophobia

這題是all-pairs shortest paths的問題,
我用Floyd-Warshall Algorithm解決掉XD

[C](0.028)

[幻想迷宮]第三關完工

第三關完工!
第三關的特色是水上傳送迷宮。
剛開始做的時候爆LAG,
害我去找了好多防止EVENT過多而導致LAG的腳本,
目前是好多了!
放幾張圖給各位看看吧!



另外我去掉了Shift加速的功能,讓剛開始就是加速的速度,
還有多加了ESC就可以重新開始的功能,
這是為了第四關先做好的!XD


最後來張破關圖,感謝各位期待,
下次進度再見了喔!^^/

[生活趣事/生活週記]3/2~3/4 晨興的禮拜三與忙碌的禮拜四


呃...其實我是照著我的大頭貼畫的,
我知道我畫的很爛,
不過這是在這段期間畫的就是了,
也補起Blog文章的圖片XD"

[3/2](三)
早上在弟兄之家和聖別學長晨興,
今次的內容讓我了解到傳福音就是為了要延續這個基督的生命,
讓這個基督的生命能夠延續下去,
蠻寶貝這個以賽亞書五三章10~11節這裡的這部份:「祂必看見後裔,並且延長年日。」
感謝主!

接著就去上自然探索,
今天聽到了教授的遊記和看到了教授出外遊玩的照片以及他的畫,
他用畫的來畫出日記,
超有趣!

因為比較早下課,
所以就到生服的攤位去發傳單,
發傳單超難!
完全不敢過去發Orz...
不過我還是有發到幾張,
感謝邵淮和蓉圓願意拿傳單XD

中午趕去上丹丹大大的簡報課,
我聽到很多好用的功能XD
我決定要來設計屬於自己的簡報Style了!

下午是程式設計(二),
教授講解作業怎麼寫,
然後他已經幾乎要上完Tree了,
超快!XD

晚上,我和浩庭去光華商場挑他要買的外接硬碟,
很碰巧地遇到我媽要幫她的朋友買MP3/MP4,
買完後我們就去吃麻醬麵,
小碗還是很大一碗= =""
然後浩庭到我家,玩我現在幻想迷宮的進度,
玩完後,我還給他看了VVVVVV和Magicka,
還有讓他玩了Clickr。XD

[3/3](四)
早上爬起來,
就趕緊去上邏輯概論,
然後老師說:「雖然我們學校是定9:00上課,
不過因為連三堂的關係,
我們第一節課從9:10上到10:00這樣。」
把下課都壓在10分鐘,
然後可以晚一點到,
好棒!!XD

中午是貓咪果醬的會議,
大概是討論各組要怎麼規劃我們將來的行程,
如此等等。

下午是微積分課,
在還沒上課前,我就畫了上面那張圖XD"
畫的還蠻糟的,繼續加油Orz......
微積分教授上的也蠻快的,
不過講得都很清晰,
能了解他在講什麼。=D

晚上是動漫社的社課,
我請Honey Bee學長訂的書來了XD
是一本骨架書,還蠻難翻的。
我覺得光要畫好軀幹的骨架就難翻天了Orz...
結果我一整堂都在研究軀幹骨架XD""""""

[3/4](五)
早上是國文,分組又要演戲,
不過演戲放在期初,真的比較好,
可以比較有時間準備!
接著是離散數學,
教授沒來,我們用教授原本錄好的影片上課XD
還有做練習題XD

中午去申請了成績單,
然後到學七吃燒臘,
燒臘部超棒!!
吃完就去找我們的前班代(現任副班代),
教他程式設計作業的部份。

下午是吳老大的數位邏輯,
上的很開心,
因為當他講到OR、AND運算的時候,
我們在離散跟邏概都很熟了,
現在最主要要看的是如何利用這些運算表現數位電路的運作,
感覺還蠻棒的XD

上完課後,
我、威豪、維倫、安偉、ψω還有映竹就到公館去,
去光南買東西,
最主要是映竹要買他的Eee PC的「小」外接鍵盤,
還有安偉要買的東西。
買完後就回家了=D

2011年3月4日 星期五

[UVa]10285:Longest Run on a Snowboard

利用DFS來解即可。

另外不一定要從大往小走,
也可以反向變成從小往大走,
這樣可以在陣列第0列和第0行的地方加入一排0,
讓DFS可以把判斷是否走出陣列的地方給簡化。

還有就是每個點走完最長路線可以記在陣列裡,
這樣就可以直接拿來用。

[C](0.040)

[UVa]10327:Flip Sort

即是計算Bubble Sort的交換次數。

[C](0.088)

[UVa]10336:Rank the Languages

利用BFS或是DFS把每塊區塊都找出來即可。

P.S. 寒訓比賽我用BFS,但到了看到這題來解的時候我改用DFS了XD"

[C](0.012)

2011年3月3日 星期四

[UVa]167:The Sultan's Successors

典型8皇后問題,利用backtracking即可得解。

[C](0.016)

2011年3月2日 星期三

[UVa]534:Frogger

此題是最短路徑問題,
可以利用dijkstra法來解決。

[C](0.012)

[UVa]494:Kindergarten Counting Game

新站連結於http://knightzone.org/?p=1211

[UVa]488:Triangle Wave

新站連結於http://knightzone.org/?p=1208

[UVa]478:Points in Figures: Rectangles, Circles, Triangles

新站連結於http://knightzone.org/?p=1205

2011年3月1日 星期二

[UVa]477:Points in Figures: Rectangles and Circles

新站連結於http://knightzone.org/?p=1202

[UVa]476:Points in Figures: Rectangles

新站連結於http://knightzone.org/?p=1197

[UVa]374:Big Mod

首先,
要先知道數學式子:(A*B)%C = (A%C) * (B%C)。
因此我就可以不用把B^P算完再去對M取餘數,
但是如果是((((B%M)*B)%M)*B)%M.....的話,
會TLE的,
所以算次方請用次方除二相乘的遞迴來算次方,
也就是 (B^P)%M = (B^(P/2)%M) * (B^(P/2)%M) 這樣遞迴。

[C](0.012)

[UVa]386:Perfect Cubes

硬爆解,每個都試試看就可以算出答案了。

[C](0.136)

[UVa]382:Perfection

先建質數表,將輸入值給質因數分解,
利用質因數分解的結果求出所有因數之和,
將所有因數之和扣除掉自己本身,再比較大小即是答案。

P.S. 利用質因數分解的結果求出所有因數之和是數學的公式,
是每一個質因數從自己的0次方加到自己在質因數分解中的最高次方,
接著在把求出來所有的和相乘起來即可得解。
Ex. 12: 2^2 * 3^1
12所有因數之和:(2^0+2^1+2^2)*(3^0+3^1) = (1+2+4) * (1+3) = 28
驗證:12之因數:1,2,3,4,6,12
12所有因數之和:1+2+3+4+6+12=28

[C](0.016)

[生活趣事/生活週記]3/1-讀馬太二章&程式設計能力檢定(初級)

今天早上上完數位邏輯,
我跟著聖別學長到邵弟兄加吃飯讀經,
今日是讀馬太2章,
我藉著這次讀經才總算懂這個星象家原來是先走錯路,
之後才藉著聖經走回正確的路上,
之前這段好像看過去只覺得是星象家找到耶穌而已,
好深的含意在裡面都沒發現呀>_<
感謝主,今天的內容我得著了很多!

下午跟著聖別學長回到分部,
我就到PC室繼續解ACM~XD
解的差不多,
順應3月的到來,
我也順便把Blog背景換成春季綠意盎然的樣子了~
希望各位會喜歡!

晚上就是程式設計能力檢定(初級),
有三題,
我都是硬爆XD"""
然後在快到8點的時候解完了,
接著我就回家了。

今天看來幻想迷宮是沒什麼進度就是了~XD

[UVa]357:Let Me Count The Ways

這題是DP的找零錢問題。

有幾種組合的算法,
由於可能會有重覆算到的關係,
所以要先加入最小的零錢(此題是1cent)進去,
看看各個值(小於等於30000)假設最後一枚硬幣為此零錢能用幾種方法(其實是dp[該值-加入的零錢價值]種)找出來,
接著再把次小的零錢(此題是5cents)放進去,
看看各個值(小於等於30000)假設最後一枚硬幣為此零錢能用幾種方法(其實是dp[該值-加入的零錢價值]種)找出來,
這樣以此類推到最大的零錢,
這樣我在算最後一個零錢是5cents的組合的時候,
我只會找出1cent跟5cents的組合,
不會找出配上10cents啦...25cents啦...或是50cents之類的組合。
等到我在算最後一個零錢是10cents的組合的時候,
我只會找出10cents跟5cents跟1cent的組合,
不會找出配上25cents啦...或是50cents之類的組合。
(如果看不懂以上內容,可以翻閱關於DP找零錢問題的教學文章。)

P.S. 這題要用long long Orz...

[C](0.020)

[UVa]147:Dollars

這題是DP的找零錢問題。

有幾種組合的算法,
由於可能會有重覆算到的關係,
所以要先加入最小的零錢(此題是5c)進去,
看看各個值(小於等於300.00)假設最後一枚硬幣為此零錢能用幾種方法(其實是dp[該值-加入的零錢價值]種)找出來,
接著再把次小的零錢(此題是10c)放進去,
看看各個值(小於等於300.00)假設最後一枚硬幣為此零錢能用幾種方法(其實是dp[該值-加入的零錢價值]種)找出來,
這樣以此類推到最大的零錢,
這樣我在算最後一個零錢是10c的組合的時候,
我只會找出5c跟10c的組合,
不會找出配上20c啦...50c啦...或是1元之類的組合。
等到我在算最後一個零錢是20c的組合的時候,
我只會找出5c跟10c跟20c的組合,
不會找出配上50c啦...或是1元之類的組合。
(如果看不懂以上內容,可以翻閱關於DP找零錢問題的教學文章。)

再來應該要建dp表,我們不可能用小數當索引值,
所以我們可以把該值乘上100在對應dp的那格為其答案,
但是浮點數乘法再配上轉成整數是避不開誤差的Orz...
因此請善用兩個整數來存值XD

[C](0.020)

[UVa]136:Ugly Numbers

這題要算第1500個Ugly Number是誰,
假設我現在要算第N項,
那麼我就找前面這N-1項中找出:
「乘2會大於第N-1項的那項」以及「乘3會大於第N-1項的那項」還有「乘5會大於第N-1項的那項」。
找出來後比較他們三個的大小,
最小的就是第N項。

接著要找N+1項,
我再從前N項中一樣找出:
「乘2會大於第N項的那項」以及「乘3會大於第N項的那項」還有「乘5會大於第N項的那項」。
那其實你再找「乘2會大於第N項的那項」,
你可以從「乘2會大於第N-1項的那項」開始往後搜,
就不用再從第0項開始搜。
找「乘3會大於第N項的那項」還有「乘5會大於第N項的那項」也可以比照辦理、以此類推。

這樣就可以很快速的找到第1500個Ugly Number了。^^

[C](0.020)

[UVa]102:Ecological Bin Packing

新站連結於http://knightzone.org/?p=1465