p_b_p_b的博客

博客

Public Round #12 题解

2024-02-25 16:08:26 By p_b_p_b

电塔

来源:

首先把 xi 从小到大排序,不妨假设 xi 相对大小关系不变,那么只需满足 xi+1xid

yi=xiid,那么只需保证最终 yi+1yi。同时,在这个过程中我们需要保证 yiid

由于我们需要保证 yiy1d,所以我们先把比 d 小的 yi 先提升到 d,然后就不需要考虑下界的限制了。

那么接下来就是有一个数组,每次给某个数加减一,使得最终单调不降,求最小操作数。

考虑设 fi,jyij 且前 i 个数已经单调不降的最小花费,gi,jyi=j 且前 i 个数已经单调不降的最小花费,那么有 gi,j=fi1,j+|yij|,容易发现我们的 j 只需要取在 {yi} 里出现过的即可,复杂度 O(n2)

然后发现假如 (j,gi1,j) 这些点是下凸的,fg 相当于前缀最小值,所以 (j,fi1,j) 这些点也是下凸的,然后 (j,|yij|) 也是下凸的,所以 (j,gi,j) 也是下凸的。

同时 (j,fi,j) 是呈现分段线性函数的样式,具体的,存在 0=a0a1a2ai,使得 f(x)=fi,x[aj,aj+1] 上斜率为 ji,且 xai,f(x)=f(ai)。我们尝试用堆维护 a1,a2,,ai 以及 w=fi,ai。那么从 fi1 转移到 fi 时,假如 yiai1,那么直接令 ai=yi 即可;假如 yi<ai1,那么令 w:=w+ai1yi,并设置 ai1:=yi,ai=yi 即可。

复杂度 O(nlogn)

并查集

来源:

考虑每条边对答案的贡献。合并 Ai,Bi 时,如果令 AiBi 的父亲,则这条边被走的次数是 Bi 当前连通块向外连的边数。

因此只要确定了边的顺序,那么一定是让度数小的连通块成为度数大的连通块的父亲。

进一步可以发现,如果 Bi 的连通块度数非零,那么把加边的顺序修改为先合并 Bi 的连通块,再连接 (Ai,Bi) ,再按照原顺序合并 Ai 的连通块,一定不劣。

因此不难证明,最优加边顺序一定满足加入的边在任意时刻都是连通的。即存在一个根,每次加边是把儿子和父亲合并,且父亲此时一定已经与根连通。

感性理解一下,最优加边顺序里,儿子的度数应该不会比上面一整个连通块的度数要大。事实上,如若不然,把儿子选为根一定更优。

于是加入一个儿子就是给答案加上总度数,然后给总度数加上儿子的度数减一。

最后只需要把加入儿子的顺序定下来,满足父亲比儿子早加入。这是一个经典的贪心题,可以用并查集加优先队列实现。

复杂度 O(n2logn)

划分序列

来源:

咕了,见验题人题解

评论

[+20]
验题人题解:据说存在 polylog 做法,敬请期待官方题解(。
  • 2024-02-25 16:11:21
  • Reply
Comment replies
RDFZchenyy:所以我能请求搞定 poly log 的 dalao 们发一下做法吗
[+1]
A题转化后等价于洛谷P4597吧
  • 2024-02-25 19:05:33
  • Reply

发表评论

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