课件
我去除了大部分数学一的内容，但是我保留了一部分，只有保留了这一部分，才知道你听的是数学一。
1））期望的定义：
看个乐就行了（
然后是期望的公式：
\[E(X)=∑_{i=1}^{n}x_ip_i \]2））期望的一些性质：
设 \(X\),\(Y\) 为随机变量，\(C\) 为常数。
-
\(E(XY)=E(X)×E(Y)\)
-
\(E(X+Y)=E(X)+E(Y)\)
-
\(E(CX)=C×E(X)\)
关于上面这个，可以简单证明一下
设 \(X\) 的多个随机变量为 ：
\[Cx_1，Cx_2，Cx_3...Cx_n \]它们对应的出现概率为：
\[p_1,p_2,p_3...p_n \]可以得出：
\[E(CX)=C∑_{i=1}^n x_ip_i \]（\(C\)提出来）
由于：
\[E(X)=∑_{i=1}^n x_ip_i \]所以：
\[E(CX)=C×E(X) \]然后就可以推出： \(E(C)=C\)
3））期望和方差的关系：
\[D(X)=∑_{i=1}^{n}[x_i-E(X)]^2p_i=E[X-E(X)]^2 \]然后我们将这个公式稍微推一下：
\[\begin{aligned} D(X)&=E[X-E(X)]^2\\ &=E[X^2-2X·E(X)+E^2(X)]\\ &=E(X^2)-2E(X)·E(X)+E^2(X)\\ &=E(X^2)-2E^2(X)+E^2(X)\\ &=E(X^2)-E^2(X) \end{aligned} \]就是平时常用的式子，一般这么求方差。
4））期望和均值的区别
这个很好理解，举个栗子，比如说扔骰子，你扔几次的平均值可能都不一样，但期望在没扔的时候就已经确定了：
\[E=\frac{1+2+3+4+5+6}{6}=3.5 \]引入：
1））
先看一个经典的问题：
甲乙两人比赛，三局两胜，奖金 \(1000\) 元，出于某些原因比赛无发继续进行，目前甲赢两局，乙赢一局，求如何分奖金。
直接平分肯定是错误的，无法使所有人满意
所以我们要考虑接下来的对局：
- 首先看第一局：如果甲赢了，则游戏结束，甲获胜，概率为 \(50\%\) ；如果乙赢了，则现在比分 \(2:2\) ，还需要再比一局。概率也是 \(50\%\)
- 然后顺着第二种结果，如果乙又赢了，则乙获胜，概率为 \(50\%×50\%=25\%\) ，如果甲赢了，则甲获胜，概率也是 \(25\%\)
综合上面所说的，我们不难发现，甲的胜率为 \(75\%\)，乙的胜率为 \(25\%\)，按照胜率来分，甲得 \(75\%×1000=750\) 元，乙得 \(25\%×1000=250\) 元。
例题：
P1365 WJMZBMR打osu! / Easy
设打到 \(i\) 时 combo 的期望长度为 \(len\)，\(f_i\) 为打到 \(i\) 时的期望得分。
共三种情况：
-
当 \(s_i\) 为 \(o\) 时，\(f_i=f_{i-1}+[(len+1)^2-len^2]=f_{i-1}+2*len+1\)，\(len=len+1\)。
-
当 \(s_i\) 为 \(x\) 时，\(f_i=f_{i-1}\)，\(len=0\)。
-
当 \(s_i\) 为 \(?\) 时，上面两种情况出现的概率相等，所以可以将 \(x\) 和 \(o\) 合在一起再乘 \(50\%\)，所以 $ f_i = \frac {f_{i-1}+2\times len+1+f_{i-1}}{2}=f_{i-1}+len+\frac {1}{2}\(，\)len=\frac {len+1} {2}$。
#include<bits/stdc++.h>
using namespace std;
int n;char s;
double ans,l;
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;++i)
{
cin>>s;
if(s=='o')
{
ans+=l*2+1;
l++;
}
else if(s=='?')
{
ans+=l+0.5;
l=(l+1)*0.5;
}
else l=0;
}
printf("%.4lf",ans);
return 0;
}
P1654 OSU!
这题和上面那题相似，区别在于要维护 \(N^3\) 的期望，至于成功率什么的没有太大影响。
记第 \(i\) 次成功率为 \(p_i\) ，长度的期望为 \(l_1\) ， 长度平方的期望为 \(l_2\)，期望得分为 \(f_i\)。
-
首先维护 \(f_i\)，这里注意乘的不是 \(50\%\) 而是 \(p_i\)，\(f_i=f_{i-1}+[(l_1+1)^3-l_1^3]×p_i=f_{i-1}+[3×(l_2+l_1)+1]×p_i\)。
-
\(l_1\) 的维护和上题一样，即 \(l_1=(l_1+1)×p_i\)。
-
\(l^2\) 需要单独维护，\(l_2=(l_2+l_1*2+1)×p_i\) 。
注意维护顺序，使用的 \(l_1\) 和 \(l_2\) 均为未更新前的，所以应为 $f_i → l_2 → l_1 $。
#include<bits/stdc++.h>
using namespace std;
int n;
double l1,l2,ans;
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;++i)
{
double p;
scanf("%lf",&p);
ans+=(3.0*(l1+l2)+1)*p;
l2=(l2+l1*2.0+1.0)*p;
l1=(l1+1.0)*p;
}
printf("%.1lf",ans);
return 0;
}
CF235B Let's Play Osu!
多倍经验了属于是，其实就是上面两题的缝合版。
- $f_i=f_{i-1}+[(l+1)2-l2]×p_i=f_{i-1}+(2×l+1)×p_i $。
- \(l=(l+1)×p_i\)。
#include<bits/stdc++.h>
using namespace std;
int n;
double l,ans;
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;++i)
{
double p;
scanf("%lf",&p);
ans+=(2*l+1.0)*p;
l=(l+1.0)*p;
}
printf("%.10lf",ans);
return 0;
}
SP1026 FAVDICE - Favorite Dice
设 \(f[i]\) 为已经掷到 \(i\) 面，还期望掷多少次骰子才能使每一面都被投到
显然的，有 \(\frac{i}{n}\) 的概率掷到已经掷到过的面，有 \(\frac{n-i}{n}\) 的概率掷到未被掷到的面。
这里需要注意一下,这两种情况均需要先掷一次，所以要再 \(+1\)。
所以可以推出：
\[f[i]=\frac{i}{n}×f[i]+\frac{n-i}{n}×f[i+1]+1 \]移项，得：
\[\frac{n-i}{n}×f[i]=\frac{n-i}{n}×f[i+1]+1 \]\[f[i]=f[i+1]+\frac{n}{n-i} \]答案就是 \(f[0]\)。
然后我们发现这个数组可以滚掉，可以得出最终代码：
#include<bits/stdc++.h>
using namespace std;
double ans,n;
int T;
int main()
{
scanf("%d",&T);
while(T--)
{
scanf("%lf",&n);
for(int i=1;i<=n;++i) ans+=(n*1.0/(i));
printf("%.2lf\n",ans);
ans=0;
}
return 0;
}
P4550 收集邮票
本题和上面那题也有些相似，区别在于每一步的代价不同。
设买了 \(n\) 张，转化一下：
\[ans=∑_{i=1}^{n}i=\frac{n×(n+1)}{2}=\frac{n^2+n}{2} \]要求的就是 \(ans\) 的期望。
设 \(a[i]\) 为收集到 \(i\) 种邮票所需购买次数的期望，\(f[i]\) 为...次数平方的期望。
先看 \(a[i]\)，容易发现可以分成两种情况：
-
第一种是买到已经有的，显而易见，概率为 \(\frac{i}{n}\)，花费为 \(a[i]\)。
-
第二种是买到没有的，概率为 \(\frac{n-i}{n}\)，花费为 \(a[i+1]\)。
显然这都是构建在买了一张邮票基础上的，所以要加一。
推出式子：
\[a[i]=\frac{i}{n}×a[i]+\frac{n-i}{n}×a[i+1]+1 \]移项的过程和上面那题一样，所以就不写了，最终得：
\[a[i]=a[i+1]+\frac{n}{n-i} \]接着维护 \(f[i]\)，其实和 \(a[i]\) 差不多：
\[f[i]=\frac{i}{n}×({f[i]+2×a[i]}+1)+\frac{n-i}{n}×(f[i+1]+2×a[i+1]+1) \]简化一下式子：
\[f[i]=\frac{i}{n-i}×(2×a[i]+1)+f[i+1]+2×a[i+1]+1 \]就维护完啦。
\(ans=\frac{n^2+n}{2}=\frac{f[0]+a[0]}{2}\)
P3802 小魔女帕琪
首先要明确一个概念，任意连续 \(7\) 位构成终极魔法的概率是一样的。那么问题就转换成了求长度为 \(7\) 的序列中触发的期望，最后再 \(×(n-6)\)，就可以算出最终的期望。
先求形如 \(1,2,3,4,5,6,7\) 的触发概率
设 \(N=a_1+a_2+...+a_7\)
很好得出：
\[P=\frac{a_1}{N}×\frac{a_2}{N-1}×\frac{a_3}{N-2}×\frac{a_4}{N-3}×\frac{a_5}{N-4}×\frac{a_6}{N-5}×\frac{a_7}{N-6} \]考虑到顺序没有影响，所以有 \(7!\) 种排列，所以：
\[P=7！×\frac{a_1}{N}×\frac{a_2}{N-1}×\frac{a_3}{N-2}×\frac{a_4}{N-3}×\frac{a_5}{N-4}×\frac{a_6}{N-5}×\frac{a_7}{N-6} \]可以得出最终答案：
\[E=(N-6)P=7！×\frac{a_1}{N}×\frac{a_2}{N-1}×\frac{a_3}{N-2}×\frac{a_4}{N-3}×\frac{a_5}{N-4}×\frac{a_6}{N-5}×a_7 \]#include<bits/stdc++.h>
using namespace std;
double a[8],n;
int main()
{
for(int i=1;i<=7;++i) scanf("%lf",&a[i]),n+=a[i];
printf("%.3lf",5040.0*a[1]/n*a[2]/(n-1.0)*a[3]/(n-2.0)*a[4]/(n-3.0)*a[5]/(n-4.0)*a[6]/(n-5.0)*a[7]);
return 0;
}
P3750 [六省联考 2017] 分手是祝愿
仔细想想不难发现：对于每个灯，只有它后面的灯才能影响到它，换句话说：对于一个点，在后面的点操作完后，如果这个灯还亮着，这个点就必须按。所以我们可以从后面扫一遍，把必须要按的灯记录下来，共 \(cnt\) 个，特别的，如果 \(cnt\le k\)，直接输出 \(cnt\) 就行。并且对于每个不必要的点，如果按到了，就必须要按回去来消除影响。
设 \(f_i\) 为由剩余 \(i\) 个必须要按的灯，变为 \(i-1\) 个必须要按的灯所需次数的期望。然后就是熟悉的分情况：
-
按到必要的灯，因为必要的灯已经确定了，所以顺序没有影响，概率为 \(\frac{i}{n}\)
-
按到不必要的灯（或者是后面已经灭了的灯），概率为 \(\frac{n-i}{n}\) ，此时必要灯的数量变为 \(i+1\) ，所以还需 \(f[i+1]+f[i]\) 次操作才能变为 \(i-1\) 个。
最后还是要加上此次操作的 \(1\)，还要注意第一种情况没有多余的代价：
\[f[i]=\frac{n-i}{n}×（f[i+1]+f[i]）+1 \]简化一下：
\[f[i]=\frac{n+(n−i)×f[i+1]}{i} \]最终求出答案（不要忘了 \(+k\) ）：
\[sum=n!×(k+∑_{i=k+1}^{cnt} f[i]) \]#include<bits/stdc++.h>
using namespace std;
long long mod=100003;
int n,k,cnt;
long long c=1,f[100001];
int a[100001];
long long qp(long long a,long long b,long long ans=1){for(;b;b>>=1,a=(a*a)%mod) if(b&1) ans=(ans*a)%mod;return ans;}
int main()
{
scanf("%d%d",&n,&k);
for(int i=1;i<=n;++i)
{
c=(c*i)%mod;
scanf("%d",&a[i]);
}
for(int i=n;i>=1;--i)
{
if(!a[i]) continue;
for(int j=1;j*j<=i;++j)
{
if(i%j==0) a[i/j]^=1,a[j]^=1;
if(j*j==i) a[j]^=1;
}
cnt++;
}
if(cnt<=k) return printf("%lld",c*cnt%mod),0;
f[n]=1;
for(int i=n-1;i;--i) f[i]=(long long)(n-i)*(f[i+1]+1)%mod*qp(i,mod-2)%mod+1;
long long ans=k;
for(int i=k+1;i<=cnt;++i) ans=(ans+f[i])%mod;
printf("%lld",ans*c%mod);
return 0;
}
P1297 [国家集训队]单选错位
比较简单的期望题，不难发现，前后两题选项的组合数为 \(a[i]×a[i-1]\) ，后面的题做对时必须要保证前后两个选项一样，共有 \(min(a[i],a[i-1])\) 种可能，所以第 \(i\) 题作对的概率为 \(\frac{min(a[i],a[i-1])}{a[i]×a[i-1]}=\frac{1}{max(a[i],a[i-1])}\)
注意特判 \(1\) 的情况
#include<bits/stdc++.h>
using namespace std;
int n,A,B,C;
int a[10000001];
double ans;
int main()
{
scanf("%d%d%d%d%d", &n, &A, &B, &C, a + 1);
for (int i = 2; i <= n; i++)
a[i] = ((long long) a[i - 1] * A + B) % 100000001;
for (int i = 1; i <= n; i++)
a[i] = a[i] % C + 1;
for(int i=1;i<=n;++i)
{
int las=i-1;
if(!las) las=n;
ans+=1.0/(max(a[i],a[las])*1.0);
}
printf("%.3lf",ans);
return 0;
}
最后还有一道条件期望：
假设你不断扔一个等概率的六面骰子，直到扔出6停止。求在骰子只出现过偶数的条件下扔骰子次数的期望。
省流：扔骰子，扔到 \(1,3,5,6\) 停，求以 \(6\) 结尾的期望投掷次数。
设 \(X\) 为期望投掷次数。
\[X= \left\{ \begin{aligned} &1→0\\ &2→X\\ &3→0\\ &4→X\\ &5→0\\ &6→0\\ \end{aligned} \right. \]所以 ：
\[X=\frac{2}{3}×0+\frac{1}{3}×X+1 \]\[X=\frac{3}{2} \]