[bzoj3450]Tyvj1952Easy
2024-10-21 19:30:23
瓜皮期望真是弱成渣。。
完全不理解的感觉qwq。。。题面%了一发千古神犇WJMZBMR哈~
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
HINT
n<=300000
osu很好玩的哦
WJMZBMR技术还行(雾),x基本上很少呢
WJMZBMR技术还行(雾),x基本上很少呢
所以说这个题题意很好理解(我都没玩过osu哈)。
考虑已知前面连续的o有L个,那么当前这个如果是o,贡献为2*L+1,并使L++。如果是x,贡献为0,并使L=0。
如果是?呢,那么一半概率是o,另一半是x。然后就是蒟蒻不懂的地方啦,这块的贡献可以直接视为$\frac{1}{2}\left ( 2L+1 \right )+\frac{1}{2}\times 0$,并使$L=\frac{1}{2}\left ( L+1 \right )+\frac{1}{2}\times 0$。
如果知道这里的可行性就水爆了对叭。。。
代码说明了一切嗷嗷嗷
#include<cstdio>
#define N 300100
using namespace std;
int main(){
int n;scanf("%d",&n);
char s[N];
scanf("%s",s+);
double f1=,f2=;
for(int i=;i<=n;i++){
double p;
if(s[i]=='o')p=;
else if(s[i]=='x')p=;
else p=0.5;
f2+=(*f1+)*p;
f1=(f1+)*p;
}
printf("%.4lf\n",f2);
return ;
}
最新文章
- [翻译]Apache Spark入门简介
- [OpenCV] Samples 04: contours2
- pay-as-you-go
- linux基础-第十四单元 Linux网络原理及基础设置
- 【API】短信通106端口验证短信的实现
- YII获取刚插入数据的id主键
- Programs vs. processes
- ZOJ 1037 Gridland
- UISwitch swift
- 在Linux中创建静态库和动态库
- JSP---JavaBean的使用-jsp:useBean标签相关
- laydate JS日期插件
- Linux运维工程师面试
- C#界面设计疑问
- Sqlite 帮助类 SQLiteHelper
- [自用]多项式类数学相关(定理&;证明&;板子)
- Scss - 简单笔记
- centos7下使用mysql离线安装包安装mysql5.7
- java设计模式-State模式
- HDOJ 2013 蟠桃记