43059 0906 - Power Grid poao899 Accepted C++ 0.600 2011-03-23 14:12:06 .
.
要仔細看清楚題目啊orz...
1. 每個邊都要走過至少一遍
2. 不能繞路
3. 城市只會出現在葉子
4. 點心數目範圍
考量某個節點：
每個子樹邊權和依序為A1 A2 A3 A4...An
每個子樹有點心的點數依序為B1 B2 B3 B4...Bn
那假設他走訪順序是s1 s2 s3 s4 ... sn
那麼浪費掉的點心是2 * [ As1 * ( Bs2+...+Bsn ) + As2 * ( Bs3+...+Bsn ) + ... + As(n-1) * ( 0 ) ]
先不要看這個式子，我們先把題目特殊化，假設所有的B都=1
那麼很逗趣的，浪費點心的式子變成：
2 * [ As1 * (n-1) + As2 * (n-2) + ... + As(n-1) * (0) ]
很明顯可以用排序不等式證明，A越小的要越先走。那麼我們回到一般化的問題：
如何使之極小化呢？想像把一個邊權和Ak 點數Bk的子樹拆成Bk個子樹 每個的A=(Ak/Bk)、這樣每個新子樹的B都會是1了
那麼利用上述結論會發現，Ak/Bk越小的子樹應該先走。顯然是一個正確的貪心策略
值得一提的是假設沒有上述性質2. 就可能出現先走一棵走一半之類的，就不知道怎做了orz
2011年3月22日 星期二
2011年2月25日 星期五
94全國賽 6. 下棋問題
數據範圍N到5000，但是記憶體卻只給到約略N^2/2。
首先因為我想不到在線(Inline)的作法，故從離線(Offline)開始想起。
當沒有任何阻隔時，任兩個棋子A, B都可以形成一個矩形。
這個矩形出現的時間是max(A, B)，也就是兩個棋子都被下下去始，直到他們中間有其他棋子出現。
也就是如果我們可以枚舉每對棋子，並且快速地算出這個矩形被破壞的時間，這題便可以做了！
而他被破壞的時間就是這個矩形區間中最早放下去的棋子。
所以變成每次查詢一個矩形，問矩形內最早放下的棋子。
這很明顯就是二維的RMQ問題！而二維RMQ可以用Sparse Table作到每次查詢O(lg^2 N)
所以我們就得到一個算法了：
**枚舉每個矩形，查詢那個區間最早被放下的棋子。
**之後我們會得到N(N-1)/2個區間 每個區間代表這個該個矩形的生命週期。
**之後對這些區間進行排序，線性掃過後可以求出每一個時間點場上"存活"的矩形有幾個。
這樣總複雜度會是O(N^2 lg^2 N)，但是記憶體非常不理想地是(N^2 lg^2 N)，
除了執行速度太慢之外，記憶體空間也不足。
以此，需要更優化此算法。
也就是要在O(N^2)以內的複雜度內求出每個矩形的生命週期。
我們想到了分而治之法。(Divide & Conquer)
首先沿中線將棋盤分為左右兩塊，左塊內的矩形及右塊內的矩形可以透過遞歸做出。
現在我們要處理的就是跨越中間線的矩形。
如上圖所示，該矩形會被中線切割為藍色塊跟紅色塊。
該矩形的死期(?)理當為Min(藍色塊內最早被放下的點, 紅色塊內最早被放下的點)
而該怎麼求出每一個點對的每個色塊呢？
我們繼續觀察下去，觀察P對B這個矩形。
我們會發現他在中間線左邊那個紫色塊完全把上圖藍色塊包含了。
也就是其實我們可以用O(點數)求出左邊每個以P為左下角的色塊 內最早被放下的點，
就只要沿著Y軸遞增掃下去即可。
如此每個矩形只會被中線切一次，故總計算量實際上是O(N^2)，也就是矩形數量。
至於記憶體(內存)不夠的問題呢，會發現只要改一下計算順序，記憶體總共只需要N的常數倍，顯然夠用。
以上。
=====題外話：=====
這題是在94年全國賽的難題之一，
最近幾年全國賽無論是測試數據強度或是題目難度感覺都有點比不上以往...
當年賽後，有選手提出了這題的在線作法
也就是每次加入一個點，算出這個點增加了幾個、破壞了幾個
OIBH 2006 模擬試題3 prob 3 情书抄写员
http://mail.bashu.cn:8080/BSoiOnline/showproblem?problem_id=1629
顯而易見可以得到第n天的情書數量有F(n) = F(n-1) + k * F(n-2)
先講結論，gcd(F(a), F(b)) = F(gcd(a, b))
以下證明 by willyliu
Lemma 1 : gcd(F(n), k) = 1
proof :
gcd(F(n), k)
= gcd(F(n-1) +F(n-2)k, k)
= gcd(F(n-1), k)
= ... = 1
Lemma 2 : gcd(F(n), F(n+1)) = 1
proof :
gcd(F(n), F(n+1))
= gcd(F(n), F(n) + F(n-1)k)
= gcd(F(n), F(n-1)) ∵Lemma 1
= ... = 1
Lemma 3 : F(a+b) = F(a)F(b+1) + F(a-1)F(b)k
proof :
F(a+b)
= F(a+b-1) + F(a+b-2)k
Induction on b,
= ( F(a)F(b) + F(a-1)F(b-1)k ) + ( F(a)F(b-1) + F(a-1)F(b-2)k )k
= F(a) * ( F(b) + F(b-1)k ) + F(a-1) * ( F(b-1) + F(b-2)k )k
= F(a)F(b+1) + F(a-1)F(b)k
Theorem : gcd(F(a), F(b)) = F(gcd(a, b))
proof :
WLDG a ≧ b,
gcd( F(a), F(b) )
= gcd( F(a-b + b), F(b) )
= gcd( F(a-b)F(b+1) + F(a-b-1)F(b), F(b) ) ∵Lemma 3
= gcd( F(a-b)F(b+1), F(b) )
= gcd( F(a-b), F(b) ) ∵Lemma 2
= gcd( F(a mod b), F(b) )
= F( gcd(a, b) ) Q.E.D.
NOI2010 航空管制
先附個題目連結，
http://hi.baidu.com/%D2%DD%C3%F7%BE%A8%C8%CB/blog/item/4bb3383d07f175cf7d1e71d5.html
第一部分很簡單，就把所有限制建構成一個DAG，
把頂點依照"最遲起飛時間"排序，由小到大儘量滿足即可。
由於保證有解，所以這部分相信不是大問題。複雜度O(N+M)
第二部分先講一下我首先想到的想法：
如果該架飛機的起飛時間在[1, K]之間，然後我們二分搜K顯然可以得到答案。
二分搜之後我們可以變成把該節點的最遲起飛時間變成K，然後做一次第一題檢查是否有解
對每個的複雜度是O((N+M)lgN)，總複雜度約O(NMlgN)
而且其實二分搜的範圍很小，應該運行速度不會太慢。
如果有把第一題弄成一個function實作難度會降低很多。
另外附一個剛才在網路上找到的不錯思路：
http://yzm-blog.appspot.com/2010/08/8/NOI-2010.html
用Heap實作，複雜度差不多。
2011年1月10日 星期一
2010年12月7日 星期二
Practice : Asia Beijing 2008 / 2009
北京賽區。據說當年五題+不錯的Penalty就可以拿到金獎 雖然不知道金獎怎麼定義XDD .
pA 給你一張有向圖(V=50 E=4000)和K，問至少要拔幾個點才使得1->N的最短路大於等於K
(邊權皆為1、1->N沒有直接連邊)
用最大流想法：增廣到該次最短路長度>=K就結束，輸出目前源點流量 不過依然WA
pB給你N和K，兩人輪流取石頭，第一個人第一次只能拿1~N-1顆、
以後每個人每次拿的數量不能超過上衣個人K倍，問先手必勝的第一步？
沒想法，不過應該是經典題
pC給你一張NxM圖片，問你有幾個矩形框在最上層？
模擬，但是注意回字型。
pD有一個龍捲風路徑是一條射線，給你他的速度，還有一個人在兩點之間等速往復運動，問龍捲風到人的最近距離？
沒想法
pE給一張無向有權完全圖，你要輸出一組M個點的生成樹且邊權和/點權和最小，且點排好後的字典序最小。
爆搜，注意一下精度問題。
pF給一張NxM網格(N=100,M=10000)，橫向(M方向)每條路徑都有兩個權重，v跟k。
從最底下任意一點開始，到最上面任意一點。只能往上或左右走，且走過路徑不能再走，
且每層(依照N分層)走過的路徑sum k要小於給定的K，求出整條路徑sum v的最大值。
DP，每層轉移需要Deque，不過我還在WAorz
pG給你很多區間(N=100000)代表婚禮，牧師必須選擇一段連續段來進行證婚。
這段必須要大於區間大小的一半，且牧師只有一個人不能分身，問有沒有可能替所有婚禮證婚？
Greedy (by worm)，還不會
pH給你一個序列ar(長度=100000)，問有幾個三數對A,B,C符合位置A<B<C且ar[B]介於ar[A]和ar[C]之間。
頗裸的Binary Indexed Tree
pI, pJ沒看題目
總體而言打得很失敗orz
不過要感謝suhorng, jurrasickill
Beijing (China)
pA 給你一張有向圖(V=50 E=4000)和K，問至少要拔幾個點才使得1->N的最短路大於等於K
(邊權皆為1、1->N沒有直接連邊)
用最大流想法：增廣到該次最短路長度>=K就結束，輸出目前源點流量 不過依然WA
pB給你N和K，兩人輪流取石頭，第一個人第一次只能拿1~N-1顆、
以後每個人每次拿的數量不能超過上衣個人K倍，問先手必勝的第一步？
沒想法，不過應該是經典題
pC給你一張NxM圖片，問你有幾個矩形框在最上層？
模擬，但是注意回字型。
pD有一個龍捲風路徑是一條射線，給你他的速度，還有一個人在兩點之間等速往復運動，問龍捲風到人的最近距離？
沒想法
pE給一張無向有權完全圖，你要輸出一組M個點的生成樹且邊權和/點權和最小，且點排好後的字典序最小。
爆搜，注意一下精度問題。
pF給一張NxM網格(N=100,M=10000)，橫向(M方向)每條路徑都有兩個權重，v跟k。
從最底下任意一點開始，到最上面任意一點。只能往上或左右走，且走過路徑不能再走，
且每層(依照N分層)走過的路徑sum k要小於給定的K，求出整條路徑sum v的最大值。
DP，每層轉移需要Deque，不過我還在WAorz
pG給你很多區間(N=100000)代表婚禮，牧師必須選擇一段連續段來進行證婚。
這段必須要大於區間大小的一半，且牧師只有一個人不能分身，問有沒有可能替所有婚禮證婚？
Greedy (by worm)，還不會
pH給你一個序列ar(長度=100000)，問有幾個三數對A,B,C符合位置A<B<C且ar[B]介於ar[A]和ar[C]之間。
頗裸的Binary Indexed Tree
pI, pJ沒看題目
總體而言打得很失敗orz
不過要感謝suhorng, jurrasickill
訂閱：
文章 (Atom)