2009年4月28日 星期二

UVa 116 Unidirectional TSP

簡化版旅行推銷員問題,用DP解

這題我的醒悟就是,用演算法不要太死腦筋
因為這題有一個機歪點,就是如果有多條權重相同的最短路徑,要輸出字典順序最小的那一條。

如果從起點往後DP,那麼字典順序很難解
如果從終點DP回來起點,那麼字典順序自然而然解決了。

瞭解演算法以後,果然還是要靈活使用才行。


附上測資
應該足夠應付各種狀況了

2009年4月21日 星期二

UVa 107 The Cat in the Hat

解題策略

這題的關鍵其實就是找N (廢話...),每隻貓都可以從帽子中變出N隻小貓,小貓的高度是 1/(N+1) ,所以有N一切的謎底就都解開了。我的做法也很簡單,就是用個for迴圈去代 n ,然後比對最後工作的小貓數量,直到符合為止。

一個可能蠻有用的測資
483736625 481890304
0 0
答案是 615441 1931252289,找出來的N應該是784。

注意

官網論壇上面很多亂七八糟的測資,像是(3 1), (5 1), (7 1) 等等除不盡的測資,請 完 全 不 要 管 這些東西。所有合法測資都是剛剛好整除的整數,貓的初始高度也一定是某數的完全次方。

閒聊

開心,終於達成100~113連號答題,整排都是綠色的AC看起來就很爽。雖然不是用很數學的方式,但是這個解法是我自己想出來的,相當有成就感。

2009年4月20日 星期一

UVa 10196 Check The Check

有趣,但是很繁瑣的題目。
我還花了很長的時間想要怎麼把check的程式簡化縮短,後來發現沒什麼好辦法,就直接爆破了。

1. 用12*12的棋盤可以省掉很多邊界檢查。
2. 從king出發去找敵棋,比較快;用其他棋子去找king,比較慢。

0.000秒AC \(>﹏<)/

2009年4月7日 星期二

UVa 10267 Graphical Editor

好有趣的題目。
不過因為參考網路上某份code,實做錯誤的BFS,導致好幾次TE= =a。
話說這好像是我第一次親手實做BFS ?
自己寫了一個Queue,看起來速度很快。
最後AC 0.020秒 Ranking 51

有兩點注意
1. V的y1,y2,測資有可能y1>y2。H也一樣。
2. fillRegion若目標顏色跟原色相同,那就不用做了。


2009年4月2日 星期四

UVa 10142 Australian Voting

弄了我三天的題目,深深覺得自己還未夠班。
Ranking 136, 但是Run Time相當不理想: 0.760。不知道要怎麼壓到0.2秒以下。

提供下面這份測資,非常關鍵,我通過這份測資後就一次AC了。
來源:http://online-judge.uva.es/board/viewtopic.php?p=49650#49650


7

2
i am jalal
he is Hasan
1 2
2 1


3
L
P
M
1 2 3
1 3 2
2 3 1
2 1 3
1 3 2
2 3 1

6
A
B
C
D
E
F
2 1 6 5 3 4
6 3 2 5 4 1
5 2 6 1 3 4
3 6 1 5 2 4
1 2 4 6 3 5
3 2 5 6 1 4
5 6 2 4 3 1
5 3 1 4 2 6
2 4 5 6 3 1
2 5 3 4 6 1

4
jalal
hasan
bijon
saiket
1 2 3 4
3 1 2 4
1 2 3 4
2 1 3 4
3 1 2 4
4 3 1 3

3
John Doe
Jane Smith
Sirhan Sirhan
1 2 3
2 1 3
2 3 1
1 2 3
3 1 2

3
John Doe
Jane Smith
Sirhan Sirhan
1 2 3
2 1 3
2 3 1
1 2 3
3 1 2

4
jalal
hasan
bijon
saiket
1 2 3 4
2 1 3 4
1 2 3 4
2 1 3 4
3 1 2 4
4 2 1 3



正解

i am jalal
he is Hasan

L
P

B

jalal
bijon

John Doe

John Doe

jalal
hasan