好久没更新了。。。随便贴几道有趣的小题目。。。都来自我的ATCS 期末take home exam。

1. 在S^d(d维空间中所有离原点距离为1的点)中随机选择d+1个点。。。组成的simplex包含原点的概率是多少？

2. 平面上有n个圆，求证边界上的顶点的数量是O(n)的。

3. 平面上有一个概率分布（不防假设是连续的），求证一定存在两条直线讲其分成相等的4部分。

过几天再贴一下我的做法。。。

题目：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中一个点到它的一个子孙）。

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