首页 > 代码库 > Codeforces B Let's Play Osu!
Codeforces B Let's Play Osu!
题目大意
现在有一个长度为n的只有ox组成的字符串。第i个位置上有pi的概率出现o，(1-pi)的概率出现x，如果有一段长度为L的全是o的部分，贡献就是L^2。求最后贡献的期望。
题解
这题有点思博啊……首先我们对于一个确定的串，从前往后扫，设当前o的长度为L，如果下一个是o的话，那么贡献就会增加(L+1)^2-L^2=2L+1.这样的话从前往后扫，我们维护两个值，一个是当前期望的o的长度now，一个是期望贡献ans，这样ans+=(2*now+1)*pi,now=(now+1)*pi
1 #include<iostream> 2 #include<algorithm> 3 #include<cstdio> 4 #include<cstdlib> 5 #include<cstring> 6 using namespace std; 7 int n; 8 double p,now,ans; 9 int main() 10 { 11 ans=0.0;now=0.0; 12 scanf("%d",&n); 13 for(int i=1;i<=n;i++) 14 { 15 cin>>p; 16 ans+=(2*now+1)*p;now=(now+1)*p; 17 } 18 printf("%.10f",ans); 19 return 0; 20 }
Codeforces B Let's Play Osu!
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。