定义
这里期望长度表示一段序列连续长度的期望。具体来说，对于一段序列，每个点都有一个概率连续和断开。求所有连续序列和的期望。
当然，对于以上期望长度的定义，我们只需要求出每个点存在的期望的和即可。但是题目永远不会这么简单。
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
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
| #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)\]
所以上题的代码的核心部分等同于：
1
2
3
4
5
6
| 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
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
| #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\)，我们可以得到以下转移：
\[
\begin{aligned}
f3_i&=f3_{i-1}+p*(3*(f2_{i-1}+f1_{i-1})+1)\\
f2_i&=p*(f2_{i-1}+2*f1_{i-1}+1)\\
f1_i&=p*(f1_{i-1}+1);
\end{aligned}
\]
注意！
我承认我的变量名的定义有亿点点毒瘤，因为读者可以清楚地发现在上一题中
\(f2\) 的转移为 \(f2_i=f2_{i-1}+p*(2*f1_{i-1}+1)\)
而非当前转移。实际上在定义 \(f2\)
时我的定义为答案而非二次项的期望，根据期望的线性性，答案是可以继承上一次的答案进行转移的，也就是对于'x'的情况继承
\(f2\) 而非 \(0\) 的原因。
在此level中我对 \(f2\)
重新定义为长度二次幂的期望。希望不要因为我的毒瘤误导大家。
相同的，我对 \(f3\)
的定义为答案，因此需要继承之前的答案。
于是我们就完成了P1654
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
| #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;
}
|
总结
期望好神奇。
