AtCoder Beginner Contest 276

咕咕咕咕。

E – Round Trip

如果存在某个点双满足这个点双包含起点且点双大小大于 \(4\) 则有解。

F – Double Chance

考虑不断在之前的基础上在末尾添加一个数，每次更新期望。

假设此前已经有 \(i – 1\) 个数了，期望为 \(E\) ，新添加的数为 \(a_i\) 。

在 \(i\) 个数中有放回的抽两个可以分为一下几种情况:

1. 在前 \(i – 1\) 个数有放回的抽两个，概率为 \(\frac{(i – 1)^2}{i^2}\) ，值为 \(E\)。
2. 一个属于前 \(i – 1\) 个数，一个为第 \(i\) 个数，概率为 \(\frac{i^2 – (i – 1)^2 – 1}{i^2}\) ，此时又分两种情况：
   1. 最大值属于前 \(i – 1\) 个数，值为 \(\dfrac{\sum_{j = 1}^{i – 1}[a_j > a_i]a_j}{i – 1}\)。
   2. 最大值为第 \(i\) 个数，值为 \(\dfrac{\sum_{j = 1}^{i – 1}[a_j \le a_i]a_i}{i – 1}\)。
3. 两次都抽到第 \(i\) 个数，概率为 \(\frac{1}{i^2}\)，值为 \(a_i\)。

三种情况线性组合一下就能算出新的期望。

第二种情况就搞个树状数组之类的数据结构维护一下。

G – Count Sequences

To be added.

Ex – Construct a Matrix

To be solved.

原文地址：http://www.cnblogs.com/zengzk/p/16861836.html