Bzoj 3450: Tyvj1952 Easy (期望)
Bzoj 3450: Tyvj1952 Easy
这里放上题面,毕竟是个权限题(洛谷貌似有题,忘记叫什么了)
Time Limit: 10 Sec Memory Limit: 128 MB
Submit: 1031 Solved: 772
Description
某一天WJMZBMR在打osu~~~但是他太弱逼了,有些地方完全靠运气:(
我们来简化一下这个游戏的规则
有n次点击要做,成功了就是o,失败了就是x,分数是按comb计算的,连续a个comb就有aa分,comb就是极大的连续o。
比如ooxxxxooooxxx,分数就是22+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
我们都爱GYZ杯
题解
分为三种情况考虑
由于此题期望计算的是长度的平方\(l\)
\(s[i] == 'x'\)时
\(l\)变成\(0\),且对答案没有贡献
\(s[i] == 'o'\)时
\(l\)长度\(+1\),对答案的贡献:\(l^2\) → \((l + 1) ^2 = l^2 + 2 * l + 1\)对答案的贡献为\(2 * l + 1\)
\(s[i] == '?'\)时
有\(1/2\)的几率\(l = 0\)或者\(l + 1\),期望长度为\((l + 1) / 2\)所以长度变成\((l+1)/2\)
对答案的贡献,只有\(1/2\)的概率是跟\(s[i] == 'x'\)一样,所以贡献时\(s[i] == 'x'\)的一半,即\((2 * l + 1 )/ 2\)
更新\(l,ans\)的顺序是一个坑点.
#include <iostream>
#include <cstring>
#include <cstdio>
const int maxN = 300000 + 7;
using namespace std;
int L,len;
char s[maxN];
int main(int argc, char const *argv[])
{
scanf("%d",&len);
scanf("%s",s + 1);
double ans = 0,l = 0;
for(int i = 1;i <= len;++ i) {
if(s[i] == 'o') {ans += 2.0 * l + 1;l ++;}
if(s[i] == 'x') {l = 0;}
if(s[i] == '?') {ans += (2.0 * l + 1) / 2.0;l = (l + 1) / 2;}
}
printf("%.4lf", ans);
return 0;
}
最新文章
- jface的CheckboxTreeViewer实现单选
- HTML5-WebSocket技术学习(1)
- [MacOS] xcrun: error: active developer path (";/Volumes/Xcode/Xcode6-Beta.app/Contents/Developer";) does not exist, use xcode-select to change
- debian完整部署 Nginx + uWSGI + Django
- mybaits3.2.8 别名包扫描通配符
- 史上最强Android 开启照相或者是从本地相册选中一张图片以后先裁剪在保存并显示的讲解附源码
- 面向对象15.3String类-常见功能-转换
- C语言_结构体变量指针做函数参数的使用案例
- 非常适用的Sourceinsight插件,提高效率【强力推荐】
- ArcGis Python脚本——将细碎小面合并到相邻的面积最大的面
- k64 datasheet学习笔记25--Multipurpose Clock Generator (MCG)
- Centos 7.6搭建LAMP,部署zabbix监控环境
- MySQL dump文件导入
- leaflet入门(三)使用GeoJSON创建矢量图形
- Redis学习之路(003)- hiredis安装及测试
- CREATESTRUCT cs 结构体
- linux下安装evernote国际版
- PHP 代码优化测试【Benchmark数据测试】
- 仿阿里云后台管理界面模板html源码——后台
- Python 小知识点(10)--异常结构记录