「雜題亂寫」ABC 293 ~ ABC 295
點擊查看目錄
目錄
- 「雜題亂寫」ABC 293 ~ ABC 295
- ABC 293
- D | Tying Rope
- E | Geometric Progression
- F | Zero or One
- G | Triple Index
- Ex | Optimal Path Decomposition
- ABC 294
- D | Bank
- E | 2xN Grid
- F | Sugar Water 2
- G | Distance Queries on a Tree
- ABC 295
- D | Three Days Ago
- E | Kth Number
- F | substr = S
- G | Minimum Reachable City
這個 ABC 系列大概會持續下去，每三場寫一份，
每三場寫一份的一個重要原因是標簽上限十個，
因為是 ABC 所以不做 A 題 B 題和 C 題，
ABC 293
身敗名裂.jpg
D | Tying Rope
簡單爆搜，
E | Geometric Progression
發現模數不為質數，通項公式算不了，因為需要逆元，那么分治，
F | Zero or One
考慮直接列舉 \(b\) 判斷是否合法，但是復雜度 \(O(n\log_bn)\)，
考慮列舉一個二進制數然后二分出對應的 \(b\)，但是復雜度 \(O(2^{\max(\log_bn)}\times\log_2n\times\log_2n)=O(n\log_2^2n)\)，
那么考慮縫合起來，設一個 \(k\)，列舉 \(1\sim k\) 的 \(b\)，然后 \(b\) 大于 \(k\) 時將 \(n\) 化為 \(b\) 進制數后位數比較小，可以直接列舉 \(\log_k\) 位的所有二進制數，
總復雜度 \(O(k+2^{\log_kn}\log_2^2n)\)，設 \(k=10^4\) 可過，
G | Triple Index
莫隊板子題，
Ex | Optimal Path Decomposition
這個題一看就挺二分答案的，
設 \(f_{i, j}\) 表示以 \(i\) 為根的子樹中，\(i\) 有不超過 \(j\) 個兒子與自己顏色相同時，從 \(i\) 出發的一條路徑上的與自己顏色不同的顏色數量最大值，顯然 \(0\le j\le2\)，（直接表示顏色數量最大值，不排除自己應該也行，但轉移好像不太方便，）
然后二分查找 \(k\)，每次用 \(O(n)\) 的時間算一下 \(f\) 陣列，總復雜度 \(O(n\log_2n)\)，
如何轉移？設當前列舉到了 \(u\) 的葉子結點 \(v\)，那么當且僅當 \(f_{u,j_1} + f_{v, j_2} + [j_2 = 2] \le k\) 時可以轉移，如果 \(f_{v, j_2}\) 完全沒機會轉移上去說明這棵子樹已經不滿足條件了，直接令 \(f_{u,0} = f_{u,1} = f_{u,2} = +\infty\)，轉移到根上后即可斃掉這種情況，
確實有點抽象，但是代碼很短很好寫，
\(%傻逼，這個是官方題解做法傻逼，這個是官方題解做法傻逼，這個是官方題解做法傻逼，這個是官方題解做法傻逼，這個是官方題解做法傻逼，這個是官方題解做法傻逼，這個是官方題解做法傻逼，這個是官方題解做法傻逼，這個是官方題解做法傻逼，這個是官方題解做法傻逼，這個是官方題解做法傻逼，這個是官方題解做法傻逼，這個是官方題解做法傻逼，這個是官方題解做法傻逼，這個是官方題解做法傻逼，這個是官方題解做法傻逼，這個是官方題解做法傻逼，這個是官方題解做法傻逼，這個是官方題解做法\)
ABC 294
D | Bank
考慮開個 \(vis\) 陣列記錄 \(1\sim n\) 中那些數在 \(b\) 陣列中，然后隨便操作了，
E | 2xN Grid
在兩個陣列中各開一個指標，移動程序中保證兩個指標指向的區間有交，值相等時計算相交長度，
F | Sugar Water 2
連二分都不會了，
我們二分一個濃度 \(x\)，計算濃度小于等于 \(x\) 的混合糖水數量，
化簡兩杯糖水混起來后濃度小于等于 \(x\) 的不等式：
\[\begin{aligned} \frac{a_i + c_j}{a_i + b_i + c_j + d_j} &\le x\\ a_i + c_j &\le x(a_i + b_i + c_j + d_j)\\ a_i + c_j &\le a_ix + b_ix + c_jx + d_jx\\ (1 - x)a_i - b_ix &\le (x - 1)c_j + d_jx\\ \end{aligned} \]那么設 \(v1_i = (1 - x)a_i - b_ix, v2_i = (x - 1)c_j + d_jx\)，排序后可以快速二分查找到與第 \(i\) 杯糖水混合后濃度小于 \(x\) 的糖水數量了，
G | Distance Queries on a Tree
樹剖板子題，
ABC 295
D | Three Days Ago
不難發現一個子段滿足條件必須要求這個子段內的每個數字出現次數為偶數，
狀壓一下 \(1\sim i\) 每個數字出現次數的奇偶性存進 \(f_i\)，當且僅當 \(f_i=f_j\) 時欄位 \([i + 1, j]\) 滿足條件，
E | Kth Number
經典結論：
\[E(A_k) = \sum_{i = 1}^{m} i\times P(A_k = i) = \sum_{i = 1}^{m} P(A_k \ge i) \]列舉到 \(i\) 時，為了滿足 \(i\) 至少是第 \(k\) 大，前面至少要有 \(n - k + 1\) 個數墊著，但是還有一些數本來就小于 \(i\)，那么設 \(l\) 為 \(n - k + 1\) 減去原陣列中小于 \(i\) 的數的個數（也就是需要的 \(0\) 的個數），\(r\) 為原陣列中 \(0\) 的個數，則：
\[P(A_k\ge i) = \sum_{j = l}^{r}\dbinom{r}{j}(\frac{m - i + 1}{m})^{j}(\frac{i - 1}{m})^{r - j} = \frac{1}{m ^ r}\sum_{j = l}^{r}\dbinom{r}{j}({m - i + 1})^{j}({i - 1})^{r - j} \]有些細節，
F | substr = S
數位 DP 板子！但是允許重疊，所以加一個 KMP，
G | Minimum Reachable City
有意思，
觀察到資料范圍 \(1\leq p_i \leq i\)，所以說父親都指向兒子，且任意一個點的兒子編號都比自己大，
「保證最開始時 \(v\) 能到達 \(u\)」，所以 \((u, v)\) 一定是一條返祖邊，在樹上構成一個強連通分量，這里可以把一個強連通分量放在一個并查集里面，操作 \(1\) 直接把 \(v\rightarrow u\) 路徑上經過的點全部合并到一個并查集里面，操作二直接找 \(x\) 所在并查集的根，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/553652.html
標籤：其他
上一篇：能帶理論
下一篇：返回列表