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\) 个。

懒了不想写，也不是很好讲清楚，不如看这里