本文最后更新于 2308 天前,其中的信息可能已经有所发展或是发生改变。
内容纲要
题解
由于给定序列,$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';
}