AtCoder Grand Contest 007

AGC007

\(a\) 單增，\(b\) 單減，考慮構造 \(a,b\) 為序列 \(c\) 的字首、字尾和。那麼 \(a_{pi}+b_{pi}=sum+c_{pi}\)。\(sum\) 為 \(\sum c_i\)。那麼讓 \(c\) 為 \(p\) 的置換即可滿足要求。

找規律

很明顯，原問題可以轉化為将 \(n\) 隻熊劃分成若幹段（每一段的金币放在一起連續取）的最優方案。那麼就可以dp了。設 \(f_i\) 為弄完 \([1,i]\) 的最短時間，有 \(f_i=\min\{f_j+(x_i-x_j)+\max(2(x_i-x_j),T)\},j<i\)。式子中 \(x_i-x_j\) 的部分求和就是總長，不用考慮。對于 \(\max\) 的部分，取 \(T\) 的一定是一段字尾，那麼可以把轉移分為兩部分，一部分取 \(T\)，一部分取 \(2(x_i-x_j)\)。簡單的維護一個隊列和最值就做到了 \(O(n)\)。

二分答案 \(x\)，然後進行dp：因為每條邊隻能進一次出一次，是以每棵子樹一定放在一起走，設 \(f_{x,a,b}\) 表示從 \(x\) 到第一個葉子距離為 \(a\)，最後一個距離為 \(b\)，中間路徑都符合 \(dist\le x\)，是否可行。然後這種 \(0/1\) 狀态的一般都可以改成求最值來優化，隻需求 \(g_{x,a}\) 表示使 \(f_{x,a,b}=1\) 的最小的 \(b\)，這個可以通過排序+雙指針快速求出。如果使用比較優秀的排序方式（歸并？），複雜度就是狀态數量。那麼有多少有效狀态呢？

注意這是一棵二叉樹，假設 \(x\) 的左右兒子分别有 \(cl,cr\) 種狀态，假設 \(cl<cr\)，那麼隻需要處理第一個葉子節點在 \(L\) 内或者最後一個葉子節點在 \(L\) 内的狀态，共 \(2cl\) 個新增的狀态。不難發現總共 \(n\log n\) 個。

懶了不想寫，也不是很好講清楚，不如看這裡