Public Round 12
电塔
令操作结束后序列是 y1,y2,⋯,yn,容易发现,把 x,y 分别排序,将 x1 变为 y1,将 x2 变为 y2 ……,是最优的。
于是问题变成了,把 xi 升序排列后,要求对于所有 i(2≤i≤n),xi−xi−1≥d,求最少操作次数。
考虑其差分序列,直接套用 UOJ-雪灾与外卖 的模拟费用流算法,能得 70 分。
再次转化,将 xi 减去 (i−1)d,问题就变成了让 xi 不降,求最少操作次数,这个能直接做到 O(nlogn)。
并查集
先拆一下贡献,对于每条边,将它的经过次数加到答案里,最后答案加上 2(n−1),就是真正的答案。
考虑把 u 挂在 v 上的过程,令 S 表示 u 所在连通块的点集,则 find(u)
到 find(v)
这条边的经过次数为:−2(|S|−1)−1+∑x∈Sdeg(x)。令这一坨式子为一个连通块的权值,显然,我们应该把 u,v 所在连通块中,权值较大的挂在权值较小的上面。
继续观察,假设 u 所在连通块的权值比 v 大,那么把 v 里面的点一个一个挂到 u 上一定是更优的。
枚举起点,将树定根在起点,问题变成了,每个点有一个权值,将 0,1,⋯,n−1 放到每个点上,要求父亲的数大于儿子,最大化每个点上权值乘上数的和。这是经典的问题,每次取权值最大的,它上面的数一定是父亲的 −1,将它和父亲合并就行,新权值设为连通块内的平均数。
复杂度 O(n2logn)。
划分序列
考虑最朴素的 dp:dp(i) 表示前 i 个数的最大价值,转移 dp(i)+mex(i+1,j)⋅sum(i+1,j)→dp(j)(j−i≤k)。
从 1 到 n 依次计算 dp 值,令当前算到的位置为 i,先维护每个位置到 i 这一段的 mex,直接开珂朵莉树维护其连续段,能分析出总共只有 O(n) 次连续段的变化。
转移考虑根号重构,令 B=⌊√n⌋,若 imod,则重构 [i-k+B,i] 这一段的贡献,转移的时候对于散块暴力算,复杂度 O(n \sqrt {n}),实现起来很多细节。
据说存在 polylog 做法,敬请期待官方题解(。