1 条题解

  • 0
    @ 2024-12-19 12:58:44

    数据范围1000,很可能解法就是n方级别的了。 然后理解一下题意:游戏开始,如果第一轮A赢,则需要第一次就抽中白羽,否则这一轮需要两个人都抽中黑羽,然后一个羽毛消失,进入下一轮。很明显是个dp(记忆化搜索)了。 注意一下如果某一轮黑羽的数量是1,则A要获胜必须直接抽中白羽。特判一下就好。

    vector<vector<double>> st(1010,vector<double>(1010,-1));
    double solve(int w,int b){
        double &v = st[w][b];
        if(v >= 0) return v;
        double dw = (double )w;
        double db = (double )b;
    
        double win = dw/(dw+db);
        if(b==1){
            return v = win;
        }else{
            double nxt = db/(dw+db)*(db-1)/(dw+db-1);
            v = win + nxt *( dw/(dw+db-2)*solve(w-1,b-2) + (db-2)/(dw+db-2)*solve(w,b-3));
        }
        return v;
    }
    void solve(){
        int W,B;
        cin>>W>>B;
        for(int i=1;i<=W;i++) st[i][0] = 1.0;
        for(int i=0;i<=B;i++) st[0][i] = 0.0;
        cout<<fixed<<setprecision(10)<<solve(W,B)<<endl;
    }
    
    • 1

    信息

    ID
    218
    时间
    1000ms
    内存
    256MiB
    难度
    10
    标签
    递交数
    7
    已通过
    3
    上传者