(\)
(Description)
一共进行(N)次操作，生成一个长度为(N)的(01)序列，成功对应(1)，失败对应(0)，已知每一次操作的成功率(p_i)。
在这个序列中连续且极长的(X)个(1)可以贡献(X^2)的分数，求期望总分。
- (Nin [1,10^5])
(\)
(Solution)
-
考虑增量的思路很可以啊。长度平方的期望并不等于期望长度的平方。所以需要直接考虑长度平方的期望变化。
-
当长度从(X)增加到(X+1)，(Delta X^2=(X+1)^2-X^2=2X+1)，所以维护答案只需要考虑长度的期望。
-
考虑一次的答案期望(x_1[i])表示到第(i)个位置为止的长度期望，有(x_1[i]=(x_1[i-1]+1) imes p_i)，代表继承上一个为止的期望长度会(+1)，但保证第(i)位合法，需要乘上(p_i)。
-
然后到第(i)个位置的平方期望就可以转移自第(i-1)个位置，注意增量是有概率的。
[ans[i]=ans[i-1]+(2x_1[i]+1) imes p_i ]
(\)
(Code)
#include<cmath>
#include<cstdio>
#include<cctype>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define N 300010
#define R register
#define gc getchar
using namespace std;
int n;
double p[N],x1[N],ans[N];
inline double calc(char x){
return x=='x'?0.0:(x=='o'?1.0:0.5);
}
int main(){
scanf("%d",&n);
char c=gc();
while(c!='o'&&c!='x'&&c!='?') c=gc();
p[1]=calc(c);
for(R int i=2;i<=n;++i) p[i]=calc(gc());
for(R int i=1;i<=n;++i){
x1[i]=(x1[i-1]+1)*p[i];
ans[i]=ans[i-1]+(x1[i-1]*2+1)*p[i];
}
printf("%.4lf",ans[n]);
return 0;
}
(\)
(Extra)
得分改为(X^3)，求分数的期望。
(\)
(Solution)
-
同样考虑增量，有(Delta X^3=(X+1)^3-X^3=X^3+3X^2+3X+1-X^3=3X^2+3X+1)
-
于是维护(x_1[i])代表长度的期望，(x_2[i])表示长度平方的期望，有：
[x_1[i]=(x_1[i-1]+1) imes p_i ][x_2[i]=x_2[i-1]+2x_1[i]+1 imes p_i ] -
更新答案方式相同，有(ans[i]=ans[i-1]+(3x_2[i]+3x_1[i]+1) imes p_i)。
-
解释一下(ans[i-1])的部分，它代表的是前一位置的答案，这一位置是否对答案有贡献是有概率的，而增量是后面括起来的部分。
(\)
(Code)
#include<cmath>
#include<cstdio>
#include<cctype>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define N 100010
#define R register
#define gc getchar
using namespace std;
inline int rd(){
int x=0; bool f=0; char c=gc();
while(!isdigit(c)){if(c=='-')f=1;c=gc();}
while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=gc();}
return f?-x:x;
}
inline double rdd(){
double x=0,base=1; bool f=0; char c=gc();
while(!isdigit(c)){if(c=='-')f=1;c=gc();}
while(isdigit(c)){x=x*10+(c^48);c=gc();}
if(c=='.'){
c=gc();
while(isdigit(c)){x+=(base/=10)*(c^48);c=gc();}
}
return f?-x:x;
}
int n;
double p[N],x1[N],x2[N],ans[N];
int main(){
n=rd();
for(R int i=1;i<=n;++i) p[i]=rdd();
for(R int i=1;i<=n;++i){
x1[i]=(x1[i-1]+1)*p[i];
x2[i]=(x2[i-1]+x1[i-1]*2+1)*p[i];
ans[i]=ans[i-1]+(x2[i-1]*3+x1[i-1]*3+1)*p[i];
}
printf("%.1lf",ans[n]);
return 0;
}