M_sea

洛谷1654 OSU!
LuoguBZOJ分析考虑多了一个 $1$ 分数会增加多少。通过暴力拆式子/二项式定理可以得到 $(x+1)^3=...
扫描右侧二维码阅读全文
09
2019/07

洛谷1654 OSU!

Luogu

BZOJ

分析

考虑多了一个 $1$ 分数会增加多少。

通过暴力拆式子/二项式定理可以得到 $(x+1)^3=x^3+3x^2+3x+1$ ,也就是说增加了 $3x^2+3x+1$ 。

设 $f[i]$ 表示前 $i$ 次操作 $x$ 的期望值,$g[i]$ 表示前 $i$ 次操作 $x^2$ 的期望值。

于是有 $f[i]=(f[i-1]+1)\times p[i]$ , $g[i]=(g[i-1]+2\times f[i-1]+1)\times p[i]$ 。

设 $ans[i]$ 表示前 $i$ 次操作的答案,那么有 $ans[i]=(ans[i-1]+3\times g[i-1]+3\times f[i-1]+1)\times p[i]+ans[i-1]\times(1-p[i])$ 。

把这个式子化简得到 $ans[i]=ans[i-1]+(3\times g[i-1]+3\times f[i-1]+1)\times p[i]$ 。

代码

// ===================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// ===================================
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=100000+10;

int n;
double p[N],f[N],g[N],h[N];

int main() {
    n=read();
    for (re int i=1;i<=n;++i) scanf("%lf",&p[i]);
    for (re int i=1;i<=n;++i) f[i]=(f[i-1]+1)*p[i];
    for (re int i=1;i<=n;++i) g[i]=(g[i-1]+2*f[i-1]+1)*p[i];
    for (re int i=1;i<=n;++i) h[i]=h[i-1]+(3*g[i-1]+3*f[i-1]+1)*p[i];
    printf("%.1lf\n",h[n]);
    return 0;
}
最后修改:2019 年 07 月 09 日 08 : 24 PM

发表评论