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

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

    有n次点击要做，成功了就是o，失败了就是x，分数是按comb计算的，连续a个comb就有a*a分，comb就是极大的连续o。

    比如ooxxxxooooxxx，分数就是2*2+4*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了

Input

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

    接下来一个字符串，每个字符都是ox？中的一个

Output

    一行一个浮点数表示答案

    四舍五入到小数点后4位

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

Sample Input

    4

    ????

Sample Output

    4.1250

    n<=300000

    osu很好玩的哦

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

 

题意 ： 给你一个长度为 n 的串，当有连续的 o  出现时你可以得到的得分为 长度的平方， ? 表示此位置可能是 o ， 也可能是 x

思路分析 ： 我们考虑一个串当前的长度为 L , 那么增加一个字母后长度变为 (L+1) * P ， 期望增加的得分为 (L+1)^2 - L^2 , 即 dp[i-1] + (2 * l[i-1] + 1) * P

代码示例 ： （未测试）

#include 
     
      using namespace std;const int maxn = 3e5+5;int n;double l[maxn], dp[maxn];char s[maxn];int main () {    cin >> n;    scanf("%s", s+1);    for(int i = 1; i <= n; i++){        if (s[i] == 'x') l[i] = 0, dp[i] = dp[i-1];        else if (s[i] == 'o') l[i] = l[i-1]+1, dp[i] = dp[i-1]+2*l[i-1]+1;        else l[i] = (l[i-1]+1.0)/2, dp[i] = dp[i-1]+(2*l[i-1]+1)/2.0;    }    printf("%.4lf\n", dp[n]);    return 0;}