自动搬运

查看原文

来自洛谷，原作者为

	littlebug AFO. || 女孩纸喵 > < || 喜欢天依宝宝喵 > <

搬运于2025-08-24 22:45:53，当前版本为作者最后更新于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.);
}

华风夏韵，洛水天依！