1 条题解
-
0
[I] Coins(dp_i)题解
题意简述
枚硬币( 为奇数),第 枚正面概率 。全部抛一次,求正面数严格多于反面数的概率。
思路
状态
设 = 考虑完前 枚硬币后,"正面数 − 反面数"为 的概率。 的范围是 ,用偏移 存成数组下标避免负数。
转移
对第 枚硬币(正面概率 ):
$$f'_{j+1} \mathrel{+}= f_j \cdot p,\qquad f'_{j-1} \mathrel{+}= f_j \cdot (1-p).$$得到 枚全部处理完的 后,答案:
因为 为奇数,正面严格多于反面等价于 。
另一种等价写法
设 = 正面恰好 枚的概率:
答案 。两种写法等价,本题解用第一种。
复杂度
时间 ,空间 。
参考代码
#include <cstdio> using namespace std; double f[6005], g[6005]; int main() { int n; scanf("%d", &n); int off = n + 1, sz = 2 * n + 3; f[off] = 1.0; for (int i = 0; i < n; i++) { double p; scanf("%lf", &p); for (int j = 0; j < sz; j++) g[j] = 0.0; for (int j = 0; j < sz; j++) { if (f[j] == 0.0) continue; g[j + 1] += f[j] * p; g[j - 1] += f[j] * (1.0 - p); } for (int j = 0; j < sz; j++) f[j] = g[j]; } double ans = 0; for (int j = off + 1; j < sz; j++) ans += f[j]; printf("%.12f\n", ans); return 0; }易错点
- 下标偏移: 可为负,没有偏移就会越界。
sz要留足 的余量,防止j-1越界。 - 答案区间是 (正面多),不是 ; 为奇数时 不可能出现。
- 输出误差:SPJ 判绝对误差 ,所以
%.12f足够;但小数位数太少(如%f只有 6 位)也可能不够——本解输出 12 位小数。 - 别用
float,精度不够。
数据说明
共 16 组:3 组官方样例; 的 ; 全 ; 全 (答案接近 )与全 ; 随机; 随机三组与全 (最坏规模、误差最敏感)。
- 下标偏移: 可为负,没有偏移就会越界。
- 1
信息
- ID
- 18
- 时间
- 2000ms
- 内存
- 256MiB
- 难度
- 5
- 标签
- 递交数
- 2
- 已通过
- 1
- 上传者