BZOJ 3450 Easy

news/2025/2/13 21:14:04/

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基本上很少呢

osu是神么,没玩过。。

这是一个期望DP。。

用f[i]表示以i结尾的o串的长度,那么当ch=='x' 时 p=0,ch=='o'时p=1,当ch=='?'时,p=0.5 然后f[i]=(f[i-1]+1)*p,再用一个数组g[i],表示从1到i每段o串长度平方的期望。

那么 (x+1)^2=x^2+2*x+1,x^2对应的就是g,那么g的转移就是g[i]=g[i-1]+(2*f[i-1]+1)*p;

之所以乘p,是因为g表示的前缀的答案总和,而后面两项乘是因为能否增加答案是概率事件。所以O(n)递推就好了,空间复杂度O(1),滚动起来就好了。

#include <cstring>
#include <stdio.h>
double f1[2],f2;
int op;int main(){int n;scanf("%d",&n);for(int i=1;i<=n;i++){char ch=getchar();while(ch!='o'&&ch!='x'&&ch!='?')ch=getchar();double x;if(ch=='o')x=1.0;if(ch=='x')x=0;if(ch=='?')x=0.5;f1[op^1]=(f1[op]+1)*x;f2=f2+(2*f1[op]+1)*x;op^=1;}printf("%.4f\n",f2);
}




http://www.ppmy.cn/news/201295.html

相关文章

hdu3450

开始看觉得是dp&#xff0c;复杂度O(n^2)会超时就没做&#xff0c;应该是用线段树或者树状数组&#xff0c;加上离散化和二分法优化。 你需要一个dp[i]数组&#xff0c;存储的是以i为结尾的个数&#xff0c;结果就是dp[]之和. 离散化的部分是用一个离散化结构体&#xff0c;最…

3450

/* KMP来做532ms */// include file #include <cstdio> #include <cstdlib> #include <cstring> #include <cmath> #include <cctype> #include <ctime>#include <iostream> #include <sstream> #include <fstream> #in…

BZOJ3450 Easy

原题链接&#xff1a;http://www.lydsy.com/JudgeOnline/problem.php?id3450 Easy Description 某一天WJMZBMR在打osu~~~但是他太弱逼了&#xff0c;有些地方完全靠运气:( 我们来简化一下这个游戏的规则 有n次点击要做&#xff0c;成功了就是o&#xff0c;失败了就是x&…

tjut 3450

/*分析:每次寻找以a[i]结尾的子序列能有多少个,只需要寻找a[i]-d和a[i]d之之间数结尾的子序列 的全部个数,然后把a[i]直接放在那些数后面即可 找寻和更新都是用树状数组 */ #include <iostream> #include <cstdio> #include <cstdlib> #include …

POJ 3450题解

题目连接 POJ 3450 Corporate Identity 思路 先用后缀数组处理出height数组&#xff0c;然后我们二分最长公共子串的长度&#xff0c;然后再height中找大于这个长度并且不在一个字符串的个数&#xff0c;如果等于n则返回true否则返回false即可。 前期一直TLE不知道为何&…

hdu 3450

吐吐槽吧&#xff1a;本来思路完全对了&#xff0c;但是那个二分查找搞错了&#xff0c;我还以为一个就可以了&#xff0c;结果查找上界和下界分别要一个查找函数&#xff08;WA时就看了一下别人的代码&#xff0c;发现别人都是用两个查找函数的&#xff0c;模仿别人写的查找函…

poj3450

Corporate Identity http://poj.org/problem?id3450 Description Beside other services, ACM helps companies to clearly state their “corporate identity”, which includes company logo but also other signs, like trademarks. One of such companies is Internet Bu…

HDU 3450(树状数组)

题目链接:HDU 3450 题目大意: 求长度大于等于且相邻差值不超过d的子序列的个数. 分析: 没什么好说的水题,就是没给a的范围真的天坑. 以下是代码: #include <set> #include <map> #include <stack> #include <queue> #include <vector> #inclu…