## 動態規劃 ## 字元串 ## 雜題 #### [A:Animals and Puzzle](https://www.luogu.com.cn/problem/CF713D) #### [B:Vanya and Treasure](https://www.luogu.com.cn/problem ...
動態規劃
字元串
雜題
A:Animals and Puzzle
B:Vanya and Treasure
根號分治。
實際上是從 \((1, 1)\) 先找一個 \(1\)，再找一個 \(2\dots\) 最後找一個 \(p\) 然後
依次按最短路走過去。
我們有兩種想法， 直接 BFS 遞推得到當前點到所有點的距離 或者 直接暴力枚舉兩個層之間的所有點對， 兩種做法的時間複雜度 都是 \(O(n^2 m^2)\)。
考慮縫合， 經過一番神秘的複雜度分析， 我們得到了 \(O(nm \sqrt{nm})\) 的優秀演算法。
D:Awesome Substrings
根號分治。
令 \(s_i\) 表示 \(\sum\limits_{1}^{i}a_i\)， 且 枚舉的倍數為 \(d\)， 則有 \(r - l = d \times (s_r - s_l)\)。
直接暴力做是 \(O(n^2)\)， 且不好優化。 我們考慮分塊計算的思想， 設閾值為 \(T\)。
當 \(d \in [1, T]\) 時， 將原式變形可得 \(d \times s_r - r = d \times s_l - l\)， 我們設 \(f(i, d) = d \times s_i - i\)， 對於每個 d 可以求出 $ f(0...n, d)$ 的值。 對於每個值 \(x\)，若有 \(k\) 個 \(i\) 滿足 \(f(i, d) = x\)， 它都會對答案產生 \(\tbinom{k}{2}\) 的貢獻。 這一部分可以做到 \(O(nT)\) 的實現。
當 \(d \in (T, n]\) 時， 將原式變形可以得到 \(s_r - s_l = \dfrac{r - l}{d} < \dfrac{n}{d}\) ， 即有貢獻的 \((a, b)\) 對應的區間中 \(1\) 的個數 \(k < \dfrac{n}{d}\)。 因此我們對於每個 \(l, k\) 找到 \(r\) 的範圍， 其對答案的貢獻為 \(\lfloor \dfrac{r - i}{k} \rfloor - \lfloor \dfrac{l - i}{k} \rfloor\) ， 再減去 \(d \le T\) 的部分。 這一部分可以做到 \(O(n\frac{n}{T})\)
總時間複雜度為 \(O(nT + n\frac{n}{T})\)， 當 \(T = \sqrt{n}\) 時最優。
E:PolandBall and Gifts
若將送別人禮物看做一條有向邊， 那麼排列 p 所形成的是 一些閉合的有向環。 一個人收到禮物當且僅當一條有向邊所連接的兩個人都帶了禮物。
先考慮最大化。 假定環的大小為 k， 對於一個奇環， 當有 \(\dfrac{k + 1}{2}\) 個人不帶禮物時， 這 k 個人收不到禮物； 對於一個偶環， 當有 \(\dfrac{k}{2}\) 個人不帶禮物時， 這 k 個人收不到禮物。
一個不帶禮物的人最多可以影響兩個人， 我們考慮儘量使每個不帶禮物的人的影響最大。 而對於任意環， 只需要 \(\lfloor \frac{k}{2} \rfloor\) 個不帶禮物的人即可將 可以影響兩個人的點位 占滿。 我們令 \(ans2 = \sum\limits{\lfloor \dfrac{siz[i]}{2} \rfloor}\)， \(siz[i]\) 表示環的大小。 當 \(ans2 >= m\) 時， 每個不帶禮物的人都能占據一個 影響兩個人的點位；
否則的話， 剩餘的人就占據奇環上只能影響一個人的點位。
再考慮最小化。 對於一個大小為 \(k\) 的環， 當環上有 \(k\) 個不帶禮物的人 與 有 \(k - 1\) 個不帶禮物的人都只會造成 \(k\) 個人得不到禮物。 故而， 將一個環完全占滿更優。 原題即轉化為 判斷是否能找到幾個環 使 他們的大小和 為 \(m\)， 如果能， 答案即為 \(m\)， 否則的話， 否則，忘帶禮物的人的形式就是若幹個環加上一條鏈，而這條鏈的尾部會有一個雖然帶了禮物，但是收不到禮物的人。所以答案就是 \(m + 1\)。
F:Nastya and Time Machine
構造。
不難發現， 經過節點次數的下界是所有節點的度數的最大值(類比於菊花)。 如何構造出滿足下界的答案？
為了方便構造，若進入節點 \(x\) 的時間點為 \(t_x\)，則離開節點 \(x\) 的時間點必須為 \(t_x - 1\) (這樣返回節點 x 的父節點時間點就為 \(t_x\))
在遍歷節點 x 的所有子節點時可能會有如下兩種情況：
-
\(t_x + deg_x < maxdeg\) 則過程中不會超過答案，只需遍歷結束後將時間回到 \(t_x - 1\) 即可。
-
\(t_x + deg_x \ge maxdeg\) 過程中會有某一個節點的時間點超過答案。因為總共會占用 \(deg_x + 1\) 個時間點，因此當過程中的標號達到 maxdeg 時只需回到 \(maxdeg − deg_x\) 的時間點即可。
G:Andryusha and Nervous Barriers
直接正向模擬很困難， 考慮從另一個角度解題。
我們可以將板子看成從高到低依次插入得到的， 這樣的話， 我們可以不用在意板子 和 球的高度， 只需關註他們的橫坐標即可。
那麼此時， 一個板子的作用實際上是 求出 一定區間中球的個數 \(x\), 並使區間兩端點 \(+x\), 將區間(除去端點)賦值為 \(0\) 。
考慮到球在一定高度下落可能會砸碎板子這一因素， 我們對於不同組的球再記錄一個參數 表示他們下降的高度， 用 優先隊列 來對高度進行排序。
我們考慮設計一個函數， 詢問一定區間內所有 不足以砸碎當前板子的球的個數。 由於對每個橫坐標不同的點都需要查找一次優先隊列， 時間複雜度過高。
考慮維護一個變數記錄區間最小值， 當區間最小值大於 堅固程度時直接返回， 這樣和區間取模類似， 在數據隨機條件下時間複雜度有保證。
H:Omkar and Landslide
結論題。
-
對山的調整順序並不影響最終的結果， 且停止時有 \(h_{i + 1} - h_i \in \{0, 1\}\)。
-
可以證明， 停止時 \(h_{i + 1} - h_i\) 最多有一個為 \(0\), 其他的為 \(1\)。
這樣的話， 對於一個 n 和 h， 就可以直接確定最終的答案。
J:Goodbye Souvenir
首先， 由於區間中一種數只會計算一次貢獻， 那麼我們要求的 \(last_x - first_x = \sum\limits_{i \in [L, R]}^{a[i] = x} i - pre_i\)， 這是因為對於中間的部分而言， 令 \(j\) 為下一個位置滿足 \(a[j] = x\) 的下標， 則 \(pre_j = i\)， 那麼 \(i - pre_i + j - pre_j = j - pre_i\)
那麼此時， 我們可以具化出兩個不等式， \(i \le R\) ， \(pre_i \ge L\)， 在加入一個時間軸， 即三維偏序。
具體的， 我們有 \(set\) 來維護每個值的首碼， 修改一個數時需要修改以當前數為首碼 數據。
