沒想到什麼特別的解法
就單純枚舉前面頭的部分 然後去一一試驗
- 7月 30 週四 200915:26
PKU - 3175 Finding Bovine Roots
- 7月 30 週四 200915:17
PKU - 3068 "Shortest" pair of paths
很棒的例題!
因為他說一個點只能走一次 除了起點跟終點
那乍看之下就是一個Max flow的結構了 拆點型
再加上它需要最少的距離
那就是一個Minimum Cost Max flow
這是我第一次寫最小成本流
首先你用一個Source出發 走到了 Sink
你使用的是SPFA去走負權邊有向圖 求出
- 7月 30 週四 200915:13
PKU - 2127 Greatest Common Increasing Subsequence
原本我寫的也是ON3的 後來參考這份報告寫出ON2的算法
不過注意他下面詳解的程式碼是錯誤的 如果理解他做法可以輕鬆看出錯誤點
你要仔細思考它的思路再重新撰寫
否則直接複製是會錯的
至於路徑追蹤 就用類似佛洛伊德 追蹤路徑法的類似方法
只不過把每一個二維陣列都做上絕對編號
這樣就可以在一個二維陣列做
- 7月 30 週四 200915:11
PKU - 3624 Charm Bracelet
蠻典型的單背包 不能重複物品的最佳解動態規劃
- 7月 28 週二 200915:19
PKU - 2230 Watchcow
把邊拆成兩個 變成Directed Graph
去作Euler Circuit的演算法即可
蠻典型的題目
- 7月 28 週二 200915:16
PKU - 3041 Asteroids
參考文件
第四頁
其實也可以用一個比較直觀的想法
R C必皆被Cover 若不成立
那可找到另外一對Ri Cj可以被配對 這樣就不是Maximum Matching了
- 7月 28 週二 200909:02
Get Over
很好聽的一首歌
你一直在扶持著我 現在的我也將用自己的力量回報你 //所以我們結伴前行 牽手走向未來 //平時就這樣嬉戲打鬧 總有些虛無的感覺 //包圍在冷漠的目光裡 屈於時代的巨風 //如果要放棄 那又何必開始 //如果要忘記 那又何必在意 //動搖與勇氣在心中此起波伏 //別再猶豫 用雙手去創
- 7月 28 週二 200908:19
PKU - 1989 The Cow Lineup
假設C1...C3皆包含有1...K的數字
而Cn卻沒全包含
則我必可找到一個數字a 不屬於Cn而屬於集合1...K
如此
xxxx...長度n-1a必不能成為整個sequence的subsequence
C1 C2 C3 ... Cn
- 7月 27 週一 200915:00
PKU - 2393 Yogurt factory
USACO Gold
寫出來會很清楚的看見
Minimum cost =
C1Y1 Y2 minC1 S, C2 Y3 minC3, S minC1 S, C2 ...
所以可以發現前項的minimum是可以被繼承的
- 7月 27 週一 200911:44
PKU - 2182 Lost Cows
表面上是需要ON2的
如果你仔細分析問題
你就會發現其實就是從後面找回來
然後該狀態下找第n大的數字
這樣的話就用Ranking Tree 我不確定真正的名稱 這是我對這作法的命名
可以在log maxL的時間下找到要的數字
這樣時間可以縮到ON log N
以這樣的規模就算合理了
如果他的N再大到
