[Tyvj 1952] Easy
2024-08-30 10:17:38
P1952 Easy时间: 1000ms / 空间: 131072KiB / Java类名: Main描述
某一天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了输入格式
第一行一个整数n,表示点击的个数
接下来一个字符串,每个字符都是ox?中的一个输出格式
一行一个浮点数表示答案
四舍五入到小数点后4位
如果害怕精度跪建议用long double或者extended测试样例
输入
4
????输出
4.1250
备注
osu很好玩的哦
WJMZBMR技术还行(雾),x基本上很少呢
确实是道水题w
保存期望得分和期望combo后对于每个字符分三种情况递推即可w
对于$'o'$直接期望combo$+=1$,期望分数加上平方差
对于$'x'$直接期望combo$=0$,期望分数等于上一次的分数
对于$'?'$期望combo更新为上次的combo$+1$后再$\times 0.5$,期望分数加上平方差的一半
但是非常坑爹的是题面没有指定数据范围(╯‵□′)╯︵┻━┻
RE了3次后用500k的数据范围A掉了这题QAQ
袋马如下
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm> const int MAXN=; int n;
char buf[MAXN];
double pt[MAXN];
double cb[MAXN]; int main(){
scanf("%d",&n);
scanf("%s",buf+);
for(int i=;i<=n;i++){
if(buf[i]=='o'){
pt[i]=pt[i-]+cb[i-]*+1.0;
cb[i]=cb[i-]+1.0;
}
else if(buf[i]=='x'){
pt[i]=pt[i-];
cb[i]=;
}
else{
pt[i]=pt[i-]+cb[i-]+0.5;
cb[i]=(cb[i-]+)/2.0;
}
}
(n+)^=n^+2n+
(n+)^=n^+3x^+3x+
printf("%.4lf\n",pt[n]);
return ;
}
Backup
吼啦图包时间
最新文章
- Python全栈开发day7
- C语言中的参数传递
- Apache 常用伪静态配置
- 备份数据库的时候设置 BufferCount 选项不正确导致 out of memory 的情况
- 【转】Android横竖屏切换问题
- uva10245-The Closest Pair Problem(平面上的点分治)
- objective-c 关键字和概念
- CentOS + EPEL YUM源地址
- cuda编程学习4——Julia
- mysql CMD命令
- SQLAlchemy基础操作一
- golang - gob与rpc
- 广师大学习笔记之文本统计(jieba库好玩的词云)
- Spring事务mysql不回滚:mysql引擎修改
- 机器学习-随机梯度下降(Stochastic gradient descent)
- session删除
- 性能测试十七:liunx下jmeter结果报表、html报表
- 〖Linux〗穿越城墙之后,直接连接国内网站的路由配置
- javascript数组元素的添加、删除与插入以及参数数组的使用
- linux inode cheat sheet