题解

要计算队伍A赢得排球比赛的概率，需分局内胜负和多局博弈两步，结合记忆化搜索和动态规划求解：

1. 局内胜负概率（单局A赢的概率）

• 状态定义：用 (a, b, serving) 表示当前局A得a分、B得b分、发球方为serving（0=A发球，1=B发球）。
• 记忆化搜索：通过递归 dfs 计算每个状态下A赢局的概率，利用哈希表 memo 缓存结果，避免重复计算。
• 发球与得分转移：
  • 若A发球，赢轮则A得分+1、继续发球；输轮则B得分+1、B发球（反之同理）。
  • 首局第一球，A和B发球概率各50%，因此单局赢概率为两种发球情况的平均值。

2. 多局博弈概率（A赢K局的概率）

• 状态定义：dp[i][j] 表示A赢i局、B赢j局时，A最终赢比赛的概率。
• 边界与递推：
  • 若A已赢K局（i=K），概率为1；若B已赢K局（j=K），概率为0。
  • 递推公式：dp[i][j] = probAWinGame * dp[i+1][j] + (1-probAWinGame) * dp[i][j+1]（probAWinGame为单局A赢的概率）。

3. 结果计算

整合单局和多局的概率计算，将最终结果转换为百分比，保留1位小数输出。

该方法通过记忆化搜索处理局内复杂规则，动态规划处理多局胜负递推，高效求解概率问题。

#include <iostream>
#include <iomanip>
#include <map>       // 替换为map头文件
#include <vector>

using namespace std;

struct State {
    int a, b, serving;
    State(int a_, int b_, int s_) : a(a_), b(b_), serving(s_) {}
    bool operator==(const State& other) const {
        return a == other.a && b == other.b && serving == other.serving;
    }
    // 为map添加小于运算符（用于排序）
    bool operator<(const State& other) const {
        if (a != other.a) return a < other.a;
        if (b != other.b) return b < other.b;
        return serving < other.serving;
    }
};

// 使用map替代unordered_map（无需哈希函数）
map<State, double> memo;

double dfs(int a, int b, int serving, int Pa, int Pb, int L) {
    if (a == L && b < L) return 1.0;
    if (b == L && a < L) return 0.0;
    State s(a, b, serving);
    if (memo.count(s)) return memo[s];
    double prob = 0.0;
    if (serving == 0) {
        double p_win = Pa / 100.0;
        prob += p_win * dfs(a + 1, b, 0, Pa, Pb, L);
        prob += (1 - p_win) * dfs(a, b + 1, 1, Pa, Pb, L);
    } else {
        double p_win = Pb / 100.0;
        prob += p_win * dfs(a, b + 1, 1, Pa, Pb, L);
        prob += (1 - p_win) * dfs(a + 1, b, 0, Pa, Pb, L);
    }
    return memo[s] = prob;
}

double gameWinProbability(int Pa, int Pb, int L) {
    memo.clear();
    double probA = dfs(0, 0, 0, Pa, Pb, L);
    double probB = dfs(0, 0, 1, Pa, Pb, L);
    return 0.5 * probA + 0.5 * probB;
}

double calculateFirstToK(double probAWinGame, int K) {
    // 修改嵌套模板中的>>为> >（旧编译器要求）
    vector<vector<double> > dp(K + 1, vector<double>(K + 1, 0.0));
    for (int j = 0; j < K; ++j) dp[K][j] = 1.0;
    for (int i = 0; i < K; ++i) dp[i][K] = 0.0;
    for (int i = K - 1; i >= 0; --i) {
        for (int j = K - 1; j >= 0; --j) {
            dp[i][j] = probAWinGame * dp[i + 1][j] + (1 - probAWinGame) * dp[i][j + 1];
        }
    }
    return dp[0][0];
}

double calculateProbability(int Pa, int Pb, int K, int L) {
    if (K == 0) return 0.0;
    double probGame = gameWinProbability(Pa, Pb, L);
    return calculateFirstToK(probGame, K) * 100;
}

int main() {
    int numTests;
    cin >> numTests;
    cout << fixed << setprecision(1);
    while (numTests--) {
        int Pa, Pb, K, L;
        cin >> Pa >> Pb >> K >> L;
        double res = calculateProbability(Pa, Pb, K, L);
        cout << res << endl;
    }
    return 0;
}