Hellc

【题目描述】

给定一个序列，有些位置是 o ，有些位置是 x，还有些位置不确定（用 ? 表示，各有 0.5 的概率是 o 或 x）。

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

求序列收益的期望。

【题目链接】

BZOJ 3450 Easy

【解题思路】

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

我们可以单独考虑每个位置的贡献（长度为 $x + 1$ 的连续 o 的最后一个位置的贡献为 $2x + 1$）。

因为贡献是长度的线性表达式，根据期望的线性性质，贡献的期望可由长度的期望得到。

设 $len(i)$ 表示以 $i$ 结尾的连续 o 的长度的期望。

分情况讨论：

当字符为 o 时，长度直接加一。

$len(i) = len(i - 1) + 1$，对答案的贡献为 $2 \times len(i - 1) + 1$

当字符为 x 时，直接成为 $0$。

$len(i) = 0$，对答案贡献为 $0$。

当字符为 ? 时，一半的概率长度加一，一半的概率直接成为 $0$。

$len(i) = \frac 1 2 \times (len(i - 1) + 1)$，对答案的贡献为 $\frac 1 2 \times (2 \times len(i - 1) + 1)$。

【AC代码】

#include <iostream>
#include <iomanip>
 
const int MAXN = 300000;
 
char str[MAXN + 1];
int n;
 
double exLen[MAXN + 1];
 
inline double solve(){
    double ans = 0;
    for(int i = 1; i <= n; i++){
        if(str[i - 1] == 'o'){
            ans += 2 * exLen[i - 1] + 1;
            exLen[i] = exLen[i - 1] + 1;
        } else if(str[i - 1] == 'x'){
            exLen[i] = 0;
        } else if(str[i - 1] == '?'){
            ans += (2 * exLen[i - 1] + 1) / 2;
            exLen[i] = (exLen[i - 1] + 1) / 2;
        } else{
            throw;
        }
    }
 
    return ans;
}
 
int main(){
    std::cin >> n >> str;
     
    std::cout.setf(std::ios::fixed);
    std::cout << std::setprecision(4) << solve() << std::endl;
 
    return 0;
}

就是这样咯~