跳到主要內容

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



留言

這個網誌中的熱門文章

讀書心得: 撒哈拉的故事

初拿起「撒哈拉的故事」時,我心中想著大概是本以沙漠為背景的美麗幻想般的愛情小說吧,有誰會真的費盡千辛萬苦跑去撒哈拉沙漠,在物質極為缺乏的環境下過著刻苦的生活呢? 沒想到這人就是三毛,只因為一個理由「我要認識沙漠」。

「撒哈拉的故事」是三毛與她的丈夫荷西在撒哈拉沙漠旅遊生活的紀實,生活在沙漠很糟糕,至少我看完最後一篇『白手成家』後認為實在很糟,不過在樂觀又開朗的三毛的筆下,撒哈拉沙漠化為一個有趣又不可思議的國度,說著一個又一個異國的故事。

如果不是三毛,我無法想像原來世界上還有這樣子的一群人,還有這等事情,你能想像沙哈拉威人三四年才洗一次澡嗎? 『觀浴記』裡三毛跑去看沙漠女人洗澡,要先用蒸氣蒸,再用石片刮下身上的泥沙,而且沙漠女人不只洗外面,還洗裡面,讓我看的哈哈大笑。『娃娃新娘』 裡則是三毛的一個沙哈拉威鄰居叫「姑卡」要出嫁了,可是她才十歲呀,結婚習俗更是特別,新郎去迎接新娘時,新娘拼命的抵抗,原來才在沙哈拉威人的觀念裡,打得激烈才叫做「好女人」,不掙扎事後會被取笑的。

沙哈拉威人很少受教育,思想沒有邏輯,通常講道理是講不通的。有次三毛要參加晚宴,遍尋不著自己的漂亮高跟鞋,反倒是鞋櫃上多了一雙破鞋子,原來高跟鞋被鄰居小女孩偷去穿了。事後三毛很生氣地跟她理論,小女孩竟然回嘴「生氣,生氣,你的鞋子在我家,我的鞋子還不是在你家,我比你還要氣。」聽見這種話真的是秀才遇到兵,有理講不清,還好三毛是個灑脫的人,笑笑就過去了。

事實上,生活在沙漠真的需要灑脫,老是計較小事肯定活不下去。除了講不清道理的沙拉哈威鄰居,沙漠也有許多危險,書中至少有兩次三毛差點在沙漠裡丟掉小命。但是每一篇故事裡,我都看見一位勇氣可嘉的中國女孩兒,她不屈不撓,以樂觀的心和智慧面對生活中的困難,盡情的玩,盡情的享受生活,像個瘋狂的孩子般,最後甚至布置了一個號稱撒哈拉沙漠裡最美麗的家,連記者都聞風專程前來拜訪,他們的物質生活雖不富裕,但是精神卻很富足。

說到三毛不能不提她的另一半荷西。三毛書裡這樣子描寫『荷西有一個很大的優點,任何三毛所做的事情,在別人看來也許是瘋狂的行為,在他看來卻是理所當然的』,所以當三毛說要去沙漠時,荷西早她兩個月,就先對著撒哈拉沙漠找工作去了,沙漠裡的瘋狂事也總有荷西的一份。人生能遇見這樣的他,既是羨慕,也是感動。

8. 使用視圖與相機鏡頭轉換,及 gluLookAt() - OpenGL FAQ

返回 OpenGL FAQ 目錄

8.010 OpenGL裡的相機鏡頭到底是怎麼運作的呢?  就目前的OpenGL來說,沒有相機鏡頭這種東西。更精確地講,相機永遠都位處於眼空間座標的原點 (0,0,0)。你的OpenGL應用程式為了假裝出移動相機的樣子,必須移動場景,對整個世界場景做相機鏡頭的逆空間轉換。

8.020 我要如何移動場景裡的眼睛或者相機鏡頭? 以相機鏡頭模型來說,OpenGL 並沒有提供介面去做這件事情。然而,GLU庫提供了gluLookAt()函數,傳入眼睛本身位置,眼睛瞄準點位置,以及朝上向量,都是世界空間坐標。這個函數依據參數計算出正確的相機逆空間轉換矩陣,並且乘上目前的矩陣。

8.030 我的相機鏡頭應該放在 ModelView 矩陣還是 Projection矩陣? GL_PROJECTION 矩陣只應該包含投影變換,它必須將眼空間坐標(eye space coordinates)轉換到裁切坐標(clip coordinates)。

GL_MODELVIEW矩陣呢,如其名,應該包含模型(modeling)與視圖(viewing)轉換,將物體空間坐標轉換成眼空間座標。所以請記住,永遠把相機鏡頭轉換放在GL_MODELVIEW矩陣,而不是GL_PROJECTION矩陣。

你可以把投影矩陣(projection matrix)想像成相機鏡頭的各種特性,像是視角的寬窄、焦距、用了魚眼鏡頭等等。而把模型視圖矩陣(model-view matrix)想成,你目前拿著相機站立的位置,及鏡頭指向的方向。

這份 The game dev FAQ 對這兩個矩陣說明得很不錯。

去讀讀 Steve Baker 的文章「濫用投影」(備用連結) 吧。此篇文章寫得很好,值得推薦。它曾經幫助過許多OpenGL新手程式員。

8.040 我該如何實現鏡頭變焦 (Zoom) 的操作? 簡單的做法是對 ModelView矩陣做等比縮放(uniform scale)。但是當模型放得太大時,通常會導致模型被近平面及遠平面裁切掉。一個比較好的做法是限縮投影矩陣裡view volume的寬與高。舉例來說,你的程式對應使用者的輸入,儲存了一個縮放參數值。當縮放值是1.0 時不變焦。縮放值變大就縮小視角,結果模型看起來就放大了。縮放值變小時就反過來做。程式碼範例看起來可能像這樣子:
/* 如果…

UVa 10018 Reverse and Add

解題策略這題是這樣的,要把輸入的數字反轉,例如1357變成7531,然後與原數相加。直到這個數字變成迴文(palindrome)為止,像是1357+7531=8888,8888就是一個迴文。本題只需要按照著要求計算即可,唯一比較技巧是反轉一個整數 int:reverse()
注意需要注意變數範圍:至少要 unsigned long 才能容納題目的數字範圍。而printf()、scanf() 與 unsigned long 打交道的代號是%lu。

爭議點這題有個爭議點是第一個數字到底需不需要判斷回文,舉個例子:
輸入2,那麼該輸出0 2或者1 4?舊版的UVa測資要求必須要輸出1 4,這有些不合常理,新版則是把爭議性測資都拿掉了,所以兩種寫法都能AC。但是在zerojudge.tw上就必須輸出1 4才行。

PS.這題我不小心把某個unsigned long打成int,抓了好久的bug。