[原创题]断罪者

题目

比赛描述不是我写的!!!!

回过神来发现就公开赛已经已经过审了orz

题解

这道题目有一个思维陷阱,那就是题目过分强调了集合的概念,导致大家一拿到这个题目就会往并查集上面去向,不过稍微玩过数据之后就会发现,这其实就是一道简单的维护最大值的题目。

因为本次比赛的题目原本是OI赛制,在我们学校内部考的,所以这道题给了几个梯度,顺着梯度来是很好想到正解的,但是想要实现还是要有不错的代码功底。(为了防止网络赛的复制模板的行为,特意复杂化了题目)

优先队列——期望得分30

观察约定我们发现,有6个点是既满足没有单点修改(清零),又满足单点插入(合并)的性质,很容易想到用优先队列维护。
优先队列里存的是一个二元组,分别是该点的值以及编号。
但是优先队列有个问题就是没办法单点修改,这时候就要我们手写堆。

大根堆——期望得分60

按照刚刚优先队列的思路,要想单点修改,还得自己写堆。
但是因为不确定每个堆的大小,所以不能直接开2000000个堆,所以得用链表实现,或者用数组模拟,这样子就能过掉所有有特殊约定的点。
对于不满足约定①的数据,当然也可以将两个堆合并,说不定还能多过一两个点。

左偏树(或者其他可并堆)——期望得分100

普通的堆的合并时间复杂度都是\(O(n^2)\)的,而对于不满足约定①的数据,我们显然需要一种数据结构,来实现快速合并,通过上面两种方法的引导,我们可以采用可并堆(这里用的是左偏树,最简单的可并堆),合并两个堆的时间复杂度为\(O(nlogn)\)

如果你不清楚左偏树做这道题,在思维的过程中,也应该体会到了左偏树的用法。

左偏树在维护了堆的性质的同时,还用\(dis\)来维护一个距离值,具体是说,节点i的距离(dis(i))是节点i到它的子树中,最近的叶子节点所经过的边数。

两个基本性质:

[性质1 堆] 节点的键值小于或等于它的左右子节点的键值。

[性质2 左偏] 节点的左子节点的距离不小于右子节点的距离。(在合并操作时起作用)

这里有篇文章专门讲左偏树,比较详细

然后你会发现这是道模板题(不好意思我太弱了orz),就用pb_ds库给A掉了。

先贴我的代码,比较丑,没有常数优化(个人不是很喜欢卡常)

这个是@Ajsoabk大佬写的,短小精悍,加了快读都比我短。

写在后面

其实这道题目一开始还更难,后面就变成了一道模板题

数据是随机生成的,可能这一点比较坑吧,只要有点微小的差错就会WA(我反省)

其实数据挺弱的,set+并查集,暴力合并,都只超时1个点

发表评论

电子邮件地址不会被公开。 必填项已用*标注