【HDU】5816 Hearthstone

12 Aug 2016

Hearthstone

题目链接

Hearthstone

题目大意

说有那么一种人玩炉石是神抽狗，总能抽到他想要的牌（确实），现在你的牌组中只有两种牌，一种是奥数智慧（可以抽两张牌），另外一种是伤害牌（可以造成X种伤害）。现在告诉你2种牌的数量，对手的HP，和每一张伤害牌的伤害，问你在第一回合就能取胜的概率是多少。

题解

很明显，这里只有当牌组里没牌的时候或者手上全是伤害的时候是最终状态，所以我们可以考虑首先预处理出： \[ d[i]:取i张伤害牌时取胜的概率。 \] 有了d[i]之后，我们就可以通过搜索搜出取i张伤害牌的概率，再来乘上这个概率就行了，于是我们定义\(dfs(A,B,a,b)\)为现在牌组中有A张A牌，B张B牌，手上有a张A牌，b张B的概率，有了这个定义，我们可以很快计算出结果～

代码

这个跑了46ms，还是挺快的。这一题因为最后要输出分数，所以搜的时候只能麻烦一点用分数存了。

#include <iostream>
#include <cstring>
#include <cstdio>
#define LL long long

using namespace std;

struct divrua
{
    LL a,b;
};
divrua d[25],dp[25][25][25][25];;
int c[25],p,n,m,T;

LL gcd(LL a,LL b)
{
    if (b==0) return a;
    return gcd(b,a%b);
}

void setup()
{
    int high=1<<m;
    for (int i=1;i<high;i++)
    {
        int cnt=0,sum=0;
        for (int j=0;j<20;j++) if ((1<<j)&i)
        {
            cnt++;
            sum+=c[j];
        }
        if (sum>=p) d[cnt].a++;
        d[cnt].b++;
    }
    for (int i=1;i<=20;i++) if (d[i].a)
    {
        int c=gcd(d[i].a,d[i].b);
        d[i].a/=c; d[i].b/=c;
    }
}

divrua sum(divrua a,divrua b)
{
    if (b.a==0) return a;
    if (a.a==0) return b;
    divrua t; LL c=0;
    t.a=a.a*b.b+b.a*a.b;
    t.b=a.b*b.b;
    if (t.a)
    {
        c=gcd(t.a,t.b);
        t.a/=c; t.b/=c;
    }
    return t;
}

divrua dfs(LL A,LL B,int a,int b)
{
    if (dp[A][B][a][b].b) return dp[A][B][a][b];
    divrua t,x1,x2,x3;
    x1.a=0; x1.b=0; x2.a=0; x2.b=0; x3.a=0; x3.b=0;
    if (a==0 || B==0 ) return d[b];
    if (A+B<=2) return dfs(0,0,a+A-1,b+B);
    if (A>=2)
    {
        t=dfs(A-2,B,a+1,b);
        x1.a=(A-1)*A*t.a/2;
        x1.b=(A+B)*(A+B-1)*t.b/2;

    }
    if (B>=2)
    {
        t=dfs(A,B-2,a-1,b+2);
        x2.a=(B-1)*B*t.a;
        x2.b=(A+B)*(A+B-1)*t.b;
    }
    t=dfs(A-1,B-1,a,b+1);
    x3.a=A*B*t.a;
    x3.b=(A+B)*(A+B-1)*t.b/2;
    t=sum(x1,x2);
    t=sum(t,x3);
    dp[A][B][a][b]=t;
    return t;
}

int main()
{
    scanf("%d",&T);
    while (T--)
    {
        memset(d,0,sizeof(d));
        memset(dp,0,sizeof(dp));
        scanf("%d%d%d",&p,&n,&m);
        for (int i=0;i<m;i++) scanf("%d",&c[i]);
        setup();
        divrua x1,x2,t,ans;
        t=dfs(n-1,m,1,0);
        x1.a=n*t.a; x1.b=(n+m)*t.b;
        t=dfs(n,m-1,0,1);
        x2.a=m*t.a; x2.b=(n+m)*t.b;
        ans=sum(x1,x2);
        if (ans.a)
        {
            LL c=gcd(ans.a,ans.b);
            ans.a/=c; ans.b/=c;
        }
        else ans.b=1;
        printf("%I64d/%I64d\n",ans.a,ans.b);
    }
    return 0;
}