板球比赛必胜路径计数问题 代码错误排查求助

问题描述 #

Pranay和Sumith正在进行板球比赛，Sumith的队伍得分X，Pranay的队伍得分Y。比赛剩余6个球，Pranay队已丢失9个wicket。当前Mahesh在strike端，Pranay在非strike端。Pranay不擅长击球，一旦轮到他击球就会出局；Mahesh是优秀击球手，不会出局。
注意：投球手不会投出wides或no-balls这类额外球，每球均为常规投球，每球通过跑位最多得3分。
需求：计算Pranay队100%获胜的路径数量。

输入格式 #

每组测试包含多组用例，第一行是整数t（测试用例数），每组用例一行输入两个整数X和Y，分别代表Sumith队和Pranay队的得分。

约束条件 #

• 1 ≤ t ≤ 10^7
• 1 ≤ Y < X ≤ 500

用户代码 #

#include <iostream>
#include <vector>
using namespace std;

vector<int> runs = {0, 2, 4, 6};
int helper(vector<vector<int>> &dp, int &target, int curr, int ball){
    if (curr >= target) return 1;
    if (ball > 6) return 0; 
    if (dp[ball][curr] != -1) return dp[ball][curr];
    int ans = 0;
    for (int j = 0; j < 4; j++) ans += helper(dp, target, curr + runs[j], ball + 1);
    return dp[ball][curr] = ans;
}

int main() {
    int t;
    cin >> t;
    while(t--){
        int x, y;
        cin >> x >> y;
        int target = x - y + 1; // You need 1 more than the required difference of X and Y
        vector<vector<int>> dp(7, vector<int>(target + 1, -1));
        cout << helper(dp, target, 0, 1) << endl;
    }
    return 0;
}

用户逻辑 #

采用top-down记忆化递归方法求解，每次递归对应一个球，将runs数组中的得分加到当前得分curr上。基准条件：

• 若curr≥target则返回1
• 若ball>6则返回0
  可选得分设为{0,2,4,6}，因为选1或3会让Pranay换到strike端，无法保证100%获胜；5分不可能（每球最多跑3分）。

测试情况 #

部分测试用例输入输出正确，但隐藏测试用例全部错误，请求排查代码漏洞。

核心漏洞排查 #

1. 提前获胜后的路径计数错误 #

当curr >= target时直接返回1是完全错误的。即使在第k个球（k<6）就达标，剩下的6-k个球仍需选择合法得分（0、2、4、6），否则中途交换strike会导致Pranay出局，这条路径就无效。正确的做法是：一旦达标，剩余每个球都有4种合法选择，所以应返回4^(剩余球数)，而非1。

比如：第2个球达标后，剩下4个球的合法路径数是4^4=256，你的代码只算1条，导致结果严重偏小。

2. 无法处理超大量测试用例 #

t的上限是1e7，当前代码每个测试用例都重新创建dp数组并递归计算，时间复杂度直接爆炸，绝对无法通过隐藏测试。必须提前预处理所有可能的target（最大为500）和剩余球数的组合结果，测试用例直接查表输出。

3. IO效率不足 #

1e7次输入输出用默认的cin/cout会超时，必须关闭同步加速：

ios_base::sync_with_stdio(false);
cin.tie(NULL);

修正方案 #

预处理动态规划实现 #

提前计算所有可能场景的结果，测试用例直接查表：

#include <iostream>
using namespace std;

const int MAX_TARGET = 500;
const int MAX_BALLS = 6;
long long dp[MAX_BALLS + 1][MAX_TARGET + 1];
long long pow4[MAX_BALLS + 1];

void precompute() {
    // 预计算4的幂次，存储剩余n个球的合法路径数
    pow4[0] = 1;
    for (int i = 1; i <= MAX_BALLS; i++) {
        pow4[i] = pow4[i-1] * 4;
    }

    // 初始化dp：dp[b][s]代表剩余b个球，需要至少得s分的有效路径数
    for (int s = 0; s <= MAX_TARGET; s++) {
        dp[0][s] = 0; // 0个球无法得分
    }

    for (int b = 1; b <= MAX_BALLS; b++) {
        dp[b][0] = pow4[b]; // 不需要得分，所有路径都合法
        for (int s = 1; s <= MAX_TARGET; s++) {
            long long res = 0;
            int runs[] = {0, 2, 4, 6};
            for (int r : runs) {
                if (r >= s) {
                    // 当前球得分达标，剩余b-1个球随便选合法得分
                    res += pow4[b-1];
                } else {
                    // 未达标，累加剩余b-1个球需得s-r分的路径数
                    res += dp[b-1][s - r];
                }
            }
            dp[b][s] = res;
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    precompute();

    int t;
    cin >> t;
    while(t--) {
        int x, y;
        cin >> x >> y;
        int target = x - y + 1;
        if (target <= 0) {
            cout << pow4[6] << '\n';
            continue;
        }
        cout << dp[6][target] << '\n';
    }
    return 0;
}

修正逻辑说明 #

1. 预处理阶段：提前计算所有剩余球数（1-6）和所需得分（1-500）的有效路径数，存储在dp数组中。
2. 幂次预计算：pow4[n]存储n个球的合法选择数（每个球4种合法得分）。
3. 状态转移：对于每个剩余球数和所需得分，遍历所有合法得分，要么当前球达标后累加剩余球的路径数，要么累加未达标时的后续路径数。
4. IO优化：关闭同步后，输入输出速度能适配1e7量级的测试用例。

内容的提问来源于stack exchange，提问作者Ultimate