ZJOI 2015 Day 1题解

题目:http://pan.baidu.com/s/1c0uA9Sc

标程:http://pan.baidu.com/s/1dDCj8bv

数据:http://pan.baidu.com/s/1qWNs1Us

Mst

这个题目是用来送分的,思路和我WC讲过的一个题差不多。看链接中的课件里的mst一题。

首先注意到,答案就是最小瓶颈生成树(最大边最小的生成树)上的最大边的期望。

进一步分析可以注意到,考虑一个x,如果<x的边合起来不能使得图联通,<=x的边合起来能够使得图联通,那么这个图的最小瓶颈生成上的最大边就是x。

那么,用WC讲过的同样的方法,我们可以得到一个多项式P(x),表示<x的边不能使得图联通的概率。

那么注意到,我们只需要对P(x)从0到1求积分就是答案了。为什么呢?因为P(x)也是答案>x的概率,这样相当于一个分部积分。

(这样说可能对于不熟悉微积分的同学来说可能不好理解,不妨考虑离散的情况。比如a有5种取值,0,1,2,3,4,令p[i]为a的取值>i的概率,那么EX[a]=sum p[i]。这里也是一样的道理)

Tree

其实这个题目并不难,题目等价于支持修改点权和寻找整个树的带权重心。

可以考虑使用点分治。注意到如果当前分治点是u,那么显然,我们可以先看看u是不是重心,如果不是,那么重心只可能在u最大的孩子里,这样问题就变成了u的一个子分治的子问题。

当然对于子分治我们还要考虑从u出去整个外面部分的影响,由于树分治最多有logn层,这样的影响也只有logn个,简单的处理就可以了。

Substring

首先题目中有一个关键条件是说叶子的数量不超过20个。

我们不妨对每个叶子都以它为根建一个Trie。

那么注意到整个树的任何一个子串,都是某个Trie上从一个点到它的一个子孙的路径。

那么,我们可以把这20个Trie合并成一个大Trie,然后求这个大Trie的子串数量就可以了(Trie的子串指的是从Trie中一个点到它的一个子孙)。

这可以使用比较经典的后缀自动机或者后缀数组实现。