HOJ生病惹QQ，因此我在這裡做了題目備份，請參考～
可以想成: 每經過一道切痕，蛋糕就可以多切出一塊了
所以，記錄下目前蛋糕上有幾道切痕，然後切的每一刀都經過所有目前的切痕
注意:
1. 在最後一刀切出邊界時也可以多切一塊蛋糕
2. 連續轉折時的第n刀切不到第n-1刀的切痕
code:
2016年1月13日 星期三
2016年1月12日 星期二
[FHC 2016 Qualification Round]The Price is Correct
首先可以發現以下性質:
如果Sum{[l,r]}<=P，那麼對於所有的l<=x<=r，Sum{[x,r]}也會<=P
如果Sum{[l,r]}>P，那麼對於所有的1<=x<=l(一個是數字一個是字母別搞混XD)，Sum{[x,r]}也會>P
如果Sum{[l,r]}<=P，那麼對於所有的l<=x<=r，Sum{[x,r]}也會<=P
如果Sum{[l,r]}>P，那麼對於所有的1<=x<=l(一個是數字一個是字母別搞混XD)，Sum{[x,r]}也會>P
因此我們可以考慮枚舉r，找出最小的l，那麼結尾為r的合法區間數量就是r-l+1了
可以考慮二分搜這個l，複雜度O(NlogN)
不過這裡提供單調對列O(N)的作法
仔細想想可以發現，最小的l在r慢慢增加時不會變小
因此可以用雙指標由左而右掃過去，右指標每增加1就把左指標往右移直到區間合法為止(有可能不需移動)
具體實作可以用queue<int>存前綴和
也不知道還有甚麼BUG，真正的結果要等比賽結束才會知道Orz
ps.最後四題全對耶真開心 :D
code:
可以考慮二分搜這個l，複雜度O(NlogN)
不過這裡提供單調對列O(N)的作法
仔細想想可以發現，最小的l在r慢慢增加時不會變小
因此可以用雙指標由左而右掃過去，右指標每增加1就把左指標往右移直到區間合法為止(有可能不需移動)
具體實作可以用queue<int>存前綴和
也不知道還有甚麼BUG，真正的結果要等比賽結束才會知道Orz
ps.最後四題全對耶真開心 :D
code:
2016年1月10日 星期日
[FHC 2016 Qualification Round]Text Editor
先備知識: Trie
首先可以把這N個字建成一棵Trie，其中根節點編號為0
然後我們可以構造一個樹型DP，DP[u][i]代表從根節點u的子樹中印出i個字所需要的最小花費
因此我們得到以下轉移方式(v_i代表u的第i個子節點)
定義f(v,i)為從u印出v子樹內的i個字所需最小花費，一般來講，f(v,i)=DP[v][i]+(i==0?0:2)
1. 當u恰好為n個單字的尾節點，可以視為u連向一個子節點v，只是f的定義稍微修改一下，f(v,0~n)=DP[v][0~n]
2. 當u有1個子節點，DP[u][i]=f(v,i)
3. 當u有2個子節點，DP[u][i]=min{f(v0,k)+f(v1,i-k), k=0~i}
4. 當u有多個子節點，可以考慮將子樹們兩個兩個合併，也就是先合併v0和v1，合出來的結果再和v2合，然後是跟v3......以此類推
因此，我們就可以根據子節點的資訊遞推出u的資訊了
答案出來了，就是DP[0][K]！
等等等，沒這麼簡單
題目範圍告訴你，這棵Trie最多會有100000個節點！
計算每個節點的DP值需要K^2的時間
這樣計算量就會多達10^12(要記的還有一個T呦~)
那怎麼辦呢？
可以注意到，上述情況2.可以再濃縮
因此，我們可以把很長很長的一條鏈濃縮成加邊權的邊，這樣f(v,i)就變成了DP[v][i]+(i==0?0:e.cost)了
濃縮過後的樹最多有2N個節點，複雜度O(N K^2)
可能有人想問，為甚麼是2N呢？
因為每加一個單字進來最多會讓Trie多一個分岔和一個葉節點嘛
證明完成(?)
所以，我們只要把這些單字建成一棵Trie，把這棵Trie重建成一個邊有權重的圖，在這張圖上作樹型DP，然後這個DP在遞推的時候要兩兩合併，就好(?)了
實作上有諸多細節要注意，尤其是重建圖的過程極為容易出錯，DP在合併的時候也容易混亂，也要注意維護單字節點的性質，至於剩下的Ø就沒什麼要注意的地方了
這個code是否還有其他BUG，真正結果要等比賽結束後才知道Orz
ps.最後四題全對耶真開心 :D
首先可以把這N個字建成一棵Trie，其中根節點編號為0
然後我們可以構造一個樹型DP，DP[u][i]代表從根節點u的子樹中印出i個字所需要的最小花費
因此我們得到以下轉移方式(v_i代表u的第i個子節點)
定義f(v,i)為從u印出v子樹內的i個字所需最小花費，一般來講，f(v,i)=DP[v][i]+(i==0?0:2)
1. 當u恰好為n個單字的尾節點，可以視為u連向一個子節點v，只是f的定義稍微修改一下，f(v,0~n)=DP[v][0~n]
2. 當u有1個子節點，DP[u][i]=f(v,i)
3. 當u有2個子節點，DP[u][i]=min{f(v0,k)+f(v1,i-k), k=0~i}
4. 當u有多個子節點，可以考慮將子樹們兩個兩個合併，也就是先合併v0和v1，合出來的結果再和v2合，然後是跟v3......以此類推
因此，我們就可以根據子節點的資訊遞推出u的資訊了
答案出來了，就是DP[0][K]！
等等等，沒這麼簡單
題目範圍告訴你，這棵Trie最多會有100000個節點！
計算每個節點的DP值需要K^2的時間
這樣計算量就會多達10^12(要記的還有一個T呦~)
那怎麼辦呢？
可以注意到，上述情況2.可以再濃縮
因此，我們可以把很長很長的一條鏈濃縮成加邊權的邊，這樣f(v,i)就變成了DP[v][i]+(i==0?0:e.cost)了
濃縮過後的樹最多有2N個節點，複雜度O(N K^2)
可能有人想問，為甚麼是2N呢？
因為每加一個單字進來最多會讓Trie多一個分岔和一個葉節點嘛
證明完成(?)
所以，我們只要把這些單字建成一棵Trie，把這棵Trie重建成一個邊有權重的圖，在這張圖上作樹型DP，然後這個DP在遞推的時候要兩兩合併，就好(?)了
實作上有諸多細節要注意，尤其是重建圖的過程極為容易出錯，DP在合併的時候也容易混亂，也要注意維護單字節點的性質，至於剩下的Ø就沒什麼要注意的地方了
這個code是否還有其他BUG，真正結果要等比賽結束後才知道Orz
ps.最後四題全對耶真開心 :D
(官方的O(N^2 K)解法單純多了可以去看一下www
code:
[FHC 2016 Qualification Round]High Security
首先可以把每一條橫向的空格都塞一個守衛
那麼甚麼情況下可以讓一個守衛擔任兩個守衛的工作呢?
大概就只有一條長度1的空格對面也是空格的情況了吧
這時候，我們可以把那佔據一個空格的守衛移出來，取代對面的守衛，絕對不會吃虧
實作的話可以先找出所有"X.X"，讓守衛站出來，然後把看守到的區域標記掉
接著，再掃一遍，把所有未看守的地區再補上一個守衛
不知道這樣的貪心法有沒有例外，真正的結果要等比賽結束才知道Orz
ps.最後四題全對耶真開心 :D
code:
那麼甚麼情況下可以讓一個守衛擔任兩個守衛的工作呢?
大概就只有一條長度1的空格對面也是空格的情況了吧
這時候，我們可以把那佔據一個空格的守衛移出來，取代對面的守衛，絕對不會吃虧
實作的話可以先找出所有"X.X"，讓守衛站出來，然後把看守到的區域標記掉
接著，再掃一遍，把所有未看守的地區再補上一個守衛
不知道這樣的貪心法有沒有例外，真正的結果要等比賽結束才知道Orz
ps.最後四題全對耶真開心 :D
code:
[FHC 2016 Qualification Round]Boomerang Constellations
我們可以枚舉兩線段的交點，然後算出這個點和其他點的距離
接著對這些距離排序
找出所有相同距離的點群，假設點群大小是n，那麼就多了n*(n-1)/2個boomerang constellation(我也不知道那是甚麼)了
加一加，當作是答案吧，真正結果等比賽結束才知道Orz
ps.最後四題全對耶真開心 :D
code:
接著對這些距離排序
找出所有相同距離的點群，假設點群大小是n，那麼就多了n*(n-1)/2個boomerang constellation(我也不知道那是甚麼)了
加一加，當作是答案吧，真正結果等比賽結束才知道Orz
ps.最後四題全對耶真開心 :D
code:
訂閱：
文章 (Atom)