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

柿子饼同学

期望的三种计算方式:
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, 这样就可以做了 (因为我们只关心大小关系)

for (int i = 1; i <= n; i++) {
    cin >> x;

    if (i == 1 || i == n)
        ans += x / 2;
    else
        ans += x / 3;
}

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

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

for (int i = 1; i <= n; i++) {
    if (s[i] == 'x') {
        l1 = l2 = 0;
        continue;
    }

    // P(i) 代表 s[i] 是 o 的概率
    // 线性的加是没事的
    // 当前能否拓展 1 ? 如果能就加上 ^2/^3 的增量再乘概率
    a1 = a1 + 1 * P(s[i]);
    a2 = a2 + (2 * l1 + 1) * P(s[i]);
    a3 = a3 + (3 * l2 + 3 * l1 + 1) * P(s[i]);

    // 注意这里先更新 l2
    l2 = (l2 + l1 * 2 + 1) * P(s[i]);
    l1 = (l1 + 1) * P(s[i]);
}

F - 奖励关

bool Ismet(int x, int st) { return ((st & req[x]) == req[x]); }

// 考虑决策, 每个物品取或者不取
db dfs(int pos, int st) {
    if (pos > k)
        return 0;
    if (vis[pos][st])
        return f[pos][st];

    vis[pos][st] = 1;

    for (int i = 0; i < n; i++) {
        if (Ismet(i, st)) {
            f[pos][st] += max(dfs(pos + 1, st), dfs(pos + 1, st | (1 << i)) + val[i]) / n;
        } else {
            f[pos][st] += dfs(pos + 1, st) / n;
        }
    }

    return f[pos][st];
}

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

cin >> T;
while (T--) {
    cin >> n >> m;

    memset(f, 0, sizeof(f));
    f[1][1][1] = 1;
    for (int i = 1; i < n * m; i++) {
        for (int j = 1; j <= n; j++) {
            for (int k = 1; k <= m; k++) {
                if (i < max(j, k) || j * k < i)
                    continue;
                int s = n * m - i;

                f[i + 1][j][k] += f[i][j][k] * (j * k - i) / s;
                f[i + 1][j + 1][k] += f[i][j][k] * k * (n - j) / s;
                f[i + 1][j][k + 1] += f[i][j][k] * j * (m - k) / s;
                f[i + 1][j + 1][k + 1] += f[i][j][k] * (n - j) * (m - k) / s;
            }
        }
    }

    db ans = 0;
    for (int i = 1; i <= n * m; i++) {
        ans += i * (f[i][n][m] - f[i - 1][n][m]);
    }
    cout << fixed << setprecision(9) << ans << '\n';
}

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

db dfs(int a, int b, int c, int d, int x, int y) {
    auto &res = f[a][b][c][d][x][y];
    if (res >= 0)
        return res;

    int as = a + (x == 0) + (y == 0), bs = b + (x == 1) + (y == 1);
    int cs = c + (x == 2) + (y == 2), ds = d + (x == 3) + (y == 3);

    if (as >= A && bs >= B && cs >= C && ds >= D)
        return res = 0;
    
    int sum = 54 - as - bs - cs - ds;
    if (sum <= 0)
        return res = 1e9;
    
    res = 1;
    // 再翻开一张牌的期望
    if (a < 13)
        res += (13.0 - a) / sum * dfs(a + 1, b, c, d, x, y);
    if (b < 13)
        res += (13.0 - b) / sum * dfs(a, b + 1, c, d, x, y);
    if (c < 13)
        res += (13.0 - c) / sum * dfs(a, b, c + 1, d, x, y);
    if (d < 13)
        res += (13.0 - d) / sum * dfs(a, b, c, d + 1, x, y);

    // 决策大小王变成哪些牌
    if (x > 3) {
        db t = 1e9;
        for (int i = 0; i < 4; i++){
            t = min(t, 1.0 / sum * dfs(a, b, c, d, i, y));
        }
        res += t;
    }
    if (y > 3) {
        db t = 1e9;
        for (int i = 0; i < 4; i++){
            t = min(t, 1.0 / sum * dfs(a, b, c, d, x, i));
        }
        res += t;
    }

    return res;
}

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

f[1][0][0] = f[1][1][1] = 0;
for(int i = 2; i <= n; i++){
    for(int j = 0; j <= min(i, m); j++){
        f[i][j][1] = f[i][j][0] = 1e10;

        Min(f[i][j][0], f[i - 1][j][0] + dis[c[i - 1]][c[i]]);
        if(j >= 1){
            // 上一轮可能申请不成功
            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]]);
            // 这一轮可能申请不成功
            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]]);
        }
        if(j > 1){
            Min(f[i][j][1], f[i - 1][j - 1][1] + (1 - k[i])*(1 - k[i - 1])*dis[c[i - 1]][c[i]]\
                                        + (1 - k[i])*k[i - 1]*dis[d[i - 1]][c[i]]\
                                        + k[i]*(1 - k[i - 1])*dis[c[i - 1]][d[i]]\
                                        + k[i]*k[i - 1]*dis[d[i - 1]][d[i]]);
        }
    }
}

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

#include <bits/stdc++.h>
using namespace std;

typedef double db;
typedef multiset<int> mt;

const int N = 32;

// s 是 n*(n - 1)/2, c 是 ai*(ai - 1)/2
// f[i] = sigma((f[j] + 1) * ai * aj / s) + (f[i] + 1) * c / s
// 移项就行了

struct DSU {
    int f[N], siz[N];

    DSU() {
        for (int i = 1; i < N; i++) {
            f[i] = i;
            siz[i] = 1;
        }
    }

    int Find(int x) {
        if (x == f[x])
            return x;
        return (f[x] = Find(f[x]));
    }

    void Merge(int x, int y) {
        x = Find(x), y = Find(y);

        if (x == y)
            return;

        siz[x] += siz[y];
        f[y] = f[x];
    }
} dsu;

int n, m;
map<mt, db> f;
mt org;

db Solve(mt u) {
    if (u.size() == 1)
        return 0;

    if (f[u])
        return f[u];

    int s = n * (n - 1) / 2, c = 0, x, y;
    db r = 0;

    for (auto i = u.begin(); i != u.end(); i++) {
        x = *i;
        c += x * (x - 1) / 2;
        for (auto j = u.begin(); j != i; j++) {
            mt cur = u;
            y = *j;

            cur.erase(cur.find(x));
            cur.erase(cur.find(y));
            cur.emplace(x + y);

            r += (Solve(cur) + 1) * x * y;
        }
    }

    f[u] = 1.0 * (r + c) / (s - c);
    return f[u];
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        int x, y;
        cin >> x >> y;

        dsu.Merge(x, y);
    }

    for (int i = 1; i <= n; i++) {
        if (i == dsu.Find(i)) {
            org.emplace(dsu.siz[i]);
        }
    }

    cout << fixed << setprecision(6) << Solve(org);

    return 0;
}

两个题没写, 一个高斯消元, 一个 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在边界）。

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

#### OSU问题

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

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

for (int i = 1; i <= n; i++) {
    if (s[i] == 'o')
        f[i] = f[i-1] + 1;
    else
        f[i] = 0;

    ans_l += f[i];
    ans_l2 += f[i] * f[i];
    ans_l3 += f[i] * f[i] * f[i];
}

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

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

sfqxx

柿子饼同学

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

学习编程中的Ben

简柠啦

很cool的阳

trinityee

看看

森林格格屋

谢谢

XiaoMengXin-1

666

XiaoMengXin-1

666

cc885544