[博弈论]巴什游戏
最编程
2024-05-03 21:40:35
...
「这是我参与11月更文挑战的第19天,活动详情查看:2021最后一次更文挑战」。
巴什博弈
简介
巴什博弈(Bash Game):一堆有个物品,如果有甲乙两个人。甲和乙轮流从这对物品中选取个物品,最后取光物品的人获胜,也就是没有取完物品的人输。
思路
若甲先手,设当前物品数为。
当时,甲可一次取完,获胜。
当时,甲无论取多少都会输。
当时,甲可以取个,使得无论如何乙取走后剩余个数不超过个,甲胜。
根据上述过程,不难发现要想自己赢必须尽可能保证对方拿到个。若甲获胜则需满足。
也就是说,如果乙后手获胜需要满足是的倍数。
算法模板
bool Bash(int n,int m){//这里返回的是先手玩家是否可以获胜
if(n%(m+1)) return true;
else return false;
}
例题
hdu1846
大概概括一下,就是有组样例,每组一个和表示含义见本文开头,输出第一个人先手时哪个人能获胜,输出获胜的人(first or second)。
#include <iostream>
using namespace std;
bool Bash(int n,int m){
if(n%(m+1)) return true;
else return false;
}
int main(){
int T,n,m;
cin>>T;
while(T--){
cin>>n>>m;
if(Bash(n,m)) cout<<"first\n";
else cout<<"second\n";
}
return 0;
}
推广
如果规定先取完的人输,那么需要重新考虑策略。
当时,则甲可以只留个给乙,甲胜。
当时,无论甲取多少,乙都能只留一个给甲,甲输。
当时,甲取个,乙从剩下的取必输。
当时,甲输。
总结规律可知时甲胜,否则乙胜。
算法模板
bool Bash(int n,int m){//这里返回的是先手玩家是否可以获胜
if((n-1)%(m+1)) return true;
else return flase;
}
上一篇: 用 C 语言解决遭遇问题
下一篇: 操作 - 服务器缓存 varnish