自动搬运

查看原文

来自洛谷，原作者为

	tkdqmx 简称请用qmx||代词可以使用"它"||meow~

搬运于2025-08-24 23:03:59，当前版本为作者最后更新于2024-09-08 00:20:45，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

出题人题解

30pts

用搜索枚举分别得出对手手上有 $i$ 张 A 的概率 $f_i$；小 Q 打出 $i$ 张 A 后，其中有 $j$ 张是红桃的概率 $g_{i,j}$；在减少一张红桃 A 的基础上，小 Q 打出 $i$ 张 A 后，其中有 $j$ 张是红桃的概率 $h_{i,j}$。

然后就可以枚举对手手上有 $i$ 张 A 的情况，这时我们分两种情况讨论：

第一种，小 Q 耗费的第一张红桃牌为 K，这时还要分两种子情况讨论：

子情况一，小 Q 手上的 A 点大于等于 $i$，此时第一次决斗一定能将敌人手上的 A 耗完，且还能使对手受到伤害，而剩下多少张红桃牌，小 Q 就可以再使对手受到多少点伤害，这种情况下的期望伤害即为 $\sum_{j=0}^{j \leq \min(i,v)} f_i \times \frac{m-v}{m}\times g_{i,j}\times (m-j)$。

子情况二，小 Q 手上的 A 点小于敌人 $i$，此时第一次决斗会将小 Q 手上的 A 点耗完，敌人手上则会剩下 $i-u-v-1$ 张 A 点，因为小 Q 还剩下 $m-v-1$ 张红桃 K，而每张红桃 K，又能耗掉对手一张 A，耗完后就能使敌人受到伤害，所以这种情况下的期望伤害为 $f_i \times \frac{m-v}{m}\times \max(0,(m-v-1)-(i-u-v-1))=f_i \times \frac{m-v}{m}\times \max(0,m-i+u)$。

第二种，小 Q 耗费的第一张红桃牌为 A，这时仍然分两种子情况讨论：

子情况一，小 Q 手上剩余的 A 点大于等于 $i$，此时第一次决斗一定能将敌人手上的 A 耗完，且还能使对手受到伤害，而剩下多少张红桃牌，小 Q 就可以再使对手受到多少点伤害，这种情况下的期望伤害即为 $\sum_{j=0}^{j \leq \min(i,v-1)} f_i \times \frac{v}{m}\times h_{i,j}\times (m-j)$。

子情况二，小 Q 手上的 A 点小于敌人 $i$，此时第一次决斗会将小 Q 手上的 A 点耗完，敌人手上则会剩下 $i-u-v$ 张 A 点，因为小 Q 还剩下 $m-v$ 张红桃 K，而每张红桃 K，又能耗掉对手一张 A，耗完后就能使敌人受到伤害，所以这种情况下的期望伤害为 $f_i \times \frac{v}{m}\times \max(0,(m-v)-(i-u-v))=f_i \times \frac{v}{m}\times \max(0,m-i+u)$。

最后将所有 $i$ 的期望伤害相加即为答案，复杂度 $O(2^{n+m}+km)$。

100pts

在 30pts 的基础上，把三个数组的计算方式由搜索改为概率 DP 即可。

我们设 $f_{i,j}$ 表示对手前 $i$ 张牌中有 $j$ 张 A 的概率，则 $f_n$ 即为 30pts 中的 $f$，其它两个数组的状态定义与 30pts 中的定义相同。

$f_{i,j}$ 可以从 $f_{i-1,j}$ 和 $f_{i-1,j-1}$ 转移过来，转移方程为 $f_{i,j}=(1-a[i])\times f_{i-1,j}+a_i\times f_{i-1,j-1}$，分别表示这一张是 A 与不是 A 的转移。

$g_{i,j}$ 同样可以从 $g_{i-1,j}$ 和 $g_{i-1,j-1}$ 转移过来，转移方程为 $g_{i,j}=\frac{u-i+j+1}{u+v-i+1}\times g_{i-1,j}+\frac{v-j+1}{u+v-i+1}\times g_{i-1,j-1}$，分别表示这张打出的牌是红桃与不是红桃的转移。

$h_{i,j}$ 同样可以从 $h_{i-1,j}$ 和 $h_{i-1,j-1}$ 转移过来，转移方程为 $h_{i,j}=\frac{u-i+j+1}{u+v-i}\times h_{i-1,j}+\frac{v-j}{u+v-i}\times h_{i-1,j-1}$，分别表示这张打出的牌是红桃与不是红桃的转移。

最后答案的计算与 30pts 相同，总复杂度 $O(kn+km)$。

#include<bits/stdc++.h>
using namespace std;
#define N 2005
int n,m,u,v,k;
double ans,a[N],dp1[N][N],dp2[N<<1][N<<1],dp3[N<<1][N<<1];
int main(){
    dp1[0][0]=dp2[0][0]=dp3[0][0]=1;
    scanf("%d%d%d%d%d",&n,&m,&u,&v,&k);
    for(int i=1;i<=k;i++)  scanf("%lf",a+i);
    for(int i=1;i<=k;i++){
        dp1[i][0]=dp1[i-1][0]*(1-a[i]);
        for(int j=1;j<=i;j++)
            dp1[i][j]=dp1[i-1][j-1]*a[i]+dp1[i-1][j]*(1-a[i]);
    }
    for(int i=1;i<=min(u+v,k);i++){
        if(i<=u)  dp2[i][0]=dp2[i-1][0]*(u-i+1)/(u+v-i+1);
        for(int j=1;j<=min(i,v);j++){
            dp2[i][j]=dp2[i-1][j-1]*(v-j+1)/(u+v-i+1);
            if(i-j<=u)  dp2[i][j]+=dp2[i-1][j]*(u-i+j+1)/(u+v-i+1);
        }
    }
    for(int i=1;i<=min(u+v-1,k);i++){
        if(i<=u)  dp3[i][0]=dp3[i-1][0]*(u-i+1)/(u+v-i);
        for(int j=1;j<=min(i,v-1);j++){
            dp3[i][j]=dp3[i-1][j-1]*(v-j)/(u+v-i);
            if(i-j<=u)  dp3[i][j]+=dp3[i-1][j]*(u-i+j+1)/(u+v-i);
        }
    }
    for(int i=0;i<=k;i++){
        if(u+v>=i)
            for(int j=0;j<=min(i,v);j++)
                ans+=dp1[k][i]*(m-v)/m*dp2[i][j]*(m-j);
        else  ans+=dp1[k][i]*(m-v)/m*max(0,m-i+u);
        if(u+v>i)
            for(int j=0;j<=min(i,v-1);j++)
                ans+=dp1[k][i]*v/m*dp3[i][j]*(m-j);
        else  ans+=dp1[k][i]*v/m*max(0,m-i+u);
    }
    printf("%.9lf\n",ans);
}