亂做的 不要太相信裡面的難度(?)
http://poao.infor.org/TIOJ.xls
說真的發現好多經典題目都沒寫過(zz
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
反正學過真的就水過。
2010年9月5日 星期日
NTUJ 1021 Highway Patrol
36916 1021 - Highway Patrol poao899 Accepted C++ 0.030 2010-09-05 19:41:21 .
好題欸@@
題意：
一個大都會內有N座城市(<=100)，有M條單行道(<=1,000)
每個單行道可以用一個數組(u, v, p, s, x)表示，表示有一條道路從u往v，
如果要派軍隊巡邏要花費p的代價、裝監視器要s的代價 (0 <= p,s <= 1,000,000)
x代表這條道路的重要性，1表示極為重要，不可以用監視器。
因為這個大都會治安很差，每條道路都必須選擇上述兩種方式之一維持治安品質。
但是，每個軍隊巡邏完了要能回到自己的城市休息，所以我們希望每個城市出分枝度 == 入分枝度。
而且，市民們也不希望看到一個全部僅由監視器戍守的城市，所以至少得有一條路是巡邏。
問最少需要花多少錢滿足以上要求。
Input:
第一行有一個數字T表示測資筆數(T <= 70)
每筆測資第一行是N, M，接下來M行每行有五個數字u, v, p, s, x。
Output:
第i筆測資輸出Case [i]: [cost]
[i]表示測資筆數，[cost]表示你所花的錢，無解請用"impossible取代"。
Sample input:
3
4 5
1 2 10 25 0
2 3 10 5 0
3 1 10 5 0
2 4 10 5 0
4 3 30 5 0
4 5
1 2 10 25 0
2 3 10 5 0
3 1 10 5 0
2 4 10 5 0
4 3 30 5 1
2 1
1 2 10 25 1
Sample output:
Case 1: 40
Case 2: 65
Case 3: impossible
=================Solution================
簡單的先捏一下，flow。
因為把這個問題轉化一下可以想到，你可以假設一開始全部監視，那這樣總cost是Σ(si)。
然後每把一個邊變成巡邏的cost會是(pi-si)。
而且最後答案一定巡邏的邊會形成好幾個環。
所以就一直找全局最小環加上去，加到那個環是正的為止。
進一步會發現，變成有負圈的圖形每次尋找全局最小簡單環。不過很可惜這個題目沒多項式作法。
所以要換一個想法。
可以先把p便宜的邊先巡邏、s便宜的邊先監視。
然後建起來可替換邊以及他的替換代價，容量都是1
然後對每個點，檢查有幾個巡邏出發/幾個巡邏回來 其中的相差就建到S/E，cost=0，容量是差。
作一次帶權flow，算出答案...
然後還要檢查答案是否合法：如果==Σ(si)那就表示你一個邊都沒取
所以Warshall一次，找出最小圈輸出
好題欸@@
題意：
一個大都會內有N座城市(<=100)，有M條單行道(<=1,000)
每個單行道可以用一個數組(u, v, p, s, x)表示，表示有一條道路從u往v，
如果要派軍隊巡邏要花費p的代價、裝監視器要s的代價 (0 <= p,s <= 1,000,000)
x代表這條道路的重要性，1表示極為重要，不可以用監視器。
因為這個大都會治安很差，每條道路都必須選擇上述兩種方式之一維持治安品質。
但是，每個軍隊巡邏完了要能回到自己的城市休息，所以我們希望每個城市出分枝度 == 入分枝度。
而且，市民們也不希望看到一個全部僅由監視器戍守的城市，所以至少得有一條路是巡邏。
問最少需要花多少錢滿足以上要求。
Input:
第一行有一個數字T表示測資筆數(T <= 70)
每筆測資第一行是N, M，接下來M行每行有五個數字u, v, p, s, x。
Output:
第i筆測資輸出Case [i]: [cost]
[i]表示測資筆數，[cost]表示你所花的錢，無解請用"impossible取代"。
Sample input:
3
4 5
1 2 10 25 0
2 3 10 5 0
3 1 10 5 0
2 4 10 5 0
4 3 30 5 0
4 5
1 2 10 25 0
2 3 10 5 0
3 1 10 5 0
2 4 10 5 0
4 3 30 5 1
2 1
1 2 10 25 1
Sample output:
Case 1: 40
Case 2: 65
Case 3: impossible
=================Solution================
簡單的先捏一下，flow。
因為把這個問題轉化一下可以想到，你可以假設一開始全部監視，那這樣總cost是Σ(si)。
然後每把一個邊變成巡邏的cost會是(pi-si)。
而且最後答案一定巡邏的邊會形成好幾個環。
所以就一直找全局最小環加上去，加到那個環是正的為止。
進一步會發現，變成有負圈的圖形每次尋找全局最小簡單環。不過很可惜這個題目沒多項式作法。
所以要換一個想法。
可以先把p便宜的邊先巡邏、s便宜的邊先監視。
然後建起來可替換邊以及他的替換代價，容量都是1
然後對每個點，檢查有幾個巡邏出發/幾個巡邏回來 其中的相差就建到S/E，cost=0，容量是差。
作一次帶權flow，算出答案...
然後還要檢查答案是否合法：如果==Σ(si)那就表示你一個邊都沒取
所以Warshall一次，找出最小圈輸出
訂閱：
文章 (Atom)