[心之碎片] - 概率与期望

柿子饼同学

期望的三种计算方式:
1 - 期望定义 E(x) = Sum(x.val * P(x)) 直接把所有可能的事件的概率乘以权值
也就是说可以先计算概率再乘以对应权值

2 - 期望线性性质 E(a*x + b*y + ...) = a*E(x) + b*E(y) + ...
这让我们可以单独计算每个点的贡献, 之后加起来就是总的期望, 利用独立性

3 - 逆推法 , 我们的状态可以设置成 "到达终点的期望.." 之类的,
然后用 记忆化搜索搜

可以只考虑局部的地方乘她的概率(C)
期望的柿子可能 x = ... + x*..., 需要移项

C - 排列价值
有一个 1-n 的排列, 每个位置有一个 ci, 如果这个位置的数字大于两边的数字, 得分就 + ci, 否则不加, 求期望得分

这里如果考虑整体会很难, 那么可以考虑一个个位置的情况
假设位置是中间的数, 发现两边的数符合条件的话概率是 1/3, 这样就可以做了 (因为我们只关心大小关系)

1. for (int i = 1; i <= n; i++) {
   
2.     cin >> x;
   
3. 
   
4.     if (i == 1 || i == n)
   
5.         ans += x / 2;
   
6.     else
   
7.         ans += x / 3;
   
8. }

复制代码

D - OSU
这题的加强版, 得分是 l, l^2 和 l^3

首先需要维护以 i 结尾的连续 o 期望长度
注意平方的期望长度需要单独维护, 因为不满足线性性质

1. for (int i = 1; i <= n; i++) {
   
2.     if (s[i] == 'x') {
   
3.         l1 = l2 = 0;
   
4.         continue;
   
5.     }
   
6. 
   
7.     // P(i) 代表 s[i] 是 o 的概率
   
8.     // 线性的加是没事的
   
9.     // 当前能否拓展 1 ? 如果能就加上 ^2/^3 的增量再乘概率
   
10.     a1 = a1 + 1 * P(s[i]);
    
11.     a2 = a2 + (2 * l1 + 1) * P(s[i]);
    
12.     a3 = a3 + (3 * l2 + 3 * l1 + 1) * P(s[i]);
    
13. 
    
14.     // 注意这里先更新 l2
    
15.     l2 = (l2 + l1 * 2 + 1) * P(s[i]);
    
16.     l1 = (l1 + 1) * P(s[i]);
    
17. }

复制代码

F - 奖励关

1. bool Ismet(int x, int st) { return ((st & req[x]) == req[x]); }
   
2. 
   
3. // 考虑决策, 每个物品取或者不取
   
4. db dfs(int pos, int st) {
   
5.     if (pos > k)
   
6.         return 0;
   
7.     if (vis[pos][st])
   
8.         return f[pos][st];
   
9. 
   
10.     vis[pos][st] = 1;
    
11. 
    
12.     for (int i = 0; i < n; i++) {
    
13.         if (Ismet(i, st)) {
    
14.             f[pos][st] += max(dfs(pos + 1, st), dfs(pos + 1, st | (1 << i)) + val[i]) / n;
    
15.         } else {
    
16.             f[pos][st] += dfs(pos + 1, st) / n;
    
17.         }
    
18.     }
    
19. 
    
20.     return f[pos][st];
    
21. }

复制代码

G - 放棋子
终点太多, 考虑先计算概率再算期望, 刷表, 分类讨论
需要注意的是这个 f 在任务结束之后仍然会更新下一天的, 所以就相当于前缀和了

1. cin >> T;
   
2. while (T--) {
   
3.     cin >> n >> m;
   
4. 
   
5.     memset(f, 0, sizeof(f));
   
6.     f[1][1][1] = 1;
   
7.     for (int i = 1; i < n * m; i++) {
   
8.         for (int j = 1; j <= n; j++) {
   
9.             for (int k = 1; k <= m; k++) {
   
10.                 if (i < max(j, k) || j * k < i)
    
11.                     continue;
    
12.                 int s = n * m - i;
    
13. 
    
14.                 f[i + 1][j][k] += f[i][j][k] * (j * k - i) / s;
    
15.                 f[i + 1][j + 1][k] += f[i][j][k] * k * (n - j) / s;
    
16.                 f[i + 1][j][k + 1] += f[i][j][k] * j * (m - k) / s;
    
17.                 f[i + 1][j + 1][k + 1] += f[i][j][k] * (n - j) * (m - k) / s;
    
18.             }
    
19.         }
    
20.     }
    
21. 
    
22.     db ans = 0;
    
23.     for (int i = 1; i <= n * m; i++) {
    
24.         ans += i * (f[i][n][m] - f[i - 1][n][m]);
    
25.     }
    
26.     cout << fixed << setprecision(9) << ans << '\n';
    
27. }

复制代码

H - 扑克牌
状态设的是每个牌翻了几个, 并且大王小王分别变成了哪些牌

