發表文章

目前顯示的是 3月, 2010的文章

UVa 587 There's treasure everywhere!

解題策略 給一張藏寶圖,記載著如何找到寶藏的指令,要算出最終寶藏的確切位置跟及離出發點的距離。這題是典型的模擬題,照著題目要求在平面座標上四處移動就行了。 我在兩個地方稍微傷了點腦筋 這題的input parsing不好做,或者說用c++ std IO有點麻煩。 operator>>切字串時不能選擇delimeter,用getline 來切也不能設定超過一個delimeter,可是這題偏偏就有兩個-逗點跟句點。我不想自己切,最後就把字串內的逗點跟句點都換成空白,這樣就能用上stringstream了。 浮點數誤差:這題送去ZJ後,我拿到一個WA結果如下 您的答案為: The treasure is located at (0.000,-0.000). 正確答案為: The treasure is located at (0.000,0.000). 怎麼會有負零呢!?  應該不是負零,是個非常非常小的負數,因為浮點數不夠精確才產生的誤差,加上一個EPS修正就行了。(不過事實上我對EPS的觀念還不是很懂..orz) 解決這兩項大概就沒問題了,AC get。

UVa 371 Ackermann function

解題策略 爛題目,首先光題目就誤導人了,這題不是Ackermann function ,是 3n+1 ,我還特別跑去確認 Ackermann function 的樣子。 然後兩個很爛的陷阱 (題目敘述沒明說) 1. 有可能 L>H。而最後輸出時必須交換成L<=H ,這跟 UVa 100 3n+1 不一樣。 2. 題目說範圍不會超過long的真正的意思是unsigned long,所以一般 int 會吃WA。 被細節弄得很火。 提供測資 ==input== 2000 3000 3000 2000 0 0 ==Output== Between 2000 and 3000, 2919 generates the longest sequence of 216 values. Between 2000 and 3000, 2919 generates the longest sequence of 216 values.

UVa 10125 Sumsets

解題策略 這題的解法很直接,要找d=a+b+c 用四層迴圈下去跑a,b,c,d就好了 XDDDD 我犯了幾個錯誤 要找最大符合d (意思是數列中可能出現好幾個符合要求的解),所以迴圈應該由最大元素往下找,第一個找到的解就是答案,我一開始由最小元素往上遞增尋找,拿了WA。 沒找到解就回傳0,殊不知0也有可能是解: 0 = -5 + 3 + 2,這裡也吃了一個WA,所以我後來改回傳 INT_MAX 作為無解。 這題有負值,所以 -5 = -10 + -2 + 7 ,這樣算一組合法的解。 是比較需要小心的地方。 官網論壇上的(a+b)=(d-c)法,方法複雜很多,卻沒有比較快。

UVa 357 Let Me Count The Ways

跟 147 、 674 同樣的題目,順便就吃下來啦 我發現IE會讓我的程式碼排版亂掉,真讓人困擾@_@

UVa 674 Coin Change

典型的DP題,沒有玩什麼花招.. Sagit's C++ 動態規劃 我想我就不需要多解釋了