洛谷 P1365 WJMZBMR打osu! / Easy
洛谷 Easy
2023-09-11 14:20:14 时间
洛谷 P1365 WJMZBMR打osu! / Easy
题目背景
原 维护队列 参见P1903
题目描述
某一天WJMZBMR在打osu~~~但是他太弱逼了,有些地方完全靠运气:(
我们来简化一下这个游戏的规则
有nn次点击要做,成功了就是o
,失败了就是x
,分数是按combo计算的,连续aa个combo就有a\times aa×a分,combo就是极大的连续o
。
比如ooxxxxooooxx
x,分数就是2 \times 2 + 4 \times 4 = 4 +16=202×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(4+9)/2=6.5了
输入格式
第一行一个整数n(n\le3\times10^5)n(n≤3×105),表示点击的个数
接下来一个字符串,每个字符都是o
,x
,?
中的一个
输出格式
一行一个浮点数表示答案
四舍五入到小数点后44位
如果害怕精度跪建议用long double或者extended
题解:
与P1654OSU!的思路基本一样:
分类讨论去求即可。
代码:
#include<cstdio>
using namespace std;
const int maxn=3*1e5+10;
int n;
char s[maxn];
double dp[maxn],f[maxn];
int main()
{
scanf("%d%s",&n,s+1);
for(int i=1;i<=n;i++)
{
if(s[i]=='o')
f[i]=f[i-1]+1;
if(s[i]=='x')
f[i]=0;
if(s[i]=='?')
f[i]=(f[i-1]+1)*0.5;
}
for(int i=1;i<=n;i++)
{
if(s[i]=='o')
dp[i]=dp[i-1]+(2*f[i-1]+1);
if(s[i]=='x')
dp[i]=dp[i-1];
if(s[i]=='?')
dp[i]=dp[i-1]+(2*f[i-1]+1)*0.5;
}
printf("%.4lf",dp[n]);
return 0;
}
相关文章
- Java实现 洛谷 P6183 [USACO10MAR]The Rock Game S(DFS)
- Java实现 洛谷 P1583 魔法照片
- Java实现 洛谷 P1023 税收与补贴问题
- Java实现 洛谷 P1055 ISBN号码
- Java实现 洛谷 P1980 计数问题
- Java实现 洛谷 P1008 三连击
- Java实现 洛谷 P1028 数的计算
- Java实现 洛谷 P1618 三连击(升级版)
- Java实现 洛谷 P1217 [USACO1.5]回文质数 Prime Palindromes
- java实现 洛谷 P1014 Cantor表
- Java实现 洛谷 P1103 书本整理
- (Java实现)洛谷 P1164 小A点菜
- (Java实现) 洛谷 P1319 压缩技术
- Java实现 洛谷 P1064 金明的预算方案
- 【洛谷】P5318 【深基18.例3】查找文献
- Vijos、洛谷——NASA的食物计划(java解法)
- Vijos、洛谷——采药(部分背包问题)(java实现)