天依题 +1 || solution - P9156

littlebug · 2025-08-15 22:05:08 · 题解

南北组太甜了啊啊啊。

可能看上去有点吓人，但实际上还是比较简单的。

考虑 dp，注意到结果仅和剩余牌数和已知的牌数有关，所以令 f_{i,j} 表示剩余 i 对牌，其中有 j 张已知，此时先手期望得分比后手期望得分高的分数。

先不考虑平局。令已知点数为 S，牌 x 的点数表示为 v_x，有三种操作方式：

• 取两张已知牌，这样就相当于跳过该回合，所以就直接从后手状态转移：

  f_{i,j} \xleftarrow{\max} -f_{i,j}

• 取一张已知牌 a，一张未知牌 b，简单分讨一下这两张牌的情况：

  • 有 \frac 1 {2i-j} 的概率 v_a = v_b，此时先手还是先手，并且分数加一，故从 1 + f_{i-1,j-1} 转移。
  • 有 \frac {j-1} {2i-j} 的概率 v_b \ne v_a \land v_b \in S，此时先手转为后手，并且后手就知道了一对已知牌，那么一定会选择这一对已知牌（后手分数加一），并且这之后还是后手，故从 -(1 + f_{i-1,j-1}) 转移。
  • 有 \frac {2(i-j)} {2i-j} 的概率 v_a \ne v_b \land v_b \notin S，此时先手转为后手，盘面上多了一张已知牌，故从 -f_{i,j+1} 转移。

  于是可以得到转移式子：

  f_{i,j} \xleftarrow{\max} \frac 1 {2i-j} (1 + f_{i-1,j-1}) - \frac {j-1} {2i-j} (1 + f_{i-1,j-1}) - \frac {2(i-j)} {2i-j} f_{i,j+1}

• 取两张未知牌 a,b，同上，类似地分讨：

  • 有 \frac {i-j} {\binom {2i-j} 2} 的概率 v_a = v_b，从 1 + f_{i-1,j} 转移。
  • 有 \frac {\binom j 2} {\binom {2i-j} 2} 的概率 v_a \ne v_b \land v_a \in S \land v_b \in S，从 -(2 + f_{i-2,j-2}) 转移。
  • 有 \frac {j \times 2(i-j)} {\binom {2i-j} 2} 的概率 v_a \ne v_b \land v_a \in S \land v_b \notin S，从 -(1+f_{i-1,j}) 转移。
  • 有 \frac {2 (i-j) (i-j-1)} {\binom {2i-j} 2} 的概率 v_a \ne v_b \land v_a \notin S \land v_b \notin S，从 -f_{i,j+2} 转移。

  转移式子：

  f_{i,j} \xleftarrow{\max} \frac {i-j} {\binom {2i-j} 2} (1 + f_{i-1,j}) - \frac {\binom j 2} {\binom {2i-j} 2} (2 + f_{i-2,j-2}) - \frac{j \times 2(i-j)} {\binom {2i-j} 2} (1 + f_{i-1,j}) - \frac {2 (i-j) (i-j-1)} {\binom {2i-j} 2} f_{i,j+2}

然后再来看平局的情况。注意到如果按照第一种情况，从本身的负状态转移，那么后手也一定会从本身的负状态转移，这样就导致了游戏无法结束，于是就不得不平局了。所以平局就等价于跟 0 取 \max。

时间复杂度 O(n^2)。

注意到多测，但不需要也不能清空，因为对于任意 f_{i,j} 的取值与总数无关。如果清空则会在复杂度上乘上一个 T，会 T 飞。

需要进行一些特判，具体见代码。

代码：

int n,m;
double f[N][N];
bitset <N> vis[N];

il double dp(int i,int j)
{
    if(i<=0 || j<0 || i<j) return 0.;
    if(vis[i][j]) return f[i][j];

    f[i][j]=(j>=2 ? 0. : -1e100);
    j>=1 && chmax(f[i][j] , (1.*(1+dp(i-1,j-1)) - 1.*(j-1)*(1+dp(i-1,j-1)) - 2.*(i-j)*dp(i,j+1)) /(2*i-j));
    2*i-j>=2 && chmax(f[i][j] , (1.*(i-j)*(1+dp(i-1,j)) - 1.*j*(j-1)/2.*(2+dp(i-2,j-2)) - 2.*j*(i-j)*(1+dp(i-1,j)) - 2.*(i-j)*(i-j-1)*dp(i,j+2)) *2./(2*i-j)/(2*i-j-1));

    return vis[i][j]=1,f[i][j];
}

il void solve()
{
    read(n,m);
    printf("%.20Lf\n",n/2.+dp(n,m)/2.);
}

华风夏韵，洛水天依！