2022-12-02：有a块草莓蛋糕，有b块芝士蛋糕，两人轮流拿蛋糕， 每次不管是谁只能选择在草莓

2022-12-02：有a块草莓蛋糕，有b块芝士蛋糕，两人轮流拿蛋糕，
每次不管是谁只能选择在草莓蛋糕和芝士蛋糕中拿一种，
拿的数量在1~m之间随意，
谁先拿完最后的蛋糕谁赢。
返回先手赢还是后手赢。
nim博弈。

答案2022-12-02：

找规律法。
1.a==b
蛋糕一样多
先手必输，因为先手不管拿什么，拿多少
后手都在另一堆上，拿同样多的蛋糕
继续让两堆蛋糕一样多
最终先手必输，后手必赢
2.a!=b
如果 a != b
关注a和b的差值，
谁最先遇到差值为0，谁输
那么这就是巴什博奕
差值蛋糕数量共rest个。
每次从最少取1个，最多取m个，最后取光的人取胜。
如果rest=(m+1)*k + s (s!=0) 那么先手一定必胜
因为第一次取走s个，
接下来无论对手怎么取，
先手都能保证取到所有(m+1)倍数的点，
那么循环下去一定能取到差值最后一个。
时间复杂度：O(1)。
空间复杂度：O(1)。

代码用rust编写。代码如下：

use std::iter::repeat;

fn main() {
    let vv = 100;
    println!("测试开始");
    for a in 0..=vv {
        for b in 0..vv {
            for m in 0..vv {
                let ans1 = who_win1(a, b, m);
                let ans2 = who_win2(a, b, m);
                if ans1 != ans2 {
                    println!("出错了！");
                    println!("a : {}", a);
                    println!("b : {}", b);
                    println!("m : {}", m);
                    println!("ans1 : {}", ans1);
                    println!("ans2 : {}", ans2);
                }
            }
        }
    }
    println!("测试结束");
}

// 草莓蛋糕a块
// 巧克力蛋糕b块
// 每次可以在任意一种上拿1~m块
// 返回谁会赢，"先手" or "后手"
static mut dp: [[[&str; 101]; 101]; 101] = [[[""; 101]; 101]; 101];
fn get_max<T: Clone + Copy + std::cmp::PartialOrd>(a: T, b: T) -> T {
    if a > b {
        a
    } else {
        b
    }
}

fn get_min<T: Clone + Copy + std::cmp::PartialOrd>(a: T, b: T) -> T {
    if a < b {
        a
    } else {
        b
    }
}
// 暴力方法
// 为了验证
fn who_win1(a: i32, b: i32, m: i32) -> &'static str {
    if m >= get_max(a, b) {
        // nim博弈
        return if a != b { "先手" } else { "后手" };
    }
    if a == b {
        // 蛋糕一样多
        // 先手必输，因为先手不管拿什么，拿多少
        // 后手都在另一堆上，拿同样多的蛋糕
        // 继续让两堆蛋糕一样多
        // 最终先手必输，后手必赢
        return "后手";
    }
    if unsafe { dp[a as usize][b as usize][m as usize] } != "" {
        return unsafe { dp[a as usize][b as usize][m as usize] };
    }
    let mut ans = "后手";
    for pick in 1..=get_min(a, m) {
        if who_win1(a - pick, b, m) == "后手" {
            ans = "先手";
        }
        if ans == "先手" {
            break;
        }
    }
    for pick in 1..=get_min(b, m) {
        if who_win1(a, b - pick, m) == "后手" {
            ans = "先手";
        }
        if ans == "先手" {
            break;
        }
    }

    unsafe {
        dp[a as usize][b as usize][m as usize] = ans;
    }
    return ans;
}

// 正式解法
// 时间复杂度O(1)
// 先看nim博弈
fn who_win2(a: i32, b: i32, m: i32) -> &'static str {
    // if m >= get_max(a, b) {
    //     // nim博弈
    //     return if a != b { "先手" } else { "后手" };
    // }
    // m < max(a,b)
    if a == b {
        // 蛋糕一样多
        // 先手必输，因为先手不管拿什么，拿多少
        // 后手都在另一堆上，拿同样多的蛋糕
        // 继续让两堆蛋糕一样多
        // 最终先手必输，后手必赢
        return "后手";
    }
    // 如果 a != b
    // 关注a和b的差值，
    // 谁最先遇到差值为0，谁输
    // 那么这就是巴什博奕
    // 差值蛋糕数量共rest个。
    // 每次从最少取1个，最多取m个，最后取光的人取胜。
    // 如果rest=(m+1)*k + s (s!=0) 那么先手一定必胜
    // 因为第一次取走s个，
    // 接下来无论对手怎么取，
    // 先手都能保证取到所有(m+1)倍数的点，
    // 那么循环下去一定能取到差值最后一个。
    let rest = get_max(a, b) - get_min(a, b);
    return if rest % (m + 1) != 0 {
        "先手"
    } else {
        "后手"
    };
}

执行结果如下：

左神java代码

本作品采用《CC 协议》，转载必须注明作者和本文链接