博弈论--巴什博弈——HDU1846

本文主要是介绍博弈论--巴什博弈——HDU1846，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

/*巴什博弈：HDU--1846*/
# include<iostream>
using namespace std;
int main()
{
    int t;
    int n,m;
    cin>>t;
    while(t--)
    {
      cin>>n>>m;
      if(n%(m+1)==0) cout<<"second"<<endl;/*此处的n%(m+1)的意思是如果取余的结果不是0，就是先者为胜，否则就是后者为胜*/
      else cout<<"first"<<endl;
    }
    return 0;
}
/*巴什博弈算法总结：
问题描述基本模型：
只有一堆n 个物品，两个人轮流从这堆物品中取物，规定每次至少取一个，最多取m 个。最后取光者得胜。


给你n，如何判断先手还是后手赢？？？
算法过程分析：
特殊的2种情况：
1 当n<m时，很显然是先手赢
2 当n=m+1时，不论先手取多少个（但必须是小于或等于m的），总是不能一次取完，所以只能是后手赢
如果总的物品数有 n=(m+1)*r+s个(其中：s<=m,r为自然数)，先手先取s个，后手取k个（k<=m）,先手只要再取（m+1-k）个
最终剩下的是（m+1）*(r-1)个也即是（m+1）的整数倍，这样无论后手怎么取，都不会把剩下的一次性取完，最终只会是先手获胜
总之就是：让最后剩下物品数是（m+1）的倍数即可
*/

这篇关于博弈论--巴什博弈——HDU1846的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---