某島

… : "…アッカリ~ン . .. . " .. .
September 30, 2012

ZOJ Monthly, September 2012

Problem A. Kitty’s Game
有一隻喵身上有個記分牌,每個點上有一個全值 pi,她每沿著邊走一步,記分牌上的數字就會變為這兩個數字的 lcm。
問從起點S走到終點T,最後記分牌上數字為 k 的方案有多少種。(要求每一步記分牌上的數字都必須發生變化。
Tags: DP
略。( .. 注意到 lcm 單調遞增,用這個值劃分階段即可。。
http://acm.hust.edu.cn:8080/judge/problem/viewSource.action?id=711276

Problem B. BiliBili
。略。。類似 [JSOI2008]球形空間產生器sphere。。
做差後消去二次項,轉換成線性方程組高斯消元即可。
http://acm.hust.edu.cn:8080/judge/problem/viewSource.action?id=709071

Problem C. Matrix Transformer
。。開始認為任意行或者列都有 1 就行,反例是 1 全部集中在某行某列的情況。。
。。。(然後發現其實就是求是否有完備匹配吧。。
http://acm.hust.edu.cn:8080/judge/problem/viewSource.action?id=709215

Problem D. Gao the Grid
好像就是 Codeforces #136 DIV 1 的 Problem D。。(。的弱化。。
http://codeforces.com/contest/220/problem/D
http://acm.hust.edu.cn:8080/judge/contest/viewSource.action?id=711104

Problem E. Gao the Grid II
只計數銳角三角形。。。
。。(。。實際上數據弱成狗。。使用點積然後 O(n4)暴力也能過。。。
http://acm.hust.edu.cn:8080/judge/contest/viewSource.action?id=711141
(唔。。這類問題有待總結。。要不比賽時還是跪成 SB 啊。。

Problem F. Social Net
Sub Task 1: 最大生成樹。(略。。
Sub Task 2: 給定一顆點權樹,權值記為 ai,每次詢問 x -> y 的路徑上,
max(aj – ai), j >= i 的值是多少。。(將路徑展開看成鏈。。
Tags: 倍增祖先
對於鏈上的問題,可以用 O(n) 解決。(動態規劃。。
。樹上結構則先用倍增祖先壓縮結點信息。。再跑鏈上演算法即可。。
(注意另一條要取反序,另外 lca 位置上的元素和諧起見最好一邊各取一次。。。
http://acm.hust.edu.cn:8080/judge/problem/viewSource.action?id=711497

Problem G. Toy Blocks
在數軸上給定若干多米諾骨牌,問至少幾次可以放倒所有骨牌。
Tags: 動態規劃,zkw 線段樹
略)。。預處理和 DP 的過程都需要使用數據結構優化。
http://acm.hust.edu.cn:8080/judge/problem/viewSource.action?id=713189

Problem H. Cipher LockCipher Lock
一個環, 環上每個點有 a, b 兩個屬性。。(a <= P, b <= Q.. 要求相鄰兩個環至少有一個屬性是相同的。。 其中一些位置要求是給定的 ai, bi.. 問方案總數。。 Tags: 狀態壓縮 DP, 矩陣乘法 http://acm.hust.edu.cn:8080/judge/problem/viewSource.action?id=711038

先根據每個已確定的位置拆環。(本題中已確定位置至少存在一個。。。
。。然後暴力 DP 。。然後發現狀態只與是否和起始位置相同有關。。
。。有兩個屬性壓縮後就是 2 位。。。
。。人工制出轉移矩陣即可。。。

Problem I. Maze
。。比較裸的 mask bfs 。。沒什麼好說的。。
http://acm.hust.edu.cn:8080/judge/problem/viewSource.action?id=710689

Problem J. Sleeper’s Schedule
睡眠分配問題。。(區間調度問題 Power up,
。。一次醒來後必須在 [t, t+l] 之間再次睡眠。。
。如果在 t 小時之後睡眠,則會有相應的懲罰分數,且本次睡眠的時間相應延長。。。
。。(。。越往後單位時間的懲罰越高。。也就是超過 t 的部分平方。。很科學。。
最終得分為 [區間調度得分] – [熬夜懲罰]。。

Analysis:
。DP[i][j] 表示時刻 i 已經熬了 j 時間的最大收益。。轉移分三種情況討論即可。(睜眼,睡覺,取區間。。
注意邊界等細節。(另外 dp[] 中間值有可能從負值轉移,初始化要設置成 -oo。。
http://acm.hust.edu.cn:8080/judge/problem/viewSource.action?id=710322

ZOJ 3654 Letty’s Math Class
。。。麻煩的地方似乎只在高精度表達式解析的那塊。。
。。Python 的話 直接 input() 進來就行了。(Ruby 的對應的寫法好像是 eval gets ?。。
http://acm.hust.edu.cn:8080/judge/problem/viewSource.action?id=709304

External link:

http://edward-mj.com/?p=615
http://acm.zju.edu.cn/onlinejudge/showContestProblems.do?contestId=341
http://acm.hust.edu.cn:8080/judge/contest/view.action?cid=13939#overview