1. db dfs(int a, int b, int c, int d, int x, int y) {
   
2.     auto &res = f[a][b][c][d][x][y];
   
3.     if (res >= 0)
   
4.         return res;
   
5. 
   
6.     int as = a + (x == 0) + (y == 0), bs = b + (x == 1) + (y == 1);
   
7.     int cs = c + (x == 2) + (y == 2), ds = d + (x == 3) + (y == 3);
   
8. 
   
9.     if (as >= A && bs >= B && cs >= C && ds >= D)
   
10.         return res = 0;
    
11.    
    
12.     int sum = 54 - as - bs - cs - ds;
    
13.     if (sum <= 0)
    
14.         return res = 1e9;
    
15.    
    
16.     res = 1;
    
17.     // 再翻开一张牌的期望
    
18.     if (a < 13)
    
19.         res += (13.0 - a) / sum * dfs(a + 1, b, c, d, x, y);
    
20.     if (b < 13)
    
21.         res += (13.0 - b) / sum * dfs(a, b + 1, c, d, x, y);
    
22.     if (c < 13)
    
23.         res += (13.0 - c) / sum * dfs(a, b, c + 1, d, x, y);
    
24.     if (d < 13)
    
25.         res += (13.0 - d) / sum * dfs(a, b, c, d + 1, x, y);
    
26. 
    
27.     // 决策大小王变成哪些牌
    
28.     if (x > 3) {
    
29.         db t = 1e9;
    
30.         for (int i = 0; i < 4; i++){
    
31.             t = min(t, 1.0 / sum * dfs(a, b, c, d, i, y));
    
32.         }
    
33.         res += t;
    
34.     }
    
35.     if (y > 3) {
    
36.         db t = 1e9;
    
37.         for (int i = 0; i < 4; i++){
    
38.             t = min(t, 1.0 / sum * dfs(a, b, c, d, x, i));
    
39.         }
    
40.         res += t;
    
41.     }
    
42. 
    
43.     return res;
    
44. }

复制代码

I - 换教室
设 f(i, j, 0/1) 表示前 i 个教室申请了 j 次, i 申不申的期望, 不难想但是需要注意细节, 考虑失败/成功/取/不取

1. f[1][0][0] = f[1][1][1] = 0;
   
2. for(int i = 2; i <= n; i++){
   
3.     for(int j = 0; j <= min(i, m); j++){
   
4.         f[i][j][1] = f[i][j][0] = 1e10;
   
5. 
   
6.         Min(f[i][j][0], f[i - 1][j][0] + dis[c[i - 1]][c[i]]);
   
7.         if(j >= 1){
   
8.             // 上一轮可能申请不成功
   
9.             Min(f[i][j][0], f[i - 1][j][1] + k[i - 1]*dis[d[i - 1]][c[i]] + (1 - k[i - 1])*dis[c[i - 1]][c[i]]);
   
10.             // 这一轮可能申请不成功
    
11.             Min(f[i][j][1], f[i - 1][j - 1][0] + k[i]*dis[c[i - 1]][d[i]] + (1 - k[i])*dis[c[i - 1]][c[i]]);
    
12.         }
    
13.         if(j > 1){
    
14.             Min(f[i][j][1], f[i - 1][j - 1][1] + (1 - k[i])*(1 - k[i - 1])*dis[c[i - 1]][c[i]]\
    
15.                                         + (1 - k[i])*k[i - 1]*dis[d[i - 1]][c[i]]\
    
16.                                         + k[i]*(1 - k[i - 1])*dis[c[i - 1]][d[i]]\
    
17.                                         + k[i]*k[i - 1]*dis[d[i - 1]][d[i]]);
    
18.         }
    
19.     }
    
20. }

复制代码

K - 互联
只在意当前连通块的数量和大小, 所以直接把连通块情况作为状态
然后枚举情况, 有可能当前选择的边能连接, 也可能没有意义

1. #include <bits/stdc++.h>
   
2. using namespace std;
   
3. 
   
4. typedef double db;
   
5. typedef multiset<int> mt;
   
6. 
   
7. const int N = 32;
   
8. 
   
9. // s 是 n*(n - 1)/2, c 是 ai*(ai - 1)/2
   
10. // f[i] = sigma((f[j] + 1) * ai * aj / s) + (f[i] + 1) * c / s
    
11. // 移项就行了
    
12. 
    
13. struct DSU {
    
14.     int f[N], siz[N];
    
15. 
    
16.     DSU() {
    
17.         for (int i = 1; i < N; i++) {
    
18.             f[i] = i;
    
19.             siz[i] = 1;
    
20.         }
    
21.     }
    
22. 
    
23.     int Find(int x) {
    
24.         if (x == f[x])
    
25.             return x;
    
26.         return (f[x] = Find(f[x]));
    
27.     }
    
28. 
    
29.     void Merge(int x, int y) {
    
30.         x = Find(x), y = Find(y);
    
31. 
    
32.         if (x == y)
    
33.             return;
    
34. 
    
35.         siz[x] += siz[y];
    
36.         f[y] = f[x];
    
37.     }
    
38. } dsu;
    
