首页 > 代码库 > bzoj4318 OSU!&&tyvj1952 Easy
bzoj4318 OSU!&&tyvj1952 Easy
链接:http://www.lydsy.com/JudgeOnline/problem.php?id=4318,http://www.tyvj.cn/p/1952
其实这两个题题意差不多,游戏都一样(一样吗?计分方式都不一样),都是连续的数值价值会变为多次方,只不过一个是变成三次方,一个是变成二次方。
对OSU!分析,增加一个连续的o做出的贡献是(x+1)3-x3=3x2+3x+1,于是我们只需要维护期望个数之和、平方和、立方和即可。
同理,Easy中增加一个o的贡献为(x+1)2-x2=2x+1,于是我们只要维护期望个数及其平方和即可。
注意一点:平方期望不等于期望的平方。
1 #include<iostream> 2 #include<cstdio> 3 #include<algorithm> 4 #include<cstring> 5 using namespace std; 6 const int maxn=100005; 7 int n; 8 double a[maxn],f1[maxn],f2[maxn],f3[maxn]; 9 int haha() 10 { 11 scanf("%d",&n); 12 for(int i=1;i<=n;i++)scanf("%lf",&a[i]); 13 f1[0]=0;f2[0]=0;f3[0]=0; 14 for(int i=1;i<=n;i++) 15 { 16 f1[i]=(f1[i-1]+1)*a[i]; 17 f2[i]=(f2[i-1]+2*f1[i-1]+1)*a[i]; 18 f3[i]=f3[i-1]+(3*f2[i-1]+3*f1[i-1]+1)*a[i]; 19 } 20 printf("%0.1lf\n",f3[n]); 21 } 22 int sb=haha(); 23 int main(){;}
OSU!
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 using namespace std; 6 const int maxn=300005; 7 int n; 8 double f1[maxn],f2[maxn],a[maxn]; 9 char s[maxn]; 10 int haha() 11 { 12 scanf("%d",&n); 13 scanf("%s",s+1); 14 for(int i=1;i<=n;i++) 15 switch(s[i]) 16 { 17 case ‘o‘:a[i]=1.0;break; 18 case ‘x‘:a[i]=0.0;break; 19 case ‘?‘:a[i]=0.5;break; 20 } 21 f1[0]=0;f2[0]=0; 22 for(int i=1;i<=n;i++) 23 { 24 f1[i]=(f1[i-1]+1)*a[i]; 25 f2[i]=f2[i-1]+(2*f1[i-1]+1)*a[i]; 26 } 27 printf("%0.4lf\n",f2[n]); 28 } 29 int sb=haha(); 30 int main(){;}
Easy
bzoj4318 OSU!&&tyvj1952 Easy
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。