BZOJ 4318: OSU!

Description

osu 是一款群众喜闻乐见的休闲软件。 

我们可以把osu的规则简化与改编成以下的样子: 

一共有n次操作,每次操作只有成功与失败之分,成功对应1,失败对应0,n次操作对应为1个长度为n的01串。在这个串中连续的 X个1可以贡献X^3 的分数,这x个1不能被其他连续的1所包含(也就是极长的一串1,具体见样例解释) 

现在给出n,以及每个操作的成功率,请你输出期望分数,输出四舍五入后保留1位小数。 

Input

第一行有一个正整数n,表示操作个数。接下去n行每行有一个[0,1]之间的实数,表示每个操作的成功率。 

Output

只有一个实数,表示答案。答案四舍五入后保留1位小数。 

Sample Input

3 0.5 0.5 0.5

Sample Output

6.0

HINT

【样例说明】 

000分数为0,001分数为1,010分数为1,100分数为1,101分数为2,110分数为8,011分数为8,111分数为27,总和为48,期望为48/8=6.0 

N<=100000

Source

考虑递推,用立方差公式转移,同时要维护E(x^3),E(x^2),E(x),E(1)

考虑第i次操作,设操作前末尾最长的1长度为x。

(1)如果操作失败,贡献为0;

(2)如果操作成功,贡献为(x+1)^3 - x^3

那么期望为(1 - pi) * 0 + pi * ((x+1)^3 - x^3)

化简一下答案为pi * ((x+1)^3 - x^3)。

注意我们并不知道x^3具体是多少,但是我们可以算出x^3的期望是多少,而且根据期望我们知道这样算出来一定是我们想要的结果。

假设我们已经知道E(x^3),如何计算E((x + 1)^3)?考虑递推。

E(x^3) = 0^3 * P(x = 0) + 1^3 * P(x = 1) + ... + maxl^3 * P(x = maxl)

E((x + 1)^3)  = 1^3 * P(x = 0) + 2^3 * P(x = 1) + ... + (maxl + 1)^3 * P(x = maxl)

将第二个式子用二项式定理展开,然后将第一个式子带入,可以得到

E((x + 1)^3) = E(x^3) + 3E(x^2) + 3E(x) + E(1)

那么我们同样递推维护E(x^2),E(x),E(1)就好了。

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<cmath>
 5 #include<algorithm>
 6 #include<vector>
 7 using namespace std;
 8 const int MAXN=100001;
 9 const int maxn=0x7fffff;
10 void read(int &n)
11 {
12     char c='+';int x=0;bool flag=0;
13     while(c<'0'||c>'9')
14     {c=getchar();if(c=='-')flag=1;}
15     while(c>='0'&&c<='9')
16     {x=x*10+c-48;c=getchar();}
17     flag==1?n=-x:n=x;
18 }
19 double f[MAXN],g[MAXN],dp[MAXN];
20 int main()
21 {
22     int n;
23     read(n);
24     for(int i=1;i<=n;i++)
25     {
26         double now;
27         scanf("%lf",&now);
28         f[i]=now*(f[i-1]+1);
29         g[i]=now*(g[i-1]+f[i-1]*2+1);
30         dp[i]=dp[i-1]+now*(g[i-1]*3+f[i-1]*3+1);
31     }
32     printf("%.1lf",dp[n]);
33     return 0;
34 }

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏钱塘大数据

【干货】十大必须掌握的基础实用算法及其讲解

作者:CSDN大数据 算法一:快速排序算法 快速排序是由东尼·霍尔所发展的一种排序算法。在平均状况下,排序 n 个项目要Ο(nlogn) 次比较。在最坏状况下...

28860
来自专栏潇涧技术专栏

Python Algorithms - C3 Counting 101

原书主要介绍了一些基础数学,例如排列组合以及递归循环等,但是本节只重点介绍计算算法的运行时间的三种方法

9840
来自专栏程序员互动联盟

程序员必须要掌握的十大经典算法

算法一:快速排序算法 快速排序是由东尼·霍尔所发展的一种排序算法。在平均状况下,排序 n 个项目要Ο(n log n)次比较。在最坏状况下则需要Ο(n2)次比较...

444130
来自专栏潇涧技术专栏

Problem: Delete Number Problem

这题可以使用贪心策略,每次从高位向低位数,删除高位比低位数字小的那位上的数字,直到删除了k位之后,得到的数字肯定是最大值。

9620
来自专栏编程之旅

数据结构——最小生成树(C++和Java实现)

快要一整个月没有更新博客了,之前的几周每周都想着要写,但是最后时间还是排不开,最近的状态是一直在写代码,一直在怼工作的需求,顺便刷刷算法题,国庆则是没心没肺的玩...

37640
来自专栏章鱼的慢慢技术路

笔试常考题型之时间复杂度

54860
来自专栏数据结构与算法

BZOJ 4318: OSU!

Description osu 是一款群众喜闻乐见的休闲软件。  我们可以把osu的规则简化与改编成以下的样子:  一共有n次操作,每次操作只有成功与失败之分...

30750
来自专栏Java 源码分析

枚举

​ 枚举就是尝试所有的可能性,尤其是当我们在确定一个问题是不是的这一类问题中尤其有用,例如说给一堆数,让我我们判断他们是不是素数,或者素数的数量的时候,这...

32360
来自专栏Python小屋

最快的组合数算法之Python实现

原理:以Cni(8,3)为例,按定义式将其展开为(8*7*6*5*4*3*2*1)/(3*2*1)/(5*4*3*2*1),对于8到6之间的数,分子上出现一次而...

39470
来自专栏章鱼的慢慢技术路

笔试常考题型之时间复杂度

16930

扫码关注云+社区

领取腾讯云代金券