39. 
    
40. int n, m;
    
41. map<mt, db> f;
    
42. mt org;
    
43. 
    
44. db Solve(mt u) {
    
45.     if (u.size() == 1)
    
46.         return 0;
    
47. 
    
48.     if (f[u])
    
49.         return f[u];
    
50. 
    
51.     int s = n * (n - 1) / 2, c = 0, x, y;
    
52.     db r = 0;
    
53. 
    
54.     for (auto i = u.begin(); i != u.end(); i++) {
    
55.         x = *i;
    
56.         c += x * (x - 1) / 2;
    
57.         for (auto j = u.begin(); j != i; j++) {
    
58.             mt cur = u;
    
59.             y = *j;
    
60. 
    
61.             cur.erase(cur.find(x));
    
62.             cur.erase(cur.find(y));
    
63.             cur.emplace(x + y);
    
64. 
    
65.             r += (Solve(cur) + 1) * x * y;
    
66.         }
    
67.     }
    
68. 
    
69.     f[u] = 1.0 * (r + c) / (s - c);
    
70.     return f[u];
    
71. }
    
72. 
    
73. int main() {
    
74.     ios::sync_with_stdio(0);
    
75.     cin.tie(0);
    
76. 
    
77.     cin >> n >> m;
    
78.     for (int i = 1; i <= m; i++) {
    
79.         int x, y;
    
80.         cin >> x >> y;
    
81. 
    
82.         dsu.Merge(x, y);
    
83.     }
    
84. 
    
85.     for (int i = 1; i <= n; i++) {
    
86.         if (i == dsu.Find(i)) {
    
87.             org.emplace(dsu.siz[i]);
    
88.         }
    
89.     }
    
90. 
    
91.     cout << fixed << setprecision(6) << Solve(org);
    
92. 
    
93.     return 0;
    
94. }

复制代码

两个题没写, 一个高斯消元, 一个 kmp
L - 弹钢琴

J - 小卖部
给出一个 n*m 的网格图，小C要从家前往小卖部，
小C每次会随机向相邻的四个方向中不为障碍物的方向移动一个格子，求到达小卖部的期望步数。

FishC

鱼油好！看得出来你在学习期望值相关的内容。这里简要总结一下核心概念和几个问题的解题方法：

### 期望的计算方式

1. **期望定义**：直接求和。
   - 公式：E(X) = ∑(x * P(x))
   - 方法：计算每个事件的概率，然后乘以对应的事件值，再求和。
   
2. **期望的线性性质**：
   - 公式：E(aX + bY + ...) = aE(X) + bE(Y) + ...
   - 方法：利用事件之间的独立性，分别计算每个部分的期望，再加总。
   
3. **逆推法**：
   - 思路：设置终状态作为目标，递归或通过记忆化搜索求解。
   - 方法：定义状态转移方程，考虑如何从当前状态一步步到达终点。

### 实例问题解析

#### 排列价值问题

**问题描述**：1-N 的排列中，每个位置有一个 ci，若该位置的数大于两边的数，得分加 ci，求期望得分。

**解法**：
- 对边界情况单独处理，中间位置的数符合条件概率为1/3。
- 公式：ans += ci / 3 （i在中间）；ans += ci / 2（i在边界）。

1. for (int i = 1; i <= n; i++) {
   
2.     if (i == 1 || i == n)
   
3.         ans += ci / 2;
   
4.     else
   
5.         ans += ci / 3;
   
6. }

复制代码

#### OSU问题

**问题描述**：求以 i 结尾的连续 o 的期望长度，得分为 l，l^2 和 l^3。

**解法**：
- 使用动态规划，分别维护以 i 结尾的期望长度。
- 需单独处理平方和立方的期望，因为它们不满足线性性质。

1. for (int i = 1; i <= n; i++) {
   
2.     if (s[i] == 'o')
   
3.         f[i] = f[i-1] + 1;
   
4.     else
   
5.         f[i] = 0;
   
6. 
   
7.     ans_l += f[i];
   
8.     ans_l2 += f[i] * f[i];
   
9.     ans_l3 += f[i] * f[i] * f[i];
   
10. }

复制代码

你可以用这些简洁的方法来处理包含期望值计算的问题，希望对你有帮助！如果有更多问题，欢迎继续提问。

以上回复来自 FishC AI 小助理，如未能正确解答您的问题，请继续追问。

sfqxx

柿子饼同学

sfqxx 发表于 2024-8-30 20:54

学习编程中的Ben

简柠啦

很cool的阳

trinityee

看看

森林格格屋

谢谢

XiaoMengXin-1

666

XiaoMengXin-1

666

cc885544

琅琊王朝

厉害