【题目描述】

给定一个序列,有些位置是 o ,有些位置是 x,还有些位置不确定(用 ? 表示,各有 0.5 的概率是 ox)。

定义 comb 为极大的连续 o ,一段长度为 $a$ 的 comb 的收益为 $a^3$,序列的收益为 comb 的收益总和。

求序列收益的期望。

【题目链接】

BZOJ 4318 OSU!

【解题思路】

$$ (x + 1)^3 - x^3 = 3x^2 + 3x + 1 $$

类似于 [BZOJ 3450] Easy - 期望,单独考虑每个位置的贡献。

因为贡献是 「长度」 和 「长度平方」 的线性表达式,根据期望的线性性质,贡献的期望可由 「长度的期望」 和 「长度平方的期望」 得到。

注意这里说的是「长度平方的期望」而不是「长度期望的平方」。

我们维护以每个位置结尾的连续 o 的「长度的期望」和 「长度平方的期望」,统计贡献即可。

【AC代码】

一开始居然把 四舍五入到小数点后一位 看成了 先四舍五入,再保留小数点一位,然后 WA 到爆炸还以为是精度问题,真是服气...

#include <iostream>
#include <iomanip>
#include <cmath>
  
int main(){
    int n;
    std::cin >> n;
  
    double exLen1 = 0, exLen2 = 0, ans = 0;
    for(int i = 0; i < n; i++){
        double p;
        std::cin >> p;
  
        ans += (3 * exLen1 + 3 * exLen2 + 1) * p;
        exLen2 = (exLen2 + 2 * exLen1 + 1) * p;
        exLen1 = (exLen1 + 1) * p;
    }
  
    std::cout.setf(std::ios::fixed);
    std::cout << std::setprecision(1) << floor(ans * 10 + 0.5 + 1e-10) / 10 << std::endl;
  
    return 0;
}

就是这样啦~