嘘~ 正在从服务器偷取页面 . . .

CF148D Bag of mice 题解

发布日期: 2024-05-26

更新日期: 2024-05-26

文章字数: 812

CF148D Bag of mice 题解

题意：

龙和公主在争论新年夜应该做什么。龙建议飞到山上观看在月光下跳舞的仙女，而公主认为他们应该早点睡觉。他们急于达成一个友好的协议，所以决定把这交给运气。

他们轮流从一个袋子里抽取老鼠，这个袋子里最初包含 $w$ 只白鼠和 $b$ 只黑鼠。第一个抽到白鼠的人获胜。在龙每次抽完老鼠后，袋子里的其余老鼠都会惊慌失措，其中一只会自己跳出袋子（公主抽老鼠时很小心，不会吓到其他老鼠）。公主先抽。公主获胜的概率是多少？

如果袋子里没有老鼠了，并且没有人抽到白鼠，则龙获胜。自己跳出袋子的老鼠不算作被抽出（不决定胜负）。一旦老鼠离开袋子，它就不会再返回。每只老鼠被抽出的概率是相同的，每只老鼠跳出袋子的概率也是相同的。

输入格式：

唯一一行输入数据包含两个整数 $w$ 和 $b$（$0 \leq w, b \leq 1000$）。

输出格式：

输出公主获胜的概率。如果答案的绝对误差或相对误差不超过 $10^{-9}$，则认为答案是正确的。

不会翻译可以不翻译，有的人真是连 ChatGPT 都不如。

设 $f(i,j)$ 表示有 $i$ 只白老鼠和 $j$ 只黑老鼠时先手获胜的概率。

边界 $f(i,0)=1,~f(i,1)=\frac{i}{i+1}$ 。考虑转移，

先手抽到白鼠，获胜概率为 $\frac{i}{i+j}$ 。
先手抽到黑鼠，后手抽到白鼠，获胜概率为 $0$ 。
先手抽到黑鼠，后手抽到黑鼠，跑了一只白鼠，获胜概率为
$\frac{j}{i+j} \times \frac{j-1}{i+j-1} \times \frac{i}{i+j-2} \times f(i-1, j-2)$

先手抽到黑鼠，后手抽到黑鼠，跑了一只黑鼠，获胜概率为 $\frac{j}{i+j} \times \frac{j-1}{i+j-1} \times \frac{j-2}{i+j-2} \times f(i, j-3)$

因此

$\small f(i, j)=\frac{i}{i+j}+\frac{j}{i+j} \times \frac{j-1}{i+j-1} \times \frac{i}{i+j-2} \times f(i-1, j-2)+\frac{j}{i+j} \times \frac{j-1}{i+j-1} \times \frac{j-2}{i+j-2} \times f(i,j-3)$

最后答案就是 $f(n,m)$ 。

时间复杂度 $\mathcal{O}(nm)$

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)(1e3 + 15))

double f[N][N];
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    int n, m; cin >> n >> m;
    for(int i = 1; i <= n; i++) f[i][0] = 1, f[i][1] = (double)i / (i + 1);
    for(int i = 1; i <= n; i++)
        for(int j = 2; j <= m; j++)
        {
            f[i][j] = (double)i / (i + j);
            f[i][j] += (double)j / (i + j) * (j - 1) / (i + j - 1) * i / (i + j - 2) * f[i - 1][j - 2];
            if(j != 2) f[i][j] += (double)j / (i + j) * (j - 1) / (i + j - 1) * (j - 2) / (i + j - 2) * f[i][j - 3];
        }
    cout << fixed << setprecision(12) << f[n][m] << '\n';
    return 0;
}