拆點作最大流
這邊最大流量可以被估計最多約nn
所以我選擇Ford Fulkerson實作Maximum Flow
而非Edmond Karp
- 8月 06 週四 200919:03
PKU - 2711 Leapin' Lizards
- 8月 06 週四 200919:03
PKU - 3439 Server Relocation
再明顯不過的一題BFS了
- 8月 06 週四 200919:00
PKU - 2689 Prime Distance
先用篩法篩一段質數
接著再用篩法
平行篩你要的那一段
假設D = U-L
這樣時間複雜度約為
O primes.size lnD
- 8月 06 週四 200918:57
PKU - 2897 Dramatic Multiplications
假設答案是J BCDEK = KBCDE
你可以知道最大的那個第一位是
K
這樣的話
用J除了之後
你就可以得到B
這樣有什麼用呢
你會發現這樣就可以代入另外一邊
變成KB都知道
這樣循環下去就可以得到正確答案
接著你會觀察到最常循環為兩位
故一百位都沒有結束 就是死循環
就沒有答案啦
- 8月 06 週四 200918:56
PKU - 2705 Overflowing Bookshelf
明顯是實作一個Double End Linked List
- 8月 06 週四 200918:54
PKU - 2710 Consecutive Digits
通分然後一直作進位轉換就好了
- 8月 06 週四 200918:53
PKU - 3126 Prime Path
用相關的關係做一個Graph
再來由BFS求是否可到達
- 8月 06 週四 200918:52
PKU - 2704 Pascal's Travels
因為有單向性
可以直接動態規劃
- 8月 03 週一 200919:36
PKU - 3692 Kindergarten
很有趣的一題
你可以想成 假設Gi跟Bj不相識 那Maximum Set之中
其中一個要被刪除
這樣的話就做一個Adjacent Matrix
是不認識的Matrix
然後做Minimum Vertex Covering就OK了
- 8月 03 週一 200917:59
ACM 10181 - 15-Puzzle Problem
類似8 Puzzle的做法
用IDA
