当前位置：首页 > 牛客 > 【牛客14777题解法】动态规划+递归优化：详解比赛得分调整问题

【牛客14777题解法】动态规划+递归优化：详解比赛得分调整问题

9个月前 (07-04)

一、题目解读

牛客14777题要求判断在给定比赛场次n、当前得分k及两队得分差d1、d2的情况下，是否可以通过调整剩余比赛得分使最终比分满足特定条件。题目核心在于处理动态变化的得分组合，并验证其可行性，需结合数学推导与算法优化技巧。

二、解题思路

1. 边界条件处理：

当剩余比赛次数k为0时，需检查总得分n是否为3的倍数（题目约束）。

当n=k时，判断两队得分差是否均为0（比赛结束条件）。

2. 动态规划核心：

计算总得分上限total=n*3，剩余需分配得分remaining=n-k。

通过双重循环枚举4种比分组合（s1,s2∈{-1,1}），模拟两队得分变化。

3. 优化策略：

利用数学性质筛除非法组合（如总分余数不为3）。

计算调整后最高得分max_score，推导所需调整次数needed，结合剩余比赛次数验证可行性。

三、解题步骤

1. 输入与初始化：

读取测试用例数t，循环处理每个案例。

2. 核心函数check(n,k,d1,d2)：

执行边界条件判断（见上文）。

计算总分与剩余得分，枚举s1、s2组合。

推导调整后的得分(a,b,c)，验证非负性。

计算max_score与调整需求needed，检查剩余次数是否满足条件。

3. 输出结果：根据check返回值输出"yes"或"no"。

四、代码与注释

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

// 核心判断函数  
bool check(long long n, long long k, long long d1, long long d2) {  
    // 特殊情况处理：比赛已结束  
    if (k == 0) return (n % 3 == 0);  
    if (n == k) return (d1 == 0 && d2 == 0);  
    
    long long total = n * 3; // 总分上限  
    long long remaining = n - k; // 剩余比赛次数  
    // 枚举4种可能的比分组合  
    for (int s1 : {-1, 1}) {  
        for (int s2 : {-1, 1}) {  
            long long sum = 2 * s1 * d1 + s2 * d2; // 当前组合得分  
            if ((k - sum) % 3!= 0) continue; // 跳过非法组合（总分非3的倍数）  
            
            long long a = (k - sum) / 3; // 调整后得分A  
            long long b = a + s1 * d1; // 得分B  
            long long c = b + s2 * d2; // 得分C  
            // 检查非负性  
            if (a < 0 || b < 0 || c < 0) continue;  
            
            // 计算需要调整的分数（使三者相等）  
            long long max_score = max(a, max(b, c));  
            long long needed = (max_score - a) + (max_score - b) + (max_score - c);  
            // 检查剩余比赛是否足够且得分合法  
            if (needed <= remaining && (remaining - needed) % 3 == 0) {  
                return true;  
            }  
        }  
    }  
    return false;  
}  

int main() {  
    ios::sync_with_stdio(false);  
    cin.tie(nullptr); // 加速IO操作  
    int t;  
    cin >> t;  
    while (t--) {  
        long long n, k, d1, d2;  
        cin >> n >> k >> d1 >> d2;  
        cout << (check(n, k, d1, d2)? "yes" : "no") << endl;  
    }  
    return 0;  
}