概率与期望
前言
做到的与期望相关的题目都会放到这里 目前是照着一个题单再刷 如果是期望 \(dp\) 会同步放到这里
题目
1. \(CF865C\ Gotta\ Go\ Fast\)
我永远想不明白的期望题
二分一个期望通过时间 期望 \(dp\) 进行检验
状态 \(f_{i, j}\) 表示剩余 \(i\) 个关卡 剩余 \(j\) 的时间时期望通关的时间
转移 \(f_{i, j} = (f_{i + 1, j + a_i} + a_i) \times p_i / 100 + (f_{i + 1, j + b_i} + b_i) \times (100 - p_i) / 100\)
由于可以重来 对二分出的值取 \(\min\)
转移 \(f_{i, j} = \min\{mid, (f_{i + 1, j + a_i} + a_i) \times p_i / 100 + (f_{i + 1, j + b_i} + b_i) \times (100 - p_i) / 100\}\)
爆零小技巧
/*
Time: 5.15
Worker: Blank_space
Source: CF865C Gotta Go Fast
*/
/*--------------------------------------------*/
#include<cstdio>
#include<algorithm>
/*--------------------------------------头文件*/
const int A = 1e4 + 7;
const int B = 1e5 + 7;
const int C = 1e6 + 7;
const int D = 1e7 + 7;
const int mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;
/*------------------------------------常量定义*/
int n, m, a[60], b[60], p[60];
double f[60][5010];
/*------------------------------------变量定义*/
inline int read() {
int x = 0, f = 1; char ch = getchar();
while(ch < '0' || ch > '9') {if(ch == '-') f = -1; ch = getchar();}
while(ch >= '0' && ch <= '9') {x = (x << 3) + (x << 1) + (ch ^ 48); ch = getchar();}
return x * f;
}
/*----------------------------------------快读*/
bool check(double x) {
for(int i = n - 1; ~i; i--)
{
for(int j = m + 1; j < 5000; j++) f[i + 1][j] = x;
for(int j = 0; j <= m; j++)
f[i][j] = std::min(x, (f[i + 1][j + a[i]] + a[i]) * p[i] * 1.0 / 100 + (f[i + 1][j + b[i]] + b[i]) * (100 - p[i]) * 1.0 / 100);
}
return f[0][0] < x;
}
/*----------------------------------------函数*/
int main() {
n = read(); m = read();
for(int i = 0; i < n; i++) a[i] = read(), b[i] = read(), p[i] = read();
double l = 0, r = 1e10, mid = (l + r) / 2;
for(int i = 1; i <= 100; i++, mid = (l + r) / 2)
if(check(mid)) r = mid; else l = mid;
printf("%.10lf", l);
return 0;
}
2. \(P4550\) 收集邮票
第一个认真 颓 推的期望题
第 \(k\) 次需要支付 \(k\) 元钱 若一共购买了 \(x\) 次 则需要 \(\sum_{i = 1}^x i = \frac{x^2 + x}2\) 元
状态 \(g_i\) 表示已经买到了 \(i\) 种时 买全所有的还需要的期望次数 相应的 \(f_i\) 表示对应的二次方
转移 \(g_i = (g_i + 1)\frac in + (g_{i + 1} + 1)\frac {n - i}n\)
发现这个转移构成了环 将 \(g_i\) 弄到另一边 化简 得
\[g_i = \frac n{n - i} + g_{i + 1} \]相应的 有 \(f_i = (f_i + 2g_i + 1)\frac in + (f_{i + 1} + 2g_{i + 1} + 1)\frac {n - i}n\)
化简 得:
\[f_i = \frac n{n - i} + \frac{2ig_i}{n - i} + 2g_{i + 1} + f_{i + 1} \]代码
/*
Time: 5.15
Worker: Blank_space
Source: P4550 收集邮票
*/
/*--------------------------------------------*/
#include<cstdio>
/*--------------------------------------头文件*/
const int A = 1e4 + 7;
/*------------------------------------常量定义*/
int n;
double g[A], f[A];
/*------------------------------------变量定义*/
inline int read() {
int x = 0, f = 1; char ch = getchar();
while(ch < '0' || ch > '9') {if(ch == '-') f = -1; ch = getchar();}
while(ch >= '0' && ch <= '9') {x = (x << 3) + (x << 1) + (ch ^ 48); ch = getchar();}
return x * f;
}
/*----------------------------------------快读*/
/*----------------------------------------函数*/
int main() {
n = read();
for(int i = n - 1; ~i; i--)
g[i] = 1.0 * n / (n - i) + g[i + 1], f[i] = 1.0 * n / (n - i) + 2.0 * i * g[i] / (n - i) + 2 * g[i + 1] + f[i + 1];
printf("%.2lf", (g[0] + f[0]) / 2);
return 0;
}
3. \(P3802\) 小魔女帕琪
期望 \(dp\)
我发现这种题就是式子化一张纸 代码一两行 遇到直接推式子...
设 \(n = \sum_{i = 1}^7 a_i\)
考虑前七次触发的概率 为
\[\frac {a_1}{n} \times \frac {a_2}{n - 1}\times \frac {a_3}{n - 2}\times \frac {a_4}{n - 3}\times \frac {a_5}{n - 4}\times \frac {a_6}{n - 5}\times \frac {a_7}{n - 6} = \prod_{i = 1}^7 \frac {a_i}{n - i + 1} \]由于 \(a_i\) 的顺序 前面在乘上一个 \(7!\)
所以前七次能够触发的概率 设为 \(p_1\) 为
\[p_1 = 7! \times \prod_{i = 1}^7 \frac {a_i}{n - i + 1} \]考虑第八个继续触发的概率 其与第一个无关 若第一个随机到的为 \(a_1\) 那么有:
\[\frac {a_1}n \times \frac {a_1 - 1}{n - 1} \times \frac {a_2}{n - 2}\times \frac {a_3}{n - 3}\times \frac {a_4}{n - 4}\times \frac {a_5}{n - 5}\times \frac {a_6}{n - 6}\times \frac {a_7}{n - 7} = \frac{a_1 - 1}{n}\prod_{i = 1}^7 \frac{a_i}{n - i} \]第一个是随机的 所以概率 设为 \(p_2\) 为 :
\[\begin{array} \\ p_2 & = 7! \times \left( \frac{a_1 - 1}{n}\prod_{i = 1}^7 \frac{a_i}{n - i} + \frac{a_2 - 1}{n}\prod_{i = 1}^7 \frac{a_i}{n - i} + \frac{a_3 - 1}{n}\prod_{i = 1}^7 \frac{a_i}{n - i} + \frac{a_4 - 1}{n}\prod_{i = 1}^7 \frac{a_i}{n - i} + \frac{a_5 - 1}{n}\prod_{i = 1}^7 \frac{a_i}{n - i} + \frac{a_6 - 1}{n}\prod_{i = 1}^7 \frac{a_i}{n - i} + \frac{a_7 - 1}{n}\prod_{i = 1}^7 \frac{a_i}{n - i}\right)\\ & = 7! \times \frac{\sum_{i = 1}^7a_i - 7}{n} \times \prod_{i = 1}^7 \frac{a_i}{n - i}\\ & = 7! \times \frac{n - 7}{n} \times \prod_{i = 1}^7 \frac{a_i}{n - i}\\ & = 7! \times \frac{n - 7}{n} \times \frac {a_1}{n - 1} \times \frac {a_2}{n - 2}\times \frac {a_3}{n - 3}\times \frac {a_4}{n - 4}\times \frac {a_5}{n - 5}\times \frac {a_6}{n - 6}\times \frac {a_7}{n - 7}\\ & = 7! \times \prod_{i = 1}^7 \frac {a_i}{n - i + 1} \end{array} \]我们发现了什么
\[p_1 = p_2 \]这就好办了...
下面就不赘述了
代码
/*
Time: 5.15
Worker: Blank_space
Source: P3802 小魔女帕琪
*/
/*--------------------------------------------*/
#include<cstdio>
/*--------------------------------------头文件*/
int a[8], sum;
double ans = 1;
/*------------------------------------变量定义*/
inline int read() {
int x = 0, f = 1; char ch = getchar();
while(ch < '0' || ch > '9') {if(ch == '-') f = -1; ch = getchar();}
while(ch >= '0' && ch <= '9') {x = (x << 3) + (x << 1) + (ch ^ 48); ch = getchar();}
return x * f;
}
/*----------------------------------------快读*/
/*----------------------------------------函数*/
int main() {
for(int i = 1; i <= 7; i++) a[i] = read(), sum += a[i];
for(int i = 1; i <= 6; i++) ans *= a[i] * 1.0 / (sum + 1 - i) * i;
printf("%.3lf", ans * a[7] * 7.0);
return 0;
}