晚上的 training
those 因為有事未能參與，所以由他來選題
然而其中一題未能讀入，便隨意選一道他做過的 geometry 題目取替之
（後來被這題玩殘了...）
training 暫時草草速記如下，細節後補：
題A Adventure of Super Mario
shortest path
做兩遍 shortest path
- 用 floyd 求出 all-pair-shotest path，避過中間節點是 castle 的情況
- 將每個 node（地點）分為 K 層，表示使用過 K 次 super-running
題B PKU 3429 metry with a Ruler
高精度 + 2D geom
被玩殘了...又要高精度又要分數 ⇒ 只好用 Java
編程期間出現很多 compile error，「夾硬」加了 static modifier 水過
（發現自己對 Java 的理解只有 1130 的程度，有待進修 orz...）
首次為 ACM 題寫 Java 的 Inner class... 而且還是兩個
是 Point2D of Fraction of BigInteger!!
leo有更巧妙的方法 ─ 利用內建 BigDecimal 設定 precision 為 400 個小數位
gagguy 用 fraction of long long 通過了... 可惡！
題C PKU 3493 Chessboard Puzzle
min-cost flow／dp／greedy（?）
解1: 依我來看，跟 Dual Core CPU 如出一轍，同樣是 binary labelling 問題
只是這題更 general，要處理 -ve cost
所以... 不能直接應用 minimum cut
不過透過 min-cost flow 就能實現 minimum cost cut（這個 cut 可以 -ve）
為此算法寫了一篇 blog entry
──可是這樣求出的 割 (Cut) 是否必然對應一個 bicoloring？嗯... 有水過的嫌疑
解2: 超超用的是 壓縮DP，時間複雜度 O(2M MN)
我們 row-by-row，col-by-col 地給每一格進行黑／白染色
至第 [i, j] 格時，一共有 2M 種 configuration
每種 state 的更新只需要考慮剛才填上的 M 格
前幾天 AC 了，發覺很容易 code
詳情可以參考 gagguy 的 blog entry
解3: 看 Discuss 發現有人用 貪心算法？
題D PKU 3221 Diamond Puzzle
bfs
本應可以 ~5 min KO...
可沒看清題目... 以為 Figure 2, 3 都是合法終結狀態... 卡了好幾分鐘...
對於寫出來的代碼感到非常滿意 =v=
題E ICPC 4270 Discret Square Roots
number theory（算是吧？）
至 training 剩下 30 min
超超笑著道出「頹做」二字後
我 跟 chin 和 leo 往這方向想...
加上在 「y 是 solution, n-y 也是 solution ⇒ 只需考慮 ≥ n/2」的提示
還是想不出來，但後來發現其實跟超超的答案相差不遠矣
（剛才 AC 的 code 裏面，跟超超的 solution 有些不同，但背後道理一樣）
解：O(#因數 × sqrt(M)) 窮舉法，可以參考 此 blog entry
題F (後補)
simulation
是往年 summer 殘餘的 individual training 題目
印象中 joe 也要在 training 過後一小段時間寫好
我在是次 trainng 把這題 priority 放到最低，直接略過
沒有留言:
發佈留言