2022-12-02:有a块草莓蛋糕,有b块芝士蛋糕,两人轮流拿蛋糕,每次不管是谁只能选择在草莓蛋糕和芝士蛋糕中拿一种,拿的数量
2023-02-26 09:49:27 时间
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代码](https://github.com/algorithmzuo/weekly-problems/blob/main/src/class_2022_08_5_week/Code01_Cakes.java)
相关文章
- 2022皆为过往,2023平安健康
- Hackcity 参赛须知 Q&A
- 无限扩展的像素动画宇宙 #Floor796 是共创元宇宙的理想形态吗?
- 破防了,今年在牛客浏览了3000条帖子,焦虑已经溢出屏幕了
- 他连拉 shi 都不会,凭什么取代人类
- 首个元宇宙国家?!# Tuvalu
- 面试官亲述|如何优雅地介绍自己的项目经历?
- 138元每月,人生搜索引擎正式上线 # Rewind
- 吴恩达的2022年终AI大事件盘点
- 每天产生新想法的系统
- 游戏玩家如何沉浸式体验交互竞技场? #ArenaVerse
- 李玟“千禧之境”演唱会震撼来袭,VR 技术有新突破?
- 一键就可像素化的神器 # Pixelator
- Notion又出新功能?未来你想做的任何软件,都可以通过 Notion 来构建!# Notion AI
- 8.8k star,这可能是我见过最强的开源支付系统!!
- 没有广告的搜索引擎,能否超越Google?#You.com
- IntelliJ IDEA 2022.3 发布,这次不追了。。。
- Containerd深度剖析-CRI篇
- 不错的文章:《如何建立自己的思维方式?》
- 财务对账,怎么实现相同金额一正一负抵销,保留剩下的?| Power Query实战