UVa 113 - Power of Cryptography

終於遇見一個秒殺的題目了，UVa 113 - Power of Cryptography這題只是單純的數字開根號問題，只要用<math.h>裡的pow(double x, double y)即可完成。

程式碼

因為有使用到<math.h>的函式，在用gcc編譯時要多一個-lm的參數。

UVa 112 - Tree Summing

面對UVa 112 - Tree Summing這一題，一開始我的想法是要先將整顆樹建立起來，再從root拜訪到leaf。但再仔細研究一下，其實不需要建立樹，用遞迴的方式，很快就能解出。遞迴想法很容易，簡單述說如下：

1. 從root開始，將value傳給左右子節點。
2. 子節點將value與父節點傳來的value相加，再將value傳給自己的左右子節點。
3. 當節點為葉節點時，判斷總合是否相符。

程式碼

對我來講，一開始遇見的瓶頸在於怎樣處理題目給的輸入，但只要想通了就很容易，每一個節點都從左括號開始，右括號結束，抓著這一點，程式就可以開始寫了。這個題目還有一點要注意的是有可能會出現負值，所以記得要處理。

UVa 111 - History Grading

UVa 111 - History Grading題目不難，可以用LCS(Longest Common Subsequence)來解。唯一要注意的是題目所給的輸入資料。

程式碼

例如：
10
3 1 2 4 9 5 10 6 8 7
2 10 1 3 8 4 9 5 7 6

第一數字表示有十個事件。
接下來的每一行裡的數字則是指每一個事件在第幾個順序發生的：
event 1 -> order 3
event 2 -> order 1
event 3 -> order 2
以此類推，所以要先經過轉換後，事件的正確發生順序為2 3 1 4 6 8 10 9 5 7。
下一行經過轉換後，順序為3 1 4 6 8 10 9 5 7 2。
由LCS計算可得到最大的共同子序列長度為9。