NOIP模拟79

「F·S·Y·O」on 10.17

T1 F

因為每個點會産生貢獻當且僅當它在可以到他的點之前被删除，并且此題遵守期望的線性性。

是以設所有可以到達點 \(i\) 的數量為 \(c_i\) 那麼答案就是 \(\sum \frac{1}{c_i}\) 。

縮點+拓撲排序+bitset 可以做到 \(\mathcal{O}(\frac{n^3}{w})\) 直接搜就是 \(\mathcal{O}(n^2)\)

T2 S

字元串 DP(KMP)。

設 \(f_{i,j}\) 表示 \(S\) 到 \(i\) 位置，目前比對到 \(T\) 的位置 \(j\) 。

每次對于删除或者不删除 \(i+1\) 進行轉移，如果不删除就不斷跳 \(nxt\) 看 \(k+1\) 能否和 \(i+1\) 成功比對。

轉移即可。。

T3 Y

暴搜竟然有 70pts ！！（盡管我沒打出來），BFS 目前空格的位置，開一個四位數組記錄空格以及指定棋子所在位置是否經過過。

枚舉空格的移動，當他移動到指定棋子的位置時兩者位置互換，于是我們得到了一份 70pts 的代碼(\(code\))

然後發現有許多狀态時重複的，于是我們考慮初始化。

枚舉每一個點時指定棋子的位置，在枚舉周圍的點是空格的情況，BFS出這幾個格子之間不經過指定格子到達别的格子的距離，建邊。

對于每一個詢問跑一邊最短路 複雜度 \(\mathcal{O}(n^2m^2+qnmlog(nm))\)

T4 O