首页 > 代码库 > bzoj4318OSU &tyvj1952 Easy
bzoj4318OSU &tyvj1952 Easy
之前做tyvj1952Easy(给定一个序列,每个位置有一定的概率是1或0,求极长连续1的长度平方期望),用的做法是求出“全1子串的期望个数”.假如每一段极长连续1分别长x1,x2,x3…要求的答案为sigma{xi^2},全1子串的期望个数即为sigma{(xi+1)*xi/2},和sigma{xi}的期望(即1的个数的期望)加加减减就出来答案了。
Bzoj4318的题意同上,不过要求立方和的期望。做法是分别考虑每个位置的期望贡献。
即:111后加一个1的贡献为4*4-3*3=7,1111后加一个1的贡献为5*5-4*4=9
也就是说,在一段长度为x的1后面加一个1,贡献为(x+1)^3-x^3=3*x^2+3^x+1,只要算出在每个位置结尾的全1子串的长度期望和长度平方的期望即可。而全1子串的长度平方期望也可以考虑每个1的期望贡献2x+1,由长度的期望推出即可。
那么Tyvj1952也可以分别考虑每个位置的期望贡献(x+1)^2-x^2=2x+1了,只要维护在每个位置结尾的全1子串期望长度即可。
#include<cstdio> #include<cctype> int main(){ int n;scanf("%d",&n); char ch; double x1=0,x2=0,p; for(int i=1;i<=n;++i){ while(ch=getchar(),!isgraph(ch)); if(ch==‘?‘)p=0.5; else if(ch==‘o‘)p=1; else p=0; x2+=p*(2*x1+1); x1=p*(x1+1); } printf("%.4f\n",x2); return 0; }
#include<cstdio> int main(){ int n;scanf("%d",&n); double x1=0,x2=0,x3=0;//结尾连续长度的一次方和平方的期望以及总共的长度立方的期望 double x; for(int i=1;i<=n;++i){ scanf("%lf",&x); x3+=(3*x2+3*x1+1)*x; x2=x*(x2+2*x1+1); x1=x*(1+x1);//x的概率,x1长度变为 x1+1;(1-x)的概率,长度变为0 } printf("%.1f\n",x3); return 0; }
bzoj4318OSU &tyvj1952 Easy
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。