题目背景

原 维护队列 参见P1903

题目描述

某一天\(WJMZBMR\)在打\(osu~~~\)但是他太弱逼了，有些地方完全靠运气:(

我们来简化一下这个游戏的规则

有\(n\)次点击要做，成功了就是\(`o`\)，失败了就是\(`x`\)，分数是按\(combo\)计算的，连续\(a\)个\(combo\)就有\(a\times a\)分，\(combo\)就是极大的连续\(`o`\)。

比如\(`ooxxxxooooxxx`\)，分数就是\(2 \times 2 + 4 \times 4 = 4\) +16=20。

\(Sevenkplus\)闲的慌就看他打了一盘，有些地方跟运气无关要么是\(`o`\)要么是\(`x`\)，有些地方\(`o`\)或者\(`x`\)各有\(50\%\)的可能性，用\(`?`\)号来表示。

比如\(`oo?xx`\)就是一个可能的输入。 那么\(WJMZBMR\)这场\(osu\)的期望得分是多少呢？

比如\(`oo?xx`\)的话，\(`?`\)是\(`o`\)的话就是\(`oooxx` => 9\)，是\(x\)的话就是\(`ooxxx` => 4\)

期望自然就是\((4+9)/2 =6.5\)了

输入输出格式

输入格式：

第一行一个整数\(n\)，表示点击的个数

接下来一个字符串，每个字符都是\(`o`,`x`,`?`\)中的一个

输出格式：

一行一个浮点数表示答案

四舍五入到小数点后\(4\)位

如果害怕精度跪建议用\(long double\)或者\(extended\)

输入输出样例

输入样例#1：

4
????

输出样例#1：

4.1250

说明

\(osu\)很好玩的哦

\(WJMZBMR\)技术还行(雾),\(x\)基本上很少呢

思路：用dp数组表示期望值，用f数组表示到某位置时连续的o的个数。然后进行分类讨论：
1.当\(s[i]\)为\(’o’\)时，\(dp[i]=dp[i-1]+2×f[i-1]+1,f[i]=f[i-1]+1\);
因为\((x+1)^2=x^2+2 \times x + 1\)
2.当\(s[i]\)为\(‘x’\)时，\(dp[i]=dp[i-1],f[i]=0\);
3.\(else\) 期望和的平均值就好咯，因为概率都是\(0.5\)，所以都乘\(0.5\)相加就可以了。

代码：

#include<cstdio>
#include<cstring>
#define dl double
#define maxn 1000007
using namespace std;
int n;
dl dp[maxn],f[maxn];
char s[maxn];
int main() {
  scanf("%d%s",&n,s+1);
  int len=strlen(s+1);
  for(int i=1;i<=len;++i) {
    if(s[i]=='x') dp[i]=dp[i-1],f[i]=0;
    else if(s[i]=='o') dp[i]=dp[i-1]+2*f[i-1]+1,f[i]=f[i-1]+1;
    else dp[i]=dp[i-1]+f[i-1]+0.5,f[i]=(f[i-1]+1)*0.5;
  }
  printf("%0.4lf\n",dp[len]);
  return 0;
}