CF1599C Bubble Strike 题解

· · 题解

这题还没有中文翻译。这里提供一个我粗略译的中文版题面。

题目大意

有 N 个棋子，其中 k 个子是黑棋，另外 N-k 个是白棋。从中随机选取三个棋子，你可以去掉其中一个棋子（你知道每个棋子的颜色），再在剩下的两个棋子中随机取出一个。设这个棋子为黑的概率为 P_k 。

你希望取出黑子的概率至少为 P. 求出一个最小的 k, 使得 P_k \ge P.

输入格式

一行，第一个数是正整数 N(3\le N\le 10^{3})，表示棋数；接着是一个小数 P(0\le P\le1), 表示所需概率。两个数用空格隔开，保证 P 的小数点后至多有四位。

输出格式

一行，一个正整数 k. 表示黑棋的最少数量。

做法

一道比较水的 2000 分题。

考虑有 k 个黑棋时，每次操作取到黑棋的平均概率。

因为每次都是完全随机去取，所以总的黑棋期望数除以总取法数就等于概率了。

总取法数为从 n 个子中取 3 个，即 C^{3}_{n}.

接下来算每个情况中黑棋被取到的期望次数。

情况 1

如果取到的白棋有 0 个，黑棋有 3 个，则方案数为 C^{3}_{k}\times C^{0}_{n-k}=C^{3}_{k}.

无论怎么随机取，因为这三个都是黑色的，所以最终一定能取到黑色的，即单次取到黑棋的期望次数为 1 ，总期望为 C^{3}_{k}\times 1.

情况 2

如果取到的白棋有 1 个，黑棋有 2 个，则方案数为 C^{2}_{k}\times C^{1}_{n-k}.

你取到了两黑一白，那么只需要把那个白色的丢掉即可。这样能保证你一定能取到黑棋。单次取到黑棋的期望次数为 1 ，则总期望为 C^{2}_{k}\times C^{1}_{n-k}\times 1.

情况 3

如果取到的白棋有 2 个，黑棋有 1 个，则方案数为 C^{1}_{k}\times C^{2}_{n-k}.

为了尽量取到黑棋，你需要把一个白棋丢掉。此时还剩下一黑一白。接下来的选棋是随机的，所以单次取到黑棋的期望次数为 \frac{1}{2}，总期望为 C^{1}_{k}\times C^{2}_{n-k}\times \frac{1}{2}.

情况 4

如果取到的白棋有 3 个，黑棋有 0 个，则方案数为 C^{0}_{k}\times C^{3}_{n-k}=C^{3}_{n-k}.

三个棋全是白棋，那无论如何都取不到黑棋。期望次数为 0 ，总期望次数也为 0.

把上面四种情况的期望加起来再除以总次数，就得到了 k 个黑棋时的概率。

枚举 k 从 0 到 n，第一个能使取黑棋概率大于等于 P 的 k 即所求。

代码实现非常简单。时间复杂度 O(n).

#include <bits/stdc++.h>
using namespace std;
#define db double
const int maxn=100010;
db ans,p;
int n;
int C(int n,int m)
{
    if (n==0||n<m) return 0;
    int res=1;
    for (int i=1;i<=m;i++) res*=n-i+1;
    for (int i=1;i<=m;i++) res/=i;
    return res;
}
int main()
{
    scanf("%d%lf",&n,&p);
    int all=C(n,3);
    for (int i=0;i<=n;i++)
    {
        int h0b3=C(n-i,3),h1b2=C(n-i,2)*C(i,1),h2b1=C(n-i,1)*C(i,2),h3b0=C(i,3);
        db res=h0b3*0+h1b2*0.5+h2b1*1.0+h3b0*1.0;
        if (res>=p*(db)all) printf("%d\n",i),exit(0);
    }
}