【题目描述】
给定一个序列，有些位置是 o ，有些位置是 x，还有些位置不确定（用 ? 表示，各有 0.5 的概率是 o 或 x）。
定义 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;
}
就是这样啦~