题解：P12061 [THUPC 2025 决赛] 喜爱之钥

Lyrella · 2025-06-26 21:14:29 · 题解

前言

困难题。前置知识：一点古典概型知识。

题解

注意到每个人均按照最优决策，所以在决策时我们需要去选择成功概率最大的。假设现在有 x 个锁，x+y 个钥匙。对于第一个人成功的概率为 {x\over x(x+y)}={1\over x+y}。我们称第一个人选择的锁和钥匙为一号锁、钥匙，现在去考虑第二个人以及后面人的情况：

• 选择一号锁和非一号钥匙。因为我们排除了一号钥匙所以还剩下 x+y-1 个钥匙，故成功的概率为 1\over x+y-1。
• 选择非一号锁和一号钥匙。成功的概率也为 1\over x+y-1。接下来考虑证明。

设 A,B,C 分别为第一个人拿到的钥匙为真的，第一个人失败，第二个人成功，下面有：

\begin{aligned} P(A|B)&={P(B|A)P(A)\over P(B)}\\&={{x-1\over x}\cdot{x\over x+y}\over{x+y-1\over x+y}}={x-1\over x+y-1}\\ P(C|B)&=P(A|B)P(C|AB)+P(\overline A|B)P(C|\overline AB)\\&={x-1\over x+y-1}\cdot{1\over x-1}+0={1\over x+y-1} \end{aligned}

证毕。

• 选择非一号锁和非一号钥匙。成功的概率为 (1-{1\over x+y-1}){1\over x+y-1}={x+y-2\over (x+y-1)^2}<{1\over x+y-1}，所以不进行此种决策。

所以第二个人会选择与第一个人相同的锁或钥匙，并且选择锁或者钥匙的概率相同，所以第二个人会有 {x-1\over 2x+y-2} 的概率选择锁，有 x+y-1\over 2x+y-2 的概率选择钥匙。并且如果第二个人选了锁，接下来的人就会一直选相同的锁直到锁开；否则就是一直选相同的钥匙直到发现其是假钥匙或者开了一把锁。因为这样他们的成功率比没有任何信息去瞎蒙的情况成功概率更高。并且我们可以计算第二个人成功的概率：(1-{1\over x+y})\cdot{1\over x+y-1}={1\over x+y}，和第一个人相同，以此类推可得到后面的成功概率同样为 {1\over x+y}。

也就是说除了第一个人外，我们对于相同的 x,y 都进行本质相同的操作（选相同的锁/钥匙），并且成功概率相同。这个问题我们尝试 dp 解决。设 f_{i,j,c} 表示现有 i 个锁 i+j 个钥匙，轮到了第 c 个人期望成功次数。

首先肯定从 x=1,y=0 的情况开始倒推（废话？）。我们进行一点小分讨进行转移：

• 选择的是能够配对的锁或钥匙，有 f_{i,j,c}\leftarrow f_{i-1,j,c-l}。首先注意 c-l 是在模 n 意义下的，因为这 n 个人是轮着来的。然后我们要将锁和钥匙稍微分开处理，首先是因为选择相同锁或钥匙的概率不同，其次就是注意枚举的 l 的上界也不同。具体的，对于锁来说，因为最多就 i 把所以上界为 i；对于钥匙上界就可以到 i+j。转移式就是：f_{i,j,c} = {\left((i-1)\sum f_{i-1,j,c-l}\right)+\left((i+j-1)\sum f_{i-1,j,c-l}\right)\over (i+j)(2i+j-2) }。

• 注意如果只选钥匙的时候我们还可以有 f_{i,j,c}\leftarrow f_{i,j-1,c-i}，因为我们如果要发现这个钥匙是假的需要让 n 个人轮 i 次，每次选相同的这个假钥匙，所以有 f_{i,j,c}={j\over i+j}\cdot{i-1\over 2i+j-2}\cdot f_{i,j-1,c-i}。因为每次要选锁，所以还要乘选择锁的系数，然后那个 {j\over i+j} 是选到假钥匙的概率。

• 最后还要考虑的是这一次本身成功的贡献。考虑是固定一个相同的锁还是钥匙，直接拿成功的概率乘上每次选择的概率即可。

直接做时间复杂度 O(n^2LK)，记得对于第一种情况进行前缀和优化，最后时间复杂度 O(nLK)。

代码就不放了，原因有二。一是这道题的代码是小清新；二是我觉得我的讲解已经足够清晰，你就算直接抄上面的转移式似乎也能写出来。

感觉这道题挺难的，能看到这里的也很不容易，要不点个免费的赞再走？求你了。