太原网站建设鸣蝉公司,国际域名注册流程,嘉兴秀洲区建设局网站,产品推广宣传方案链接#xff1a;登录—专业IT笔试面试备考平台_牛客网 来源#xff1a;牛客网 Alice 和 Bob 是一对竞技编程选手#xff0c;他们路过了一家气球店#xff0c;发现有 m 个大爱心气球和 n个小爱心气球。他们决定玩一个游戏#xff0c;游戏规则如下#xff1a;
Alice先手拿…链接登录—专业IT笔试面试备考平台_牛客网 来源牛客网 Alice 和 Bob 是一对竞技编程选手他们路过了一家气球店发现有 m 个大爱心气球和 n个小爱心气球。他们决定玩一个游戏游戏规则如下
Alice先手拿球两人轮流进行。每个人在自己的回合只能选择一种类型的气球。对于大爱心气球每次拿取可以选择取 5个、2个或 1个。对于小爱心气球每次拿取可以选择任意数量 不含0个。
游戏终止的条件是当所有的气球都被拿取完毕最后一个球被拿取的人即为获胜者。 假设两人都足够聪明并采取最优策略请问谁将获胜 分析
选5个的情况可以用212221代替结果相同所以只要考虑一二因为12都比3小并且123所以最后这堆剩下的为m%3个然后发现满足nim博弈的前提任意取至少一个至多全部最后取的赢所以直接用nim博弈的结论nim和为0那么后手赢而这里只有两堆则两堆相同后手赢否则先手赢。 #includebits/stdc.h
typedef long long ll;
using namespace std;
void solve()
{ll m,n;cinmn;//只考虑12(523),nim博弈if(m%3n)//nim和为0即m%3异或n等于0后手赢,即m%3n{coutBob\n;}else coutAlice\n;
}
int main()
{ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);ll t1;cint;while(t--)solve();return 0;
}
