题目描述

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

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

次点击要做,成功了就是o,失败了就是x,分数是按combo计算的,连续

个combo就有

分,combo就是极大的连续o

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

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

比如oo?xx的话,?o的话就是oooxx => 9,是x的话就是ooxxx => 4

期望自然就是


 

期望水题..

设\(f[i] \) 表示到i位 的答案

\(c[i]\) 表示到i位的期望长度

考虑转移 \((x+1)^2=x^2+2*x+1 \)

如果是 o

\(f[i]=f[i-1]+2*c[i]+1 \)

\(c[i]=c[i-1]+1 \)

如果是 x

\(f[i]=f[i-1] \)

\(c[i]=0 \)

如果是 ?

\(f[i]=f[i-1]+c[i]+0.5 \)

\(c[i]=c[i-1]*0.5 \)

然后直接滚动

双倍经验,cf235B

比上面的还简单就只放一个代码了

 


说点什么

avatar
  Subscribe  
提醒