概率与期望

概念讲解

基本概念

  • 概率： 事件发生的可能性，范围 [0, 1]
  • 期望： 随机变量的平均值

期望的性质

  1. E(aX + b) = aE(X) + b
  2. E(X + Y) = E(X) + E(Y)
  3. E(XY) = E(X)E(Y)（X, Y 独立）

期望 DP

基本思想

利用期望的线性性，通过 DP 计算期望。

示例：随机游走

12345678double dp[N];

// dp[i] 表示从状态 i 到终点的期望步数
dp[n] = 0;  // 终点

for (int i = n - 1; i >= 0; i--) {
    dp[i] = 1 + dp[i + 1];  // 走一步到 i+1
}

经典问题

1. 骰子问题

问题： 掷 n 个骰子，求点数之和的期望。

解答：
E=n×3.5E = n \times 3.5

2. 抽签问题

问题： 从 n 个球中随机抽取，求抽到特定球的期望次数。

解答：
E=n+12E = \frac{n + 1}{2}

3. 随机游走

问题： 在数轴上随机游走，每次等概率向左或向右走一步，求到达终点的期望步数。

123456789double expectedSteps(int n) {
    vector<double> dp(n + 1, 0);
    
    for (int i = n - 1; i >= 0; i--) {
        dp[i] = 1 + 0.5 * dp[i + 1] + 0.5 * dp[max(0, i - 1)];
    }
    
    return dp[0];
}

考点分析

初赛考查方式

  1. 选择题： 概率和期望的概念
  2. 程序阅读： 理解期望 DP
  3. 编程题： 概率与期望应用

常见题型

  • 期望 DP
  • 概率计算
  • 随机游走

例题精讲

例题 1：骰子问题

题目： 掷 n 个骰子，求点数之和的期望。

解答：

12345678910111213#include <iostream>
using namespace std;

int main() {
    int n;
    cin >> n;
    
    double expected = n * 3.5;
    
    cout << expected << endl;
    
    return 0;
}

例题 2：随机游走

题目： 在数轴上随机游走，求到达终点的期望步数。

解答：

123456789101112131415161718#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n;
    cin >> n;
    
    vector<double> dp(n + 1, 0);
    
    for (int i = n - 1; i >= 0; i--) {
        dp[i] = 1 + 0.5 * dp[i + 1] + 0.5 * dp[max(0, i - 1)];
    }
    
    cout << dp[0] << endl;
    
    return 0;
}

练习题

  1. 洛谷 P1291 随机数生成器
查看答案

思路：期望 DP，计算到达目标值的期望步数。

123456789101112#include <iostream>
using namespace std;

int main() {
    int n;
    cin >> n;
    
    // 期望步数 = n
    cout << n << endl;
    
    return 0;
}
  1. 洛谷 P1365 WJMZBMR T 了什么
查看答案

思路：期望 DP，计算期望长度。

12345678910111213141516171819202122232425262728#include <iostream>
#include <cstdio>
using namespace std;

int main() {
    int n;
    scanf("%d", &n);
    
    char s[n + 1];
    scanf("%s", s);
    
    double ans = 0, cnt = 0;
    
    for (int i = 0; i < n; i++) {
        if (s[i] == 'o') {
            cnt++;
            ans += 2 * cnt - 1;
        } else if (s[i] == 'x') {
            cnt = 0;
        } else {
            ans += cnt;
            cnt = (cnt + 1) / 2;
        }
    }
    
    printf("%.4f\n", ans);
    return 0;
}
  1. 洛谷 P1850 换教室
查看答案

思路：期望 DP，考虑申请成功和失败两种情况。

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869#include <iostream>
#include <cstdio>
using namespace std;

int main() {
    int n, m, v, e;
    scanf("%d %d %d %d", &n, &m, &v, &e);
    
    int c[n + 1], d[n + 1];
    double k[n + 1];
    
    for (int i = 1; i <= n; i++) scanf("%d", &c[i]);
    for (int i = 1; i <= n; i++) scanf("%d", &d[i]);
    for (int i = 1; i <= n; i++) scanf("%lf", &k[i]);
    
    int dist[v + 1][v + 1];
    for (int i = 1; i <= v; i++) {
        for (int j = 1; j <= v; j++) {
            dist[i][j] = (i == j ? 0 : 1e9);
        }
    }
    
    for (int i = 0; i < e; i++) {
        int a, b, w;
        scanf("%d %d %d", &a, &b, &w);
        dist[a][b] = dist[b][a] = min(dist[a][b], w);
    }
    
    // Floyd
    for (int k = 1; k <= v; k++) {
        for (int i = 1; i <= v; i++) {
            for (int j = 1; j <= v; j++) {
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
            }
        }
    }
    
    // DP
    double dp[n + 1][m + 1][2];
    for (int i = 0; i <= n; i++) {
        for (int j = 0; j <= m; j++) {
            dp[i][j][0] = dp[i][j][1] = 1e9;
        }
    }
    
    dp[1][0][0] = dp[1][1][1] = 0;
    
    for (int i = 2; i <= n; i++) {
        for (int j = 0; j <= min(i, m); j++) {
            // 不申请
            dp[i][j][0] = min(dp[i][j][0], dp[i - 1][j][0] + dist[c[i - 1]][c[i]]);
            dp[i][j][0] = min(dp[i][j][0], dp[i - 1][j][1] + dist[c[i - 1]][c[i]] * (1 - k[i - 1]) + dist[d[i - 1]][c[i]] * k[i - 1]);
            
            if (j > 0) {
                // 申请
                dp[i][j][1] = min(dp[i][j][1], dp[i - 1][j - 1][0] + dist[c[i - 1]][c[i]] * (1 - k[i]) + dist[c[i - 1]][d[i]] * k[i]);
                dp[i][j][1] = min(dp[i][j][1], dp[i - 1][j - 1][1] + dist[c[i - 1]][c[i]] * (1 - k[i - 1]) * (1 - k[i]) + dist[d[i - 1]][c[i]] * k[i - 1] * (1 - k[i]) + dist[c[i - 1]][d[i]] * (1 - k[i - 1]) * k[i] + dist[d[i - 1]][d[i]] * k[i - 1] * k[i]);
            }
        }
    }
    
    double ans = 1e9;
    for (int j = 0; j <= m; j++) {
        ans = min(ans, min(dp[n][j][0], dp[n][j][1]));
    }
    
    printf("%.2f\n", ans);
    return 0;
}

易错点

⚠️ 注意：

  1. 期望具有线性性
  2. 期望 DP 要注意状态转移
  3. 概率和期望是不同的概念
  4. 期望 DP 通常要倒序计算