主要思路

一道非常好的题，适合我这种概率期望新手来搞。

首先，我们设\(dp[i]\)为以\(i\)结尾的期望长度。其次，我们发现\((x+1)^2-x^2=2x+1\)，如果要求连续的根据字符的情况，有以下几种转移：

1. 当\(str[i]=’o’\)时，那么\(dp[i] = dp[i-1]+1\)，对答案的贡献为\(2dp[i-1]+1\)。
2. 当\(str[i]=’x’\)时，不进行转移，对答案贡献为\(0\)。
3. 当\(str[i]=’?’\)时，为\(o\)的概率为\(\frac{1}{2}\)，转移为\(dp[i]=\frac{dp[i-1]+1}{2}\)，对答案的贡献为\(\frac{2dp[i-1]+1}{2}\)。

乱搞即可。

代码

// BZ3450.cpp
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 300200;
int n;
char str[MAX_N];
long double dp[MAX_N], ans;
int main()
{
    scanf("%d%s", &n, str + 1);
    dp[0] = 0;
    for (int i = 1; i <= n; i++)
        switch (str[i])
        {
        case 'o':
            dp[i] = dp[i - 1] + 1;
            ans += 2 * dp[i - 1] + 1;
            break;
        case 'x':
            dp[i] = 0;
            break;
        case '?':
            dp[i] = 1.0 * (dp[i - 1] + 1) / 2.0;
            ans += 1.0 * (2.0 * dp[i - 1] + 1) / 2.0;
            break;
        }
    printf("%.4Lf", ans);
    return 0;
}