IOI 2005 Mountains

不簡單的 segment tree 題..
麻煩在於 memory 不夠開整棵 segment tree

解決方法1: 離散化query, 感覺很難寫
解決方法2: 動態開樹

最後用了方法2, 可分為用 pointer 或 array 模擬.. 我用了後者, 應該分別不大

每個 node 記的資料為:
1] 是否整段都是同 slope
2] 總上升高度
3] 最高點的位置

就足夠了 (注意要用long long..)

IOI 2005 Mean Sequence

首先留意到 fix 了 s[1] = fix 了整條 sequence
然後觀察到, 合法的 sequence 的 s[1] 必定是一個連續區間的整數

做法: 先設合法的 upper bound 和 lower bound 為 U = m[1] 和 L = -INF

s[2] = 2*m[1] - s[1], 而且 s[2] <= m[2] 可得 2*m[1] - s[1] <= m[2], 即 L >= 2*m[1] - m[2]

如此類推, 從而縮窄 upper bound 和 lower bound
最後 number of mean sequences = upper bound - lower bound + 1

IOI 2005 Garden

對於任何長方形的放法, 總有方法用一條橫/直線把它們分開
做法就是窮舉那條分界線

先假設是打橫切
問題就變為在 row[x..y] 中要包住 k 支roses 的長方形的最小邊長

先 pre compute 長方形的邊 exactly 由 row x 到 row y 的情況
然後用兩條掃描線就可以了

總時間O(N³)

IOI 2004 Phidias

由於有「一刀切」的條件, 很容易想到用 dp

dp[x][y] = 分割一 x*y 長方形最小的浪費空間

於是有

• dp[x][y] = 0 if size[x][y] exists
  
• dp[x][y] = min{ dp[x-i][y] | 0<i<x , dp[x][y-j] | 0<j<y }
  

但係我猜想, 其實會唔會每一次切都係切一些 plate size 的長度, 即

dp[x][y] = min{ dp[x-height[i]][y], dp[x][y-width[i]] }

最後發現是可行的
不過未 prove 到..

IOI 2004 Farmer

一開始以為係 knapsack, 後來又發現可以分開拎

睇明題目後做法很簡單, 如果樹圈的數目 >= 可以拎的, 咁就睇下砌唔砌到剛剛好N (即答案是N或N-1)
如果唔夠, 就對餘下的線樹繼續做 knapsack..