CUP 4367: Tyvj1952 Easy BZOJ

题解

由于给定序列，$o$的概率一定是1，$x$的概率一定是0.
$?$的期望实际上是0.5
我们要求的是$E_{x^2}$,令$dp_i$代表到第i位时$E_{x^2i}$，$l_i$为到达$i$位置时的期望长度。根据上述条件，$o$时$l_i = l_{i-1} + 1$,$x$时$l_i = 0$,而$x$的时候$l_i = 0.5 \times (l_{i-1} + 1)$

根据$l$，观察$E_i - E_{i-1}$,可以发现$x^2 - (x - 1)^2 = 2x + 1$
因此$dp_i = dp_{i - 1} + 2 \times l_{i - 1} + 1$
$dp_n$为答案

AC代码

#include <iostream>
#include <iomanip>
using namespace std;
const int maxn = 3e5+6;
long double dp[maxn],l[maxn];
int main()
{
    int n;
    string s;
    cin >> n >> s;
    s = " " + s;
    for(int i = 1;i<=n;++i)
    {
        if(s[i] == 'o') {
            dp[i] = dp[i - 1] + l[i - 1] * 2 + 1;
            l[i] = l[i - 1] + 1;
        }
        else if(s[i] == 'x') {
            dp[i] = dp[i - 1];
            l[i] = 0;
        }
        else {
            dp[i] = dp[i - 1] + l[i - 1] + 0.5;
            l[i] = l[i - 1] / 2 + 0.5;
        }
    }
    cout << setiosflags(ios::fixed) << setprecision(4);
    cout << dp[n] << '\n';
}