用asp做网站需要什么软件,平台推广是做什么的,wordpress个人模板下载,企业网站建设教程视频题干#xff1a;
某一天WJMZBMR在打osu~~~但是他太弱逼了#xff0c;有些地方完全靠运气:( 我们来简化一下这个游戏的规则 有n次点击要做#xff0c;成功了就是o#xff0c;失败了就是x#xff0c;分数是按comb计算的#xff0c;连续a个comb就有a*a分#xff0c;comb就…题干
某一天WJMZBMR在打osu~~~但是他太弱逼了有些地方完全靠运气:( 我们来简化一下这个游戏的规则 有n次点击要做成功了就是o失败了就是x分数是按comb计算的连续a个comb就有a*a分comb就是极大的连续o。 比如ooxxxxooooxxx分数就是2*24*441620。 Sevenkplus闲的慌就看他打了一盘有些地方跟运气无关要么是o要么是x有些地方o或者x各有50%的可能性用?号来表示。 比如oo?xx就是一个可能的输入。 那么WJMZBMR这场osu的期望得分是多少呢 比如oo?xx的话?是o的话就是oooxx 9是x的话就是ooxxx 4 期望自然就是(49)/2 6.5了
Input 第一行一个整数n表示点击的个数 接下来一个字符串每个字符都是ox中的一个
Output
一行一个浮点数表示答案 四舍五入到小数点后4位 如果害怕精度跪建议用long double或者extended
Sample Input
4
????Sample Output
4.1250n300000
osu很好玩的哦
WJMZBMR技术还行(雾),x基本上很少呢
题目大意
解题报告
两种方式要么直接dp要么直接计算。
这题如果dp的话状态是n*2的。所以考虑直接计算。
根据期望的线性性我们可以分别计算每个字符的期望贡献分值然后求和
我们观察可以得到如果在一个长为x的o串之后接上一个o那么答案加上了也就是说每个字符的贡献分值和它前面的期望o串长度有关系。
分类讨论记录每个元素的贡献。
ol[i]l[i−1]1dp[i] l[i−1]∗21。注意这里的贡献时长度*21而不是直接dp[i-1]*21
?(l[i]l[i−1]1)/2dp[i] (l[i−1]∗21)2
x: l[i]0,dp[i]0;
AC代码
#includecstdio
#includeiostream
#includealgorithm
#includequeue
#includemap
#includevector
#includeset
#includestring
#includecmath
#includecstring
#define F first
#define S second
#define ll long long
#define pb push_back
#define pm make_pair
using namespace std;
typedef pairint,int PII;
const int MAX 3e5 5;
int n;
char s[MAX];
double dp[MAX],l[MAX];
int main()
{cinn;cins1;for(int i 1; in; i) {if(s[i] x) dp[i] 0,l[i] 0;;if(s[i] o) dp[i] l[i-1]*2 1,l[i] l[i-1] 1; if(s[i] ?) dp[i] 0.5*(l[i-1]*21),l[i](l[i-1]1)/2;}double ans 0;for(int i 1; in; i) ans dp[i];printf(%.4f\n,ans);return 0 ;
}
