首页 > 代码库 > BZOJ 4318: OSU!
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
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 }
BZOJ 4318: OSU!
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。