zoj 3551 – Bloodsucker

吸血鬼,挺有意思的,概率数列题。

村子里有 n-1 个人,1 个吸血鬼,每天随机抽取两个家伙进行反应,如果是一个人一个鬼,那么有 p 的概率会把人变成吸血鬼,求全部变成吸血鬼的期望天数。

分析一下,假设 n, p 为常数 E(k) 为有 k 只吸血鬼的期望天数,不难发现,其实从 E(k) 到 E(k+1) 有一个直接的递推关系。

初始值,E(1) = 0,现在要求 E(n)。

然后我们说一下这个递推关系:

  1. 如果有 k 只鬼,那么每个晚上可以变成 k+1 只鬼的概率是:
q = p*k*(n-k)/c(n,2) = 2*p*k*(n-k)/n/(n+1)
  1. 然后有:
E(k+1) = E(k) + 1*q + 2*q*(1-q) + 3*q*(1-q)^2 + ...
  1. 对于上式右侧的数列,高中的时候学过,可以这样解:

设:

s = q * (1 + 2*(1-q) + 3*(1-q)^2 + ...)

则:

(1-q)*s = q * (0 + (1-q) + 2*(1-q)^2 + ...)

两式相减得到:

s * q = q * (1 + (1-q) + (1-q)^2 + (1-q)^3 + ...)

这是一个等比数列的所有项和,因此:

s = 1 / q

多么优美的结果,也就是说:

E(k+1) = E(k) + 1/q

所以,我们将 k 从 1 遍历到 n-1,求出对应的 1/q,累加起来,就得到了结果。

// 3493567 2013-12-21 18:16:02 Accepted 3551 C++ 90 168 呆滞的慢板

#include <cstdio>

int main() {

    int t, n, k;
    double p, ans;

    for(scanf("%d", &t); t--;) {
        scanf("%d%lf", &n, &p);
        for(ans = 0, k = 1; k < n; ++k)
            ans += 1.0/k/(n-k);
        printf("%.3lf\n", 0.5*n*(n-1)/p*ans);
    }

}

【转载请附】愿以此功德,回向 >>

原文链接:http://www.huangwenchao.com.cn/2013/12/zoj3551.html【zoj 3551 – Bloodsucker】

发表评论

电子邮件地址不会被公开。 必填项已用*标注