跳到主要內容

發表文章

目前顯示的是 十二月, 2008的文章

UVa 110 Meta-Loopless Sorts

相當有趣的一題....寫程式產生器
用自創的Modified-Permutation Algo ( ̄▽ ̄#)﹏﹏
第一次寫有點痛苦,過了幾天醞釀過想法後,寫起來很順很快就AC了
距離連號解題剩下最後一題107了..

UVa 109 SCUD Busters

解題策略典型的凸包 (Convex Hull ) 問題。我是採用 Graham's Scan 來解。作法可以參考維基條目 Graham's Scan,我就是照著條目裡的算法原封不動實做的。

本題要找出所有被飛彈摧毀的王國的國土面積總和。過程中一共有兩件事要解決,第一個要知道每個王國的國土面積,第二個要能判斷飛彈落點有沒有打中王國。

求國土面積,要先對王國內的所有的發電廠位置求凸包,然後由凸包去計算多邊形面積 (題目頁有給多邊形面積公式) 。 判斷飛彈落點是否落在國土內,也是以凸包為基礎,沿著凸包的每個邊判斷,如果飛彈落點都在邊的左側,那就表示打中了!
注意使用Graham's Scan 時要特別注意共線問題,尤其是起始點三點共線,例如 (0,0) (1,1) (2,2) (1,3) ,求出來的凸包應該是 (0,0) (2,2) (1,3)。
閒聊@2011.10.07
有點囉嗦的題目。2008年底我第一次解這題,因為過程有點曲折,所以花了好幾天才解出來,而且一直搞不定 std::sort( ) 的判斷函數,現在重寫一遍,感覺比較清爽一些了!

線性代數的世界作者 Dr. Strang 妙語如珠

"you can't add apples and oranges."「你不能把蘋果和橘子加在一起」
--談為什麼需要向量

The central porblem of linear algebra is to solve a system of equations.
線性代數的核心問題就是要解方程組!

It is also common sense: If you put on socks and then shoes, the first to be taken off are the ___.
常識也告訴我們:假如你先穿襪子再穿鞋,那麼脫的時候,首先該脫掉___。
--談為何AB的反矩陣是B-1A-1

Ax combines the columns of A while xTAT combines the rows of AT
Ax線性組合了A的諸行,而xTAT線性組合了AT的諸列。
--談為何(AB)T = BTAT
最近看Gilbert Strang寫的『Introduction to Linear Algebra』,Strang教授講法生動,不論是趣味的例子,或者是一句話直搗觀念核心,都常讓我拍案叫絕。
比起補習班名師的講義,研讀起來樂趣大多了。有機會再補上更多句子。

UVa 104 Arbitrage

解題策略Some Hints about uVA 104 
gits大大說得很清楚,我就不囉唆作法了。

閒聊苦思良久的UVa 104終於在 gits 幾乎手把手的帶領下寫出來了,了結了多天以來的心中懸念。XDDD稍微變化題,馬上就把我土法煉鋼學會的Floyd-Warshall 打回原型。連F-W要用二維還是三維陣列來建表都搞不清楚,唉,由這題可以知道我的DP/Graph有待磨練。

只有與問題面對面的對決,在測資跟Bug中打滾一番後,才能對Algorithm有更深刻的體會吧。這也是我寫ACM的目的與樂趣所在。不過...這題還是有點心虛阿.....orz 只能說敗給你了Modified Floyd-Warshall,還未夠班....總有一天我要能秒殺這題。


[ACM] Some hints about uva 104 (Modified Floyd-Warshall)

by gits
Original Thread http://online-judge.uva.es/board/viewtopic.php?t=7292

Well, I'll assume you understand what the problem asks. You have to find the shortest sequence that yelds a profit (not the one with the greatest profit!). If there is more then one sequence with the same length, any of those is valid.

Now, you can't just try with brute force (trying all combinations) because it'll be too slow and you'll get Time Limit Exceeded. However, there's a well known algorithm, Floyd-Warshall, which will find all the shortest paths between every node to the others in just O(n^3) time. You can find more info about F-W in the net. In my previous post I said how you have to change the general F-W algorithm to work for this particular problem...

As for floating point errors, most numbers representation isn't totally acurate; for instance, 0.1 is usually stored as 0.10000000000000001. After some operations, the error may influence the final result. Again, search th…