[心之碎片] - 概率与期望
本帖最后由 柿子饼同学 于 2024-8-30 19:10 编辑期望的三种计算方式:
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 == 'x') {
l1 = l2 = 0;
continue;
}
// P(i) 代表 s 是 o 的概率
// 线性的加是没事的
// 当前能否拓展 1 ? 如果能就加上 ^2/^3 的增量再乘概率
a1 = a1 + 1 * P(s);
a2 = a2 + (2 * l1 + 1) * P(s);
a3 = a3 + (3 * l2 + 3 * l1 + 1) * P(s);
// 注意这里先更新 l2
l2 = (l2 + l1 * 2 + 1) * P(s);
l1 = (l1 + 1) * P(s);
}
F - 奖励关
bool Ismet(int x, int st) { return ((st & req) == req); }
// 考虑决策, 每个物品取或者不取
db dfs(int pos, int st) {
if (pos > k)
return 0;
if (vis)
return f;
vis = 1;
for (int i = 0; i < n; i++) {
if (Ismet(i, st)) {
f += max(dfs(pos + 1, st), dfs(pos + 1, st | (1 << i)) + val) / n;
} else {
f += dfs(pos + 1, st) / n;
}
}
return f;
}
G - 放棋子
终点太多, 考虑先计算概率再算期望, 刷表, 分类讨论
需要注意的是这个 f 在任务结束之后仍然会更新下一天的, 所以就相当于前缀和了
cin >> T;
while (T--) {
cin >> n >> m;
memset(f, 0, sizeof(f));
f = 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 += f * (j * k - i) / s;
f += f * k * (n - j) / s;
f += f * j * (m - k) / s;
f += f * (n - j) * (m - k) / s;
}
}
}
db ans = 0;
for (int i = 1; i <= n * m; i++) {
ans += i * (f - f);
}
cout << fixed << setprecision(9) << ans << '\n';
}
H - 扑克牌
状态设的是每个牌翻了几个, 并且大王小王分别变成了哪些牌
db dfs(int a, int b, int c, int d, int x, int y) {
auto &res = f;
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 = f = 0;
for(int i = 2; i <= n; i++){
for(int j = 0; j <= min(i, m); j++){
f = f = 1e10;
Min(f, f + dis]]);
if(j >= 1){
// 上一轮可能申请不成功
Min(f, f + k*dis]] + (1 - k)*dis]]);
// 这一轮可能申请不成功
Min(f, f + k*dis]] + (1 - k)*dis]]);
}
if(j > 1){
Min(f, f + (1 - k)*(1 - k)*dis]]\
+ (1 - k)*k*dis]]\
+ k*(1 - k)*dis]]\
+ k*k*dis]]);
}
}
}
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 = sigma((f + 1) * ai * aj / s) + (f + 1) * c / s
// 移项就行了
struct DSU {
int f, siz;
DSU() {
for (int i = 1; i < N; i++) {
f = i;
siz = 1;
}
}
int Find(int x) {
if (x == f)
return x;
return (f = Find(f));
}
void Merge(int x, int y) {
x = Find(x), y = Find(y);
if (x == y)
return;
siz += siz;
f = f;
}
} dsu;
int n, m;
map<mt, db> f;
mt org;
db Solve(mt u) {
if (u.size() == 1)
return 0;
if (f)
return f;
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 = 1.0 * (r + c) / (s - c);
return f;
}
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);
}
}
cout << fixed << setprecision(6) << Solve(org);
return 0;
}
两个题没写, 一个高斯消元, 一个 kmp
L - 弹钢琴
J - 小卖部
给出一个 n*m 的网格图，小C要从家前往小卖部，
小C每次会随机向相邻的四个方向中不为障碍物的方向移动一个格子，求到达小卖部的期望步数。 鱼油好！看得出来你在学习期望值相关的内容。这里简要总结一下核心概念和几个问题的解题方法：
### 期望的计算方式
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 == 'o')
f = f + 1;
else
f = 0;
ans_l += f;
ans_l2 += f * f;
ans_l3 += f * f * f;
}
你可以用这些简洁的方法来处理包含期望值计算的问题，希望对你有帮助！如果有更多问题，欢迎继续提问。
以上回复来自 FishC AI 小助理，如未能正确解答您的问题，请继续追问。 {:10_275:} sfqxx 发表于 2024-8-30 20:54
{:10_256:} {:10_284:} {:10_256:}{:10_256:} {:7_113:} {:10_254:}看看 谢谢 666 666 {:5_111:}{:5_111:}{:5_111:}
页:
[1]