首页 > 代码库 > BZOJ 3450 Tyvj1952 Easy(期望)
BZOJ 3450 Tyvj1952 Easy(期望)
【题目链接】 http://www.lydsy.com/JudgeOnline/problem.php?id=3450
【题目大意】
给出一个字符串,包含o,x和?,一个字符串的得分为
每段连续的o的长度的平方和,现在在?处填上o或者x,问期望得分
【题解】
对于连续的一段,我们对平方这个计算方法进行拆分
1^2=1, 2^2=1+3, 3^3=1+3+5, ……
我们发现每次如果是o,增加的是最后连续o的数量的两倍+1,
那么我们按照这个方法,记录连续o的期望,同时计算得分期望即可。
【代码】
#include <cstdio>#include <algorithm>using namespace std;const int N=300010;char s[N];double dp[N],d[N];int n; int main(){ scanf("%d %s",&n,s+1); for(int i=1;i<=n;i++){ if(s[i]==‘x‘){dp[i]=dp[i-1];d[i]=0;} else if(s[i]==‘o‘){dp[i]=dp[i-1]+2*d[i-1]+1;d[i]=d[i-1]+1;} else{dp[i]=dp[i-1]+d[i-1]+0.5;d[i]=(d[i-1]+1)/2;} }printf("%.4lf",dp[n]); return 0;}
BZOJ 3450 Tyvj1952 Easy(期望)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。