UOJ Logo AprilGrimoire的博客

博客

标签
暂无

十二省联考D2T2 spring 线段树做法

2019-04-08 14:45:32 By AprilGrimoire

十二省联考D2T2 spring 线段树做法


由于我太菜了,不会长链剖分,所以在JSOI的考场上口胡了一个奇怪的线段树的做法,水过了D2T2。考完后我证了一下,发现它好像确实是对的。

我们按照$M_i$从大到小的顺序依次覆盖所有的点。定义$f(i)=[i号点已被覆盖]$,$g(i)$为从$i$号点出发到子树中某个点所经过的已被覆盖的点的个数的最大值。设点$a$是点$b$的父亲。若$g(b)=g(a)-f(a)$,我们就称$b$是$a$的实儿子。否则,我们称$b$是$a$的虚儿子。设当前我们已经创建了$k$个段,$S_1 \cdots S_k$。我们将构造一种方案,使得$k$始终等于$g(1)$,而且以任意一个$x$为根的子树中用过的不同的段的数量恰好等于$g(x)$。设当前我们将要覆盖的点为$p$。

将$p$覆盖后,可能会有两种情况出现:

1) $g(1)$的值增大了

这种情况下,原来的$k$个段就不够用了。为了最小化所有段的大小之和,我们可以创建一个大小为$M_p$的新段,用它来覆盖$p$。

2) $g(1)$的值保持不变

这种情况下,我们可以从$p$出发沿着实边往根走,直到遇到第一个虚边(由于$g(1)$的值保持不变,这样的虚边一定存在)。设达到的最后一个点是$a$,$a$的父亲是$b$。任选一个$b$的实儿子$c$,则一定有$g(c)>g(a)$。由于$c$的子树中用过的不同的段的个数比$a$的子树多,我们一定可以选出一个在$c$的子树中用过但是没有在$a$的子树中用过的段,并用这个段来覆盖$p$。

可以验证在这遇到遇到这两种情况后,「以任意一个$x$为根的子树中用过的不同的段的数量恰好等于$g(x)$」这个性质仍然成立。因此,我们只需要在原树的DFS序上建立线段树,维护$g(1)$的值,就能知道我们在哪些时候需要新建一个段,并把它的长度累加到答案里。由于我们建立的最大的段,次大的段,第三大的段……都分别是最小的,而且建立的段的个数也是最少的,所以这样求出的答案一定是正确的。

AC代码

关于UOJ上奇怪的CE问题

2018-07-18 17:25:12 By AprilGrimoire

这个提交经过各位dalao的验证,在本地(Linux环境)能够正常编译,然而在UOJ上不管选择C++还是C++11都会CE,而且CE信息很奇怪。

这是为什么呢?

共 2 篇博客