單周賽 250 題解

本次周賽知識點：字元串，數學，上取整，動态規劃，高性能，字首字尾

題外話：自己在 <code>okr</code> 中立了個 <code>flag</code>，希望在 <code>7-8</code> 雙月逐漸熟練掌握 <code>python, go</code>，是以在之後的周賽題解中，我會逐漸引入 <code>python, go</code> 的代碼，有興趣的小夥伴可以一起學習

本次周賽着重講解一下第三題，前面兩題一筆帶過，最後一題涉及到 \(01\ trie\) 樹，後續單獨出一篇文章講解

給定一個字元串 \(w\) 表示一串單詞，給定一個字元串 \(b\) 表示破壞的字母，對于 \(w\) 中的所有單詞，如果包含 \(b\) 中的字母，那麼該單詞不可用，計算可用的單詞數

用一個數組存放 <code>w</code> 中的單詞，用桶存放 <code>b</code> 中的字元，循環判斷即可

給一個嚴格遞增的數組 \(r\)，表示台階的高度，給一個正整數 \(dist\) 表示爬一次最高能上的台階高度，初始時站在高度 \(0\) 位置，計算最少還需要放置幾個台階，使得可以爬到最後一個台階

例如 <code>r = [1, 3, 5, 10], dist = 2</code>，需要放置 <code>2</code> 個台階，高度分别為 <code>7, 9</code>（方案不唯一）

例如 <code>r = [3, 6, 8, 10], dist = 3</code>，不需要放置台階

例如 <code>r = [3, 4, 6, 7], dist = 2</code>，需要放置 <code>1</code> 個台階，高度為 <code>1</code>

對于任意兩個台階，高度分别為 \(i,\ j\)，設高度差為 \(h\)，則可以放 \(\lceil\frac{h}{dist}\rceil - 1\) 個台階

是以我們計算出差分數組 \(d\)，依次做判斷即可

在實作 \(\lceil\frac{a}{b}\rceil - 1\) 時，使用 <code>(a - 1) / b</code> 即可

給定一個 \(m\times n\) 的矩陣 \(p\)，每一個格子有一個權值 \(p[i][j]\)

現在從第一行到最後一行，每一行選一個格子，收益為權值和

但是，對于第 \(i\) 行和第 \(i - 1\) 行，如果分别選了 \(j,\ k\) 列，那麼收益減去 \(\mid j - k\mid\)

資料保證

\(1\leq m,\ n,\ m\times n\leq 10^5\)

\(0\leq p[i][j]\leq 10^5\)

考慮二維動态規劃，定義 \(dp[i][j]\) 表示走到 \((i,\ j)\) 位置的收益最大值，則狀态轉移方程為

\[dp[i][j]= \max\left\{dp[i][j],\ dp[i - 1][k] +p[i][j] - \mid j - k\mid\right\}

\]

其中 \(0\leq k &lt; n\)

但是我們需要枚舉 \(i,\ j,\ k\)，複雜度為 \(O(nmk)\)，不能接受，是以考慮優化決策，對于狀态轉移方程，我們發現實際上要計算的是

\[\left\{\begin{matrix}

dp[i - 1][k] + k + p[i][j] - j, &amp; j\geq k\\

dp[i - 1][k] - k + p[i][j] + j, &amp; j &lt; k

\end{matrix}\right.

對于目前決策，我們隻需要分别計算出 \(j\geq k\) 部分的最大值和 \(j &lt; k\) 部分的最大值即可

我們用數組 \(h_1,\ h_2\) 分别維護兩個值，具體來說

\[h_1[j] = dp[i - 1][k] + k + p[i][j] - j\\

h_2[j] = dp[i - 1][k] - k + p[i][j] + j\\

然後用兩棵紅黑樹維護二進制組 \((j,\ h_1[j]),\ (j,\ h_2[j])\)，這樣便可以在 \(O(\log n)\) 時間計算出兩段決策的最大值，在 <code>c++</code> 中，我選用 <code>set</code> 來實作，需要重載運算符

随着決策 \(j\) 指針右移，第一棵紅黑樹中要删去節點 \((j,\ h_1[j])\)，第二顆紅黑樹中要插入節點 \((j,\ h_2[j])\)，時間複雜度均為 \(O(\log n)\)

是以總的時間複雜度為 \(O(nm \log n)\)

用 \(pre[j]\) 維護 \(\max\left\{dp[i - 1][k] + k\mid 0\leq k\leq j\right\}\)

用 \(suf[j]\) 維護 \(\max\left\{dp[i - 1][k] - k\mid j\leq k\leq n - 1\right\}\)

則狀态轉移方程更新為

\[dp[i][j] = \max\left\{dp[i][j],\ \max\left\{pre[j] - j,\ suf[j] + j\right\} + p[i][j]\right\}

同時使用滾動數組把 \(dp\) 數組的第一維狀态優化掉

總的時間複雜度為 \(O(nm)\)，空間複雜度為 \(O(n)\)

注意此題爆 <code>int</code>，不開 <code>long long</code> 見祖宗

使用前字尾代替紅黑樹，代碼更好寫了，運作效率也更快