Codeforces 540D Bad Luck Island 题解

发表于 | 更新于 | 阅读次数：
本文字数： 783 字 | 阅读时长 ≈ 4 分钟

题意简述

一个岛屿上有$a$只A类生物，$b$只B类生物,$c$只C类生物。其中A吃B，B吃C，C吃A。每个时刻，每一对动物相遇的概率都是等概率的。若干时刻后，岛屿上应该只剩下一种动物。对于A,B,C，求出剩下的最后一种动物是A，B，C的概率。$1<=a,b,c<=100$

思路

设状态

由于a,b,c<=100，容易得到$dp[i][j][k]$表示剩下$i$个A，$j$个B，$k$个C。很明显。

转移

首先，$dp[i][j][k]$珂以由$dp[i+1][j][k],dp[i][j+1][k],dp[i][j][k+1$转移过来。由于三种情况相似，就只讨论一种，写代码的时候基本就是复制然后改改了。

dp[i+1][j][k]转移到dp[i][j][k]

那就是死了一个A种生物。也就是上一秒一个A生物和一个C生物相遇了。总共的方案数是$(i+1)j+(i+1)k+jk$，一个A一个C有$(i+1)k$中情况，那么概率就是$\dfrac{(i+1)k}{(i+1)j+(i+1)k+jk}$。用这个式子乘以$dp[i+1][j][k]$即珂。

然后把三个情况加起来就是$dp[i][j][k]$的概率了。注意特判分母为零的情况，这个时候要令分数值为0。因为我们的转移中是要舍去这种情况的。

最后的答案：A存活的概率就是$dp[1,2….n][0][0]$，B存活的概率就是$dp[0][1,2…n][0]$，C存活的概率就是$dp[0][0][1,2…n]$

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
#include <bits/stdc++.h>
using namespace std;
namespace Flandre_Scarlet
{
    #define N 122
    #define real double
    #define EPS 1e-8
    #define F(i,l,r) for(int i=l;i<=r;++i)
    #define D(i,r,l) for(int i=r;i>=l;--i)
    #define Fs(i,l,r,c) for(int i=l;i<=r;c)
    #define Ds(i,r,l,c) for(int i=r;i>=l;c)
    #define Tra(i,u) for(int i=G.Start(u),__v=G.To(i);~i;i=G.Next(i),__v=G.To(i))
    #define MEM(x,a) memset(x,a,sizeof(x))
    #define FK(x) MEM(x,0)

    int a,b,c;
    void Input()
    {
        cin>>a>>b>>c;
    }

    real dp[N][N][N];
    void Soviet()
    {
        FK(dp);
        dp[a][b][c]=1.00;
        D(i,a,0) D(j,b,0) D(k,c,0)
        {
            if(i==a and j==b and k==c) continue;
            real ii=i,jj=j,kk=k;

            dp[i][j][k]=0.00;
            real all,p;

            all=(ii+1)*jj+(ii+1)*kk+jj*kk;//总共的情况，如果为0，那就令p=0
            p=(ii+1)*k;p/=all;if (fabs(all)<EPS) p=0.00;//p: 概率
            dp[i][j][k]+=p*dp[i+1][j][k];

            all=ii*(jj+1)+ii*kk+(jj+1)*kk;
            p=(jj+1)*ii;p/=all;if (fabs(all)<EPS) p=0.00;
            dp[i][j][k]+=p*dp[i][j+1][k];

            all=ii*jj+ii*(kk+1)+jj*(kk+1);
            p=(k+1)*jj;p/=all;if (fabs(all)<EPS) p=0.00;
            dp[i][j][k]+=p*dp[i][j][k+1];//这两个同理
        }
        real aa=0.00,bb=0.00,cc=0.00;
        F(i,1,a) aa+=dp[i][0][0];
        F(i,1,b) bb+=dp[0][i][0];
        F(i,1,c) cc+=dp[0][0][i];
        printf("%.9f %.9f %.9f\n",aa,bb,cc);
    }

    #define Flan void
    Flan IsMyWife()
    {
        Input();
        Soviet();
    }
}
int main()
{
    Flandre_Scarlet::IsMyWife();
    getchar();getchar();
    return 0;
}
w