概率
1.基本概念
2.古典概率
3.条件概率
3.1 乘法公式
3.2 全概率公式
3.3 贝叶斯公式
期望
1.期望的线性性质
2.例题
Ⅰ. P4206 [NOI2005] 聪聪与可可
\(p_{x,y}\) 表示顶点 \(i\) 到顶点 \(j\) 的最短路上与顶点 \(i\) 相邻且编号最小的顶点编号。
\(f_{x,y}\) 表示聪聪在 \(x\), 可可在 \(y\) 时，聪聪抓住可可的平均步数。
\(yy\) 表示可可下一步所取的点。
\(d_x\) 表示 \(x\) 点的度数。
用记忆化搜索来实现：
- \(\Large x = y\), \(\Large f_{x,y} = 0\)
- \(\Large p_{x,y} = y \ \ || \ \ p_{p_{x,y},y} = y\) ，\(\Large f_{x,y} = 1\)
- \(\Large f_{x,y} = \dfrac{\sum\limits_{w} f_{p_{p_{x,y}, w}}}{d_y + 1} + 1\)
点击查看代码
#include<bits/stdc++.h>
#define db double
using namespace std;
const int N = 1e3 + 67;
int read(){
int x = 0, f = 1; char ch = getchar();
while(ch < '0' || ch > '9'){if(ch == '-') f = -f; ch = getchar();}
while(ch >= '0' && ch <= '9'){x = (x << 1) + (x << 3) + (ch ^ 48); ch = getchar();}
return x * f;
}
int n, m, s, t;
int tot, Head[N], Next[N << 1], to[N << 1], edge[N << 1];
bool vis[N];
db f[N][N];
int p[N][N], dis[N][N], d[N];
void add(int u, int v, int w){
to[++tot] = v, Next[tot] = Head[u], Head[u] = tot, edge[tot] = w, ++d[u];
}
void spfa(int s){
memset(dis, -1, sizeof(dis));
vis[s] = 1, dis[s][s] = 0;
queue<int> q; q.push(s);
while(!q.empty()){
int x = q.front(); q.pop();
vis[x] = 0;
for(int i = Head[x]; i; i = Next[i]){
int y = to[i], z = edge[i];
if(dis[s][y] == -1 || (dis[s][y] == dis[s][x] + z && p[s][x] < p[s][y])){
dis[s][y] = dis[s][x] + z;
if(p[s][x]) p[s][y] = p[s][x];
else p[s][y] = y;
if(!vis[y]) q.push(y), vis[y] = 1;
}
}
}
}
db dfs(int x, int y){
if(f[x][y]) return f[x][y];
if(x == y) return f[x][y] = 0.0;
if(p[x][y] == y || p[p[x][y]][y] == y) return f[x][y] = 1.0;
for(int i = Head[y]; i; i = Next[i]) f[x][y] += dfs(p[p[x][y]][y], to[i]);
f[x][y] = (f[x][y] + dfs(p[p[x][y]][y], y)) / (d[y] + 1) + 1;
return f[x][y];
}
int main(){
n = read(), m = read(), s = read(), t = read();
for(int i = 1; i <= m; ++i){
int u = read(), v = read();
add(u, v, 1), add(v, u, 1);
}
for(int i = 1; i <= n; ++i)
spfa(i);
printf("%.3lf\n", dfs(s, t));
return 0;
}
Ⅱ. P4745 [CERC2017]Gambling Guide
假设当前处理到 \(x\) 点， 期望为 \(f_x\)。
发现如果 \(x\) 周围点 \(f_y < f_x\) 的话， \(f_y\) 是会对 \(f_x\) 有影响的。
有什么影响呢？即 \(y\) 下一步走到 \(x\)。
从 \(n\) 开始遍历，已经遍历过的点 \(f\) 一定小于 \(f_x\)，没有遍历过的点 \(f\) 一定大于 \(f_x\)。
为什么我们可以保证这个性质？因为我们试着考虑最短路（\(\text{Dijkstra}\)），会发现每一个已经遍历过的点与根的距离一定小于一个没有遍历过的点，这是它的正确性。
假设所有 \(f_i<f_x(1\leqslant i\leqslant n)\) 中 \(i\) 构成的点集称为 \(S\)，点集大小为 \(c\)。
那么走到点 \(x\) 时肯定走 \(S\) 中的点是最优的。
得到式子：
\[f_x = \dfrac{c}{k}\sum\limits_{i \in S} \dfrac{f_i}{c} + \dfrac{k - c}{k} \times f_x + 1
\]
化简得:
\[f_x = \dfrac{\sum_{i \in S} f_i + k}{c}
\]
点击查看代码
#include<bits/stdc++.h>
#define db double
#define mp make_pair
using namespace std;
const int N = 3e5 + 67;
int read(){
int x = 0, f = 1; char ch = getchar();
while(ch < '0' || ch > '9'){if(ch == '-') f = -f; ch = getchar();}
while(ch >= '0' && ch <= '9'){x = (x << 1) + (x << 3) + (ch ^ 48); ch = getchar();}
return x * f;
}
int n, m;
int tot, Head[N], Next[N << 1], to[N << 1], d[N], cnt[N];
db f[N], sum[N];
bool vis[N];
priority_queue<pair<double, int> > pq;
void add(int u, int v){
to[++tot] = v, Next[tot] = Head[u], Head[u] = tot, ++d[u];
}
void dijkstra(int s){
pq.push(mp(0, s));
while(!pq.empty()){
int x = pq.top().second; pq.pop();
if(vis[x]) continue; vis[x] = 1;
for(int i = Head[x]; i; i = Next[i]){
int y = to[i]; if(vis[y]) continue;
++cnt[y], sum[y] += f[x];
f[y] = (d[y] + sum[y]) / cnt[y];
pq.push(mp(-f[y], y));
}
}
}
int main(){
n = read(), m = read();
for(int i = 1; i <= m; ++i){
int u = read(), v = read();
add(u, v), add(v, u);
}
dijkstra(n);
printf("%.10lf\n", f[1]);
return 0;
}