做到的与期望相关的题目都会放到这里 目前是照着一个题单再刷 如果是期望 \(dp\) 会同步放到这里
概率题都不是好东西
我永远想不明白的期望题
二分一个期望通过时间 期望 \(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;
}
第一个认真 颓 推的期望题
第 \(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\) 弄到另一边 化简 得
相应的 有 \(f_i = (f_i + 2g_i + 1)\frac in + (f_{i + 1} + 2g_{i + 1} + 1)\frac {n - i}n\)
化简 得:
代码
/*
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;
}
期望 \(dp\)
我发现这种题就是式子化一张纸 代码一两行 遇到直接推式子...
设 \(n = \sum_{i = 1}^7 a_i\)
考虑前七次触发的概率 为
由于 \(a_i\) 的顺序 前面在乘上一个 \(7!\)
所以前七次能够触发的概率 设为 \(p_1\) 为
考虑第八个继续触发的概率 其与第一个无关 若第一个随机到的为 \(a_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;
}
过于数学的证明方法我不会 只能感性理解
第一个人可能抢到的钱的区间为 \([0, w]\) 概率是均等的
也就是抢到每一个金额的概率都是 \(\frac 1{w + 1}\)
所以期望为
对于第二个人 剩余的钱就是 \(\frac w2\) 期望为 \(\frac w{2^2}\)
同理 第 \(k\) 个人获得的钱的期望为 \(\frac w{2^k}\)
/*
Time: 5.19
Worker: Blank_space
Source: P5104 红包发红包
*/
/*--------------------------------------------*/
#include<cstdio>
#define int long long
/*--------------------------------------头文件*/
const int mod = 1e9 + 7;
/*------------------------------------常量定义*/
int w, k;
/*------------------------------------变量定义*/
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 power(int a, int b, int res = 1) {for(; b; b >>= 1, a = a * a % mod) if(b & 1) res = res * a % mod; return res;}
/*----------------------------------------函数*/
signed main() {
w = read(); read(); k = read(); printf("%lld", w * power(power(2, k), mod - 2) % mod);
return 0;
}
结论: 有向无环图中路径长度的期望 \(\frac {len}{cnt}\)
怎么出来的 不知道 题解里都是这么说的
/*
Time: 5.19
Worker: Blank_space
Source: P6154 游走
*/
/*--------------------------------------------*/
#include<cstdio>
#define int long long
/*--------------------------------------头文件*/
const int A = 1e4 + 7;
const int B = 1e5 + 7;
const int C = 1e6 + 7;
const int D = 1e7 + 7;
const int mod = 998244353;
const int INF = 0x3f3f3f3f;
/*------------------------------------常量定义*/
int n, m, f[B << 1], g[B << 1], sum1, sum2;
struct edge {int v, nxt;} e[C << 1];
int head[B << 1], ecnt;
/*------------------------------------变量定义*/
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;
}
/*----------------------------------------快读*/
void add_edge(int u, int v) {e[++ecnt] = (edge){v, head[u]}; head[u] = ecnt;}
void dfs(int u) {
if(g[u]) return ; g[u] = 1;
for(int i = head[u], v = e[i].v; i; i = e[i].nxt, v = e[i].v)
dfs(v), g[u] = (g[u] + g[v]) % mod, f[u] = (f[u] + f[v] + g[v]) % mod;
sum1 = (sum1 + f[u]) % mod; sum2 = (sum2 + g[u]) % mod;
}
int power(int a, int b, int res = 1) {for(; b; a = a * a % mod, b >>= 1) if(b & 1) res = res * a % mod; return res;}
/*----------------------------------------函数*/
signed main() {
n = read(); m = read();
for(int i = 1; i <= m; i++) add_edge(read(), read());
for(int i = 1; i <= n; i++) if(!g[i]) dfs(i);
printf("%lld", sum1 * power(sum2, mod - 2) % mod);
return 0;
}
考虑 \(a_i\) 和 \(a_{i + 1}\) 两个位置
若 \(a_i = a_{i + 1}\) 则对第 \(i + 1\) 个位置有 \(\frac 1{a_i}\) 的概率答对
若 \(a_i < a_{i + 1}\) 则对第 \(i + 1\) 个位置有 \(\frac {a_i}{a_{i + 1}} \times \frac 1{a_i} = \frac 1{a_{i + 1}}\) 的概率答对
若 \(a_i > a_{i + 1}\) 则对第 \(i + 1\) 个位置有 \(\frac {a_{i + 1}}{a_i} \times \frac 1{a_{i + 1}} = \frac 1{a_i}\) 的概率答对
所以期望为 \(\sum_{i = 1}^n \frac 1{\max\{a_i, a_{i + 1}\}}\) (乘1略去了)
/*
Time: 5.19
Worker: Blank_space
Source: P1297 [国家集训队]单选错位
*/
/*--------------------------------------------*/
#include<cstdio>
#define int long long
#define Max(x, y) ((x) > (y) ? (x) : (y))
/*--------------------------------------头文件*/
const int D = 1e7 + 7;
const int mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;
/*------------------------------------常量定义*/
int n, A, B, C, a[D];
double ans;
/*------------------------------------变量定义*/
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;
}
/*----------------------------------------快读*/
/*----------------------------------------函数*/
signed main() {
n = read(); A = read(); B = read(); C = read(); a[n + 1] = a[1] = read();
for(int i = 2; i <= n; i++) a[i] = (a[i - 1] * A + B) % 100000001;
for(int i = 1; i <= n + 1; i++) a[i] = a[i] % C + 1;
for(int i = 1; i <= n; i++) ans += 1.0 / Max(a[i], a[i + 1]);
printf("%.3lf", ans);
return 0;
}
原文：https://www.cnblogs.com/blank-space-/p/14787105.html