期望长度
定义
这里期望长度表示一段序列连续长度的期望。具体来说，对于一段序列，每个点都有一个概率连续和断开。求所有连续序列和的期望。
当然，对于以上期望长度的定义，我们只需要求出每个点存在的期望的和即可。但是题目永远不会这么简单。
Osu!
Osu!是一个音乐游戏，玩家需要对音符在恰当时候进行敲击来通关。一次到位的敲击为o，不到位的为x。一段连续到位的敲击，即combo次数为这段序列的长度。
我们接下来讨论的三个题都和这个游戏有关。
- level1
一段Osu!序列为一串字符，包括'o','x','?'。其中'o','x'的定义如上，'?'表示此位置有一半的几率为'o'。游戏得分为所有combo次数平方的和。求得分的期望。
也就是我们要求所有序列长度平方的期望和。
期望
期望具有线性性，但不具有积性。这意味着我们无法对求得的期望长度直接平方来得到答案。
并且请注意一点，若一个值的期望为0，并不意味着它的平方的期望为0。这可以帮助我们理解期望的线性性。
期望的平方在大多数情况下并没有什么实际意义。
但是，期望具有线性性。
考虑我们的答案，实际上就是长度平方的期望。考虑往后的转移。（设(f1)表示当前期望长度，(f2)表示答案，即长度平方期望的和）
根据公式((len+1)^2=len^2+2*len+1)若后一位(i)为'o',则后一位(i)的期望值分别为
(f1_i=f1_{i-1}+1)
(f2_i=f2_{i-1}+2*f1_{i-1}+1)
即此位(f2)的值其实是可以从前一位线性转移来的。所谓线性，就是其幂为1。
同样，考虑第(i)位为'x'的情况，(f1=0),(f2)直接继承前面的答案。
然后我们就可以得到'?'的情况：上述两种情况和除以2.
(f1_i=frac{f1_{i-1}+1}2)
(f2_i=frac{2*f2_{i-1}+2*f1_{i-1}+1}{2})
于是我们就能完成P1365
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cctype>
using namespace std;
inline int read(){
int x=0,w=0;char c=getchar();
while(!isdigit(c))w|=c=='-',c=getchar();
while(isdigit(c))x=(x<<3)+(x<<1)+(c^48),c=getchar();
return w?-x:x;
}
namespace star
{
int n;
double f,len,p;
inline void work(){
n=read();
char c=getchar();
while(c!='o' and c!='?' and c!='x')c=getchar();
while(n--){
if(c=='o')f=(f+2*len+1),len=len+1;
else if(c=='?')f=(2*(f+len)+1)/2,len=(len+1)/2;
else len=0;
}
printf("%.4lf",f);
}
}
signed main(){
star::work();
return 0;
}
- level2
我们发现，其实对于概率任意的情况也可以推出来。上题三种字符其实就是对应概率为1,0.5,0的三种情况。
设(p)为该点为'o'的概率，则有:
(f2_i=f2_{i-1}+p*(2*f1_{i-1}+1))
(f1_i=p*(f1_{i-1}+1))
所以上题的代码的核心部分等同于：
while(n--){
p=c=='o'?1.0:c=='?'?0.5:0.0;
f=f+p*(2*len+1);
len=p*(len+1);
c=getchar();
}
于是我们可以完成CF235B
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cctype>
using namespace std;
inline int read(){
int x=0,w=0;char c=getchar();
while(!isdigit(c))w|=c=='-',c=getchar();
while(isdigit(c))x=(x<<3)+(x<<1)+(c^48),c=getchar();
return w?-x:x;
}
namespace star
{
int n;
double f,len,p;
inline void work(){
n=read();
while(n--){
scanf("%lf",&p);
f=(f-len*len+(len+1)*(len+1))*p+f*(1-p);
len=p*(len+1);
}
printf("%.8lf",f);
}
}
signed main(){
star::work();
return 0;
}
- level3
我们已经完成了对于长度平方的期望和的问题。那么我们就可以解决新的问题：对于答案为所有combo长度立方的和的期望我们怎么求解呢？
根据期望的线性性，我们再维护一个平方的期望即可。
根据公式((len+1)^3=len^3+3len^2+3len+1)，我们可以得到以下转移：
注意！
我承认我的变量名的定义有亿点点毒瘤，因为读者可以清楚地发现在上一题中(f2)的转移为(f2_i=f2_{i-1}+p*(2*f1_{i-1}+1))而非当前转移。实际上在定义(f2)时我的定义为答案而非二次项的期望，根据期望的线性性，答案是可以继承上一次的答案进行转移的，也就是对于'x'的情况继承(f2)而非(0)的原因。
在此level中我对(f2)重新定义为长度二次幂的期望。希望不要因为我的毒瘤误导大家。
相同的，我对(f3)的定义为答案，因此需要继承之前的答案。
于是我们就完成了P1654
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cctype>
using namespace std;
inline int read(){
int x=0,w=0;char c=getchar();
while(!isdigit(c))w|=c=='-',c=getchar();
while(isdigit(c))x=(x<<3)+(x<<1)+(c^48),c=getchar();
return w?-x:x;
}
namespace star
{
int n;
double f1,f2,f3;
inline void work(){
n=read();
double p;
while(n--){
scanf("%lf",&p);
f3=f3+p*(3*(f2+f1)+1);
f2=p*(f2+2*f1+1);
f1=p*(f1+1);
}
printf("%.1lf",f3);
}
}
signed main(){
star::work();
return 0;
}
总结
期望好神奇。