2018.6清北学堂day3下午笔记

概率

样本空间：

包含：

条件概率
定义B的关于A的条件概率
P(B|A)=P(A⋂BP(A)$P(B|A)=\frac{P(A\bigcap B}{P(A)}$

独立：
如果A，B满足P（A⋂B）=P(A)P(B)$P（A\bigcap B）=P(A)P(B)$

期望

数学期望就是随机变量在概率意义下的平均值

以下是离散型的定义

期望具有线性性
E[ax+by]=aE[x]+bE[y]$E[ax+by]=aE[x]+bE[y]$

CF280C Game on tree

解法：
根据期望的线性性，计算出每个点比选择的期望次数，然后直接相加

所以得出E(x)=1dep[x]$E(x)=\frac{1}{dep[x]}$

这里之所以是1dep[x]$\frac{1}{dep[x]}$是因为我们求的期望是每个点把自己及自己子树染黑的概率（而不是靠祖先）

bzoj3036

记忆化搜索或者拓扑排序都是可以的

bzoj3143游走

首先，需要明确一件事情，我们希望期望经过次数最大的边编号最小，和上一道题一样，由点推边

对于一号点 f[1]=1+∑f[j]/deg[j]$f[1]=1+\sum f[j]/deg[j]$
j和1有边

对于其他点
f[i]=∑f[j]/deg[j]$f[i]=\sum f[j]/deg[j]$

但由于是无向图，每个点的值会互相影响，所以不能递推

所以需要高斯消元求解

设dp[i][j]$dp[i][j]$已经找到了i个系统，j种病毒还需要的期望天数
dp[i][j]=dp[i+1][j]∗s−is∗jn+dp[i][j+1]∗n−jn∗is+dp[i+1][j+1]∗s−is∗n−jn+dp[i][j]∗is∗jn$dp[i][j]=dp[i+1][j]\ast \frac{s-i}{s}\ast \frac{j}{n}+dp[i][j+1]\ast \frac{n-j}{n}\ast \frac{i}{s}+dp[i+1][j+1]\ast \frac{s-i}{s}\ast \frac{n-j}{n}+dp[i][j]\ast \frac{i}{s}\ast \frac{j}{n}$

一道不知出处的题

给定n种物品，每次购买会随机买到一种，询问买到n种物品的期望次数

解法：

当我们已经买到了k种物品了，再继续买多少次能得到第k+1种物品

这个值是nn−k$\frac{n}{n-k}$（可以通过求无穷等比数列的式子得出来）
所以 ans=n∑ni=1in$ans=n\sum _{i=1}^n\frac{i}{n}$

UVA11021 Tribles

下一道

bzoj1419

下一题….

51NOD1670 打怪兽

好的，因老师忘记题面，所以这个题跳过了

下一题
UVA10529

、

下一题

noi2005聪聪和可可

下一题

下一个题
NOI2012迷失游乐场