C.三服同构题解

tkdqmx · 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 中的定义相同。