1 条题解

  • 0
    @ 2026-11-12 21:57:31

    [I] Coins(dp_i)题解

    题意简述

    NN 枚硬币(NN 为奇数),第 ii 枚正面概率 pip_i。全部抛一次,求正面数严格多于反面数的概率。

    思路

    状态

    设 fjf_{j} = 考虑完前 ii 枚硬币后,"正面数 − 反面数"为 jj 的概率。jj 的范围是 [−i,i][-i, i],用偏移 N+1N+1 存成数组下标避免负数。

    转移

    对第 ii 枚硬币(正面概率 pp):

    $$f'_{j+1} \mathrel{+}= f_j \cdot p,\qquad f'_{j-1} \mathrel{+}= f_j \cdot (1-p).$$

    得到 NN 枚全部处理完的 ff 后,答案:

    ∑j>0fj.\sum_{j > 0} f_j .

    因为 NN 为奇数,正面严格多于反面等价于 j≥1j \ge 1。

    另一种等价写法

    设 gkg_{k} = 正面恰好 kk 枚的概率:

    gk′=gk−1p+gk(1−p),g'_k = g_{k-1} p + g_k (1-p),

    答案 ∑k>N/2gk\sum_{k > N/2} g_k。两种写法等价,本题解用第一种。

    复杂度

    时间 O(N2)≤9×106O(N^2) \le 9\times10^6,空间 O(N)O(N)。

    参考代码

    #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;
    }
    

    易错点

    1. 下标偏移:jj 可为负,没有偏移就会越界。sz 要留足 2N+32N+3 的余量,防止 j-1 越界。
    2. 答案区间是 j≥1j \ge 1(正面多),不是 j≥0j \ge 0;NN 为奇数时 j=0j=0 不可能出现。
    3. 输出误差:SPJ 判绝对误差 ≤10−9\le 10^{-9},所以 %.12f 足够;但小数位数太少(如 %f 只有 6 位)也可能不够——本解输出 12 位小数。
    4. 别用 float,精度不够。

    数据说明

    共 16 组:3 组官方样例;N=1N=1 的 0.50/0.01/0.990.50/0.01/0.99;N=3N=3 全 0.50.5;N=5N=5 全 0.990.99(答案接近 11)与全 0.010.01;N=101/301/1001N=101/301/1001 随机;N=2999N=2999 随机三组与全 0.500.50(最坏规模、误差最敏感)。

    • 1

    信息

    ID
    18
    时间
    2000ms
    内存
    256MiB
    难度
    5
    标签
    递交数
    2
    已通过
    1
    上传者