2011年2月25日 星期五
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
2010年12月6日 星期一
TIOJ 1516 Problem F. HALLO ☆ GAME [Binary Tree]
3 91671 poao899 18388K 2197MS G++ 3.18K 2010-12-07 01:07:12 .
因為要正名(?)所以就不用Segment Tree這個名詞了XD
其實我覺得叫做Segment Tree也沒什麼不好，這種東西這麼常用總該有個名字吧XD
而且為什麼歪果仁講的就是正確的大陸人講就是亂講(?)
或許我跟這些都不熟上面只是我一廂情願罷了XD
反正以後這種東西在我的部落格上都會紀錄為Binary Tree?
這題操作很多，不過不難寫。
只需要有三個操作：
區間覆蓋、區間詢問、單點求值就好了。
不過這題還是值得推薦的?
因為它有用到存左邊右邊中間再meld的概念還有大陸學生口中的延遲標記(或sb標記?)
還有有些操作不能純用樹來作XD
仔細想了一下，似乎一棵純粹的Splay Tree可以支援所有操作？
因為那個旋轉說實話我搞了一個禮拜xD
因為要正名(?)所以就不用Segment Tree這個名詞了XD
其實我覺得叫做Segment Tree也沒什麼不好，這種東西這麼常用總該有個名字吧XD
而且為什麼歪果仁講的就是正確的大陸人講就是亂講(?)
或許我跟這些都不熟上面只是我一廂情願罷了XD
反正以後這種東西在我的部落格上都會紀錄為Binary Tree?
這題操作很多，不過不難寫。
只需要有三個操作：
區間覆蓋、區間詢問、單點求值就好了。
不過這題還是值得推薦的?
因為它有用到存左邊右邊中間再meld的概念還有大陸學生口中的延遲標記(或sb標記?)
還有有些操作不能純用樹來作XD
仔細想了一下，似乎一棵純粹的Splay Tree可以支援所有操作？
因為那個旋轉說實話我搞了一個禮拜xD
2010年9月12日 星期日
[文件] about Miller-Rabin & Pollard-ρ
※前言
關於質數，台灣競賽方面似乎比較少提及，頂多學學篩法、根號檢驗法而已。
草提一下這兩個算法：
>>埃氏篩法：
//什麼毛啦顏色傳上來變得醜死了
O(N ln N)時間複雜度、O(N)記憶體，求出1~N所有的質數。
一些優化：
1. 僅 型如 6n ± 1 者有可能是質數（2 | 6n+2、3 | 6n+3、2 | 6n+4）
其實這個優化加下去已經可以達到一定速度了。
2. 用位元壓縮，記憶體僅需要(N/32)個int（排掉偶數可以剩下N/64，但個人認為沒必要）
一些應用：
1. 求出質因數個數：
![]()
![]()
值得注意的是I = i*i要改成I = i+i才行。
2. 求Φ(n)：
即找出1~n-1中有幾個跟n互質的數。
因為有Φ(n) = n * Π(1 - (1/p)) 對每個質數p | n，所以可以用篩法作到。
// 另外，線性篩法我不會，所以省略...
相關題目：
TIOJ：1036、1260、1353、1514、1535
ACM：294
>>根號檢驗法：
O(√n)檢驗一個數是否為質數。
一些應用：
1. 質因數分解：
每次除到不能除，若<= √p都試完了剩下的那個一定是質數。
相關題目：
ACM：583
反正目前為止的台灣競賽幾乎都只注重以上兩者，相關題目也十分罕見（目前為止沒見過）
但是對於密碼學而言，以上算法都還不能讓人滿意。
>>Miller-Rabin：
一個能期望極快的判斷質數作法。
算法核心：
引理一：若p是質數，則a(p-1) mod p = 1 （費瑪小定理）
引理二：若x2 mod p = 1（其中x<p、p是質數）那x = p-1或x = 1 （證明就是用(x+1)(x-1) = kp）
然後若我們要測定n是否能通過以a為底的米勒拉賓測試
先把n-1 = 2r * d ， 其中d是奇數 也就是求出n-1最高含2的幾次方
那麼 如果 a (2r * d) mod n 不是1 就一定是合數 （引理一）
就繼續下去a (2(r-1) * d) mod n 得是n-1 或1（引理二）
如果是n-1即是通過檢測，如果是1就繼續遞迴直到 ad mod n
對int範圍的數字，只需要測 a = 2, 7, 61
對10^16內的數字，只需要測 a = 2, 3, 5, 7, 11, 13, 17, 61, 24251
所以只需要寫一個大數次方 + 主程序大概 20~30 行很OK。
虛擬碼就不附了，上次寫得爛爛的。
進一步可以參照Matrix67的相關文章。
>>Pollard-ρ：
還在學...
關於質數，台灣競賽方面似乎比較少提及，頂多學學篩法、根號檢驗法而已。
草提一下這兩個算法：
>>埃氏篩法：
//什麼毛啦顏色傳上來變得醜死了
O(N ln N)時間複雜度、O(N)記憶體，求出1~N所有的質數。
一些優化：
1. 僅 型如 6n ± 1 者有可能是質數（2 | 6n+2、3 | 6n+3、2 | 6n+4）
其實這個優化加下去已經可以達到一定速度了。
2. 用位元壓縮，記憶體僅需要(N/32)個int（排掉偶數可以剩下N/64，但個人認為沒必要）
一些應用：
1. 求出質因數個數：
2. 求Φ(n)：
即找出1~n-1中有幾個跟n互質的數。
因為有Φ(n) = n * Π(1 - (1/p)) 對每個質數p | n，所以可以用篩法作到。
// 另外，線性篩法我不會，所以省略...
相關題目：
TIOJ：1036、1260、1353、1514、1535
ACM：294
>>根號檢驗法：
O(√n)檢驗一個數是否為質數。
一些應用：
1. 質因數分解：
每次除到不能除，若<= √p都試完了剩下的那個一定是質數。
相關題目：
ACM：583
反正目前為止的台灣競賽幾乎都只注重以上兩者，相關題目也十分罕見（目前為止沒見過）
但是對於密碼學而言，以上算法都還不能讓人滿意。
>>Miller-Rabin：
一個能期望極快的判斷質數作法。
算法核心：
引理一：若p是質數，則a(p-1) mod p = 1 （費瑪小定理）
引理二：若x2 mod p = 1（其中x<p、p是質數）那x = p-1或x = 1 （證明就是用(x+1)(x-1) = kp）
然後若我們要測定n是否能通過以a為底的米勒拉賓測試
先把n-1 = 2r * d ， 其中d是奇數 也就是求出n-1最高含2的幾次方
那麼 如果 a (2r * d) mod n 不是1 就一定是合數 （引理一）
就繼續下去a (2(r-1) * d) mod n 得是n-1 或1（引理二）
如果是n-1即是通過檢測，如果是1就繼續遞迴直到 ad mod n
對int範圍的數字，只需要測 a = 2, 7, 61
對10^16內的數字，只需要測 a = 2, 3, 5, 7, 11, 13, 17, 61, 24251
所以只需要寫一個大數次方 + 主程序大概 20~30 行很OK。
虛擬碼就不附了，上次寫得爛爛的。
進一步可以參照Matrix67的相關文章。
>>Pollard-ρ：
還在學...
2010年9月10日 星期五
PKU 1286 Necklace of Beads [Pólya]
poao899 1286 Accepted 404K 0MS G++ 416B 2010-09-10 23:20:57 .
Pólya超經典題。
長為n<24的項鍊，三種顏色定義不同構為旋轉 翻轉<b>擇一</b>後不一樣者。
就套Pólya：
( Σ(i=1...n)(3^gcd(i, n)) + 翻轉 ) / 2n
反正學過真的就水過。
Pólya超經典題。
長為n<24的項鍊，三種顏色定義不同構為旋轉 翻轉<b>擇一</b>後不一樣者。
就套Pólya：
( Σ(i=1...n)(3^gcd(i, n)) + 翻轉 ) / 2n
反正學過真的就水過。
訂閱：
文章 (Atom)