Bzoj3450 Tyvj1952 Easy
2024-10-18 23:30:14
Time Limit: 10 Sec Memory Limit: 128 MB
Submit: 570 Solved: 428
[Submit][Status][Discuss]
Description
某一天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基本上很少呢
HINT
Source
期望DP
/*by SilverN*/
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
using namespace std;
const int mxn=;
char s[mxn];
double len[mxn],ans=;
int n;
int main(){
scanf("%d",&n);
scanf("%s",s+);
for(int i=;i<=n;i++){
if(s[i]=='o'){
len[i]=len[i-]+;
ans+=*len[i]-;
}
else if(s[i]=='x'){len[i]=;}
else{
ans+=(*(len[i-]+)-)/;
len[i]=(len[i-]+)/;
}
}
printf("%.4f\n",ans);
return ;
}
最新文章
- linux下用c实现ls命令
- Linux Shell 通配符、元字符、转义符【转帖】
- [Leetcode][JAVA] Distinct Subsequences
- [转载]使用SoapUI进行负载测试
- The only legal comparisons are between two numbers, two strings, or two dates.
- ActiveNotifications
- hdu1391(Number Steps )
- 每天收获一点点------Hadoop RPC机制的使用
- 搭建Hadoop平台(新手入门)
- Bootstrap 4,“未捕获错误:Bootstrap工具提示需要Tether(http://github.hubspot.com/tether/)”
- 字符串匹配KMP算法详解
- Shell 脚本进阶2
- 【转】Jenkins 二次开发 - Python
- Beta阶段冲刺-2
- Android学习之ListView使用基础
- Zookeeper 系列(四)ZKClient API
- 【转】解决IDEA新建项目名称为红色
- 多表批量导出txt及打压缩包下载
- 关于新塘 M0 M4添加库文件的说明
- 编译openvpn在链接时报tuncfg错误