题解 P6036 【Ryoku 爱学习】

hhoppitree · 2021-01-08 13:24:38 · 题解

题意简述：

求一个期望，经过转化，发现，也就是求：

题目解法：

首先，本题解并不是一篇普通的题解，这是一篇 卡常题解。

做法推荐看 大佬 \rm z7z-Eta 的，本文也是采用 TA 这种做法。

算是对这篇题解的补充吧。

我们发现，在这位大神的题解里，TA 开了许多数组，实际上只要开 w 这一个数组就行了，如果改一改输入格式甚至空间复杂度能做到 \mathcal{O}(1) 的（w 只是个存数据的工具数组）正解：用修改输入文件格式让输入文件成为工具人。

具体点，在 TA 的题解中，递推式要维护数组 t 和 f，但这两个数组递推维护一下就行了。

然后还要用到 p_{i-1},p_{i},p_{i+1}，滚动数组一下就行了，具体见代码。

然后就最优解了（截止本文写作日期 [2021/1/8]）（包括空间吧）。

然后就没有然后了。

还是看代码吧。

哦，如果您要问快的原因，过多的数组调用需要耗费时间。

顺便说些小细节：不要用 \rm cin，读入 w_i 时不要手滑用 \rm \%lf（我开始就是这样所以速度只有 \rm rank\;2，后来看了 \rm rank\;1 的代码才发现，这说明 \rm \%lf 比少开数组重要）

正确代码：

#include<bits/stdc++.h>
using namespace std;
inline int read(){
    int res=0;
    bool zf=0;
    char c;
    while(((c=getchar())<'0'||c>'9')&&c!='-');
    if(c=='-')zf=1;
    else res=c-'0';
    while((c=getchar())>='0'&&c<='9')res=(res<<3)+(res<<1)+c-'0';
    if(zf)return -res;
    return res;
}
int w[100005];
signed main(){
    int n=read();
    double a,b;
    scanf("%lf%lf",&a,&b);
    a=pow(a,b);
    double ans=0,t=0,f=0,p1=0.0,p2,p3;
    for(register int i=1;i<=n;++i){
        scanf("%d",&w[i]);
    }
    scanf("%lf",&p2);
    for(register int i=1;i<=n;++i){
        if(i!=n)scanf("%lf",&p3);else p3=0;
        t=a*p2*t+p2*(1-p1);
        f=a*p2*f+t*w[i];
        ans+=(1-p3)*f;
        p1=p2;p2=p3;
    }
    printf("%lf\n",ans);
    return 0;
}

最后，还是那句话：

如果您没有看懂这篇题解，可以在评论区问我，我将会回答您的问题并且修改这篇题解，使它变得更加通俗易懂，服务更多的 \text{OIer}。
如果您看懂了这篇题解，可以点个赞，使这篇题解的排名上升，服务更多的 \text{OIer}。