znstz的博客

博客

PR #12 验题人题解

2024-02-25 15:02:01 By znstz

Public Round 12

电塔

令操作结束后序列是 y1,y2,,yn,容易发现,把 x,y 分别排序,将 x1 变为 y1,将 x2 变为 y2 ……,是最优的。

于是问题变成了,把 xi 升序排列后,要求对于所有 i(2in),xixi1d,求最少操作次数。

考虑其差分序列,直接套用 UOJ-雪灾与外卖 的模拟费用流算法,能得 70 分。

再次转化,将 xi 减去 (i1)d,问题就变成了让 xi 不降,求最少操作次数,这个能直接做到 O(nlogn)

并查集

先拆一下贡献,对于每条边,将它的经过次数加到答案里,最后答案加上 2(n1),就是真正的答案。

考虑把 u 挂在 v 上的过程,令 S 表示 u 所在连通块的点集,则 find(u)find(v) 这条边的经过次数为:2(|S|1)1+xSdeg(x)。令这一坨式子为一个连通块的权值,显然,我们应该把 u,v 所在连通块中,权值较大的挂在权值较小的上面。

继续观察,假设 u 所在连通块的权值比 v 大,那么把 v 里面的点一个一个挂到 u 上一定是更优的。

枚举起点,将树定根在起点,问题变成了,每个点有一个权值,将 0,1,,n1 放到每个点上,要求父亲的数大于儿子,最大化每个点上权值乘上数的和。这是经典的问题,每次取权值最大的,它上面的数一定是父亲的 1,将它和父亲合并就行,新权值设为连通块内的平均数。

复杂度 O(n2logn)

划分序列

考虑最朴素的 dp:dp(i) 表示前 i 个数的最大价值,转移 dp(i)+mex(i+1,j)sum(i+1,j)dp(j)(jik)

1n 依次计算 dp 值,令当前算到的位置为 i,先维护每个位置到 i 这一段的 mex,直接开珂朵莉树维护其连续段,能分析出总共只有 O(n) 次连续段的变化。

转移考虑根号重构,令 B=n,若 imod,则重构 [i-k+B,i] 这一段的贡献,转移的时候对于散块暴力算,复杂度 O(n \sqrt {n}),实现起来很多细节。

据说存在 polylog 做法,敬请期待官方题解(。

评论

[+11]
T2 O(nlogn)
  • 2024-02-25 15:13:55
  • Reply
Comment replies
znstz:是 n^2 log,感谢指出(
[0]
T1 能讲一下最后的”直接做“是怎么做吗?赛时转化到了这个东西但往后不会了。
  • 2024-02-25 15:56:23
  • Reply
Comment replies
cnyz:可以看 CF713C 题解。
[0]
T1 其实可以直接写 O(nV) 状态数的 DP 然后直接上 Slope Trick(
  • 2024-02-25 15:58:40
  • Reply
T1 中 "考虑其差分序列,直接套用 UOJ-雪灾与外卖 的模拟费用流算法",具体是怎么做的/kel 似乎并不能直接用老鼠进洞模型,因为洞的位置可以变
  • 2024-02-25 16:11:30
  • Reply
Comment replies
znstz:一次操作就相当于在差分数组上把一个数挪到左边或者右边,这就是老鼠进洞模型。

发表评论

可以用@mike来提到mike这个用户,mike会被高亮显示。如果你真的想打“@”这个字符,请用“@@”。