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實作，複雜度差不多。

TIOJ 題目分類

亂做的 不要太相信裡面的難度(?)


http://poao.infor.org/TIOJ.xls








說真的發現好多經典題目都沒寫過(zz