题意简述:
求一个期望,经过转化,发现,也就是求:
$$\sum_ {1\le l\le r\le n}a^ {r-l}(1-p_ {l-1})(1-p_ {r+1})\prod\limits_ {i=l}^ {r}p_ i\sum\limits_ {i=l}^ {r}w_ i$$
题目解法:
首先,本题解并不是一篇普通的题解,这是一篇 卡常题解。
做法推荐看 [链接登录后可见],本文也是采用 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}$。