题解：CF1599C Bubble Strike

TCY1234567 · 2026-06-10 20:41:27 · 题解

题解

难度并不大，感觉其实评不到 2000。

我们可以将这题拆分成 2 个阶段，第一个阶段是从 n 个选 3 个，第二个阶段是从 3 个里禁止。

发现第二阶段中选出的地图很少，考虑分类讨论。

对于 3 个地图中有 0 个学习过的，那么不可能有学习过的，概率为 0。

有 1 个学习过时，因为自己不会禁止自己会的地图，所以概率为 \frac{1}{2}。

有 2 或 3 个时，还是因为自己尽量不会禁止自己会的地图，所以概率均为 1。

最后考虑怎么算答案，其实直接枚举学过的地图数量即可，对于第一阶段，直接用组合数处理即可。

代码

#include <bits/stdc++.h>
using namespace std;
double C(int n,int m)
{
    if(m<0||m>n) return 0;
    double cnt = 1;
    for(int i=1;i<=m;i++) cnt = cnt*(n-m+i)/i;
    return cnt;
} 
int main()
{
    int n;
    double p;
    scanf("%d%lf",&n,&p);
    for(int i=0;i<=n;i++)
    {
        int c3 = C(i,3);
        int c2 = C(i,2)*C(n-i,1);
        int c1 = C(i,1)*C(n-i,2);
        int c0 = C(n-i,3);
        double p2 = (c3+c2+0.5*c1)/(c3+c2+c1+c0);
        if(p2>=p)
        {
            printf("%d\n",i);
            return 0;
        }
    }
}