题目背景
原 维护队列 参见 P1903
题目描述
某一天 WJMZBMR 在打 osu,但是他太弱了,有些地方完全靠运气:(。
我们来简化一下这个游戏的规则
有 $n (n\le3\times10^5)$ 次点击要做,成功了就是 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$($n\le3\times10^5$),表示点击的个数
接下来一个字符串,每个字符都是 o
,x
,?
中的一个
输出格式
一行一个浮点数表示答案
四舍五入到小数点后 $4$ 位
如果害怕精度跪建议用 long double 或者 extended。
输入输出样例 #1
输入 #1
1 |
|
输出 #1
1 |
|
题解
我们记期望连续的 $o$ 个数为 $l$,$f(i)$ 表示以第 $i$ 个字符结尾的期望得分。
当当前字符为 o
时,
$$ f(i) = f(i-1) + [(l + 1)^2 - l^2] = f(i-1) + 2 \times l + 1, l = l + 1 $$
当当前字符为 x
时,
$$ f(i) = f(i-1), l = 0 $$
当当前字符为 ?
时,把以上两种转移乘以 $\frac{1}{2}$ 并相加即可,
$$ f(i) = f(i-1) + \frac{[(l + 1)^2 - l^2] + 0}{2} = f(i-1) + l + 0.5, l = \frac{l + 1}{2} $$