2018年全国多校算法寒假训练营练习比赛（第三场）D 小牛vs小客 【简单博弈 + 图解】

题目描述

小牛和小客玩石子游戏，他们用n个石子围成一圈，小牛和小客分别从其中取石子，谁先取完谁胜，每次可以从一圈中取一个或者相邻两个，每次都是小牛先取，请输出胜利者的名字（小牛获胜输出XiaoNiu，小客获胜输出XiaoKe）（1 2 3 4 取走 2 13 不算相邻）

输入描述:

输入包括多组测试数据
每组测试数据一个n（1≤n≤1e9）

输出描述:

每组用一行输出胜利者的名字（小牛获胜输出XiaoNiu，小客获胜输出XiaoKe）

示例1

输入

2
3

输出

XiaoNiu
XiaoKe

题意： 注意是围成个圈

分析： 这个和我们以前见得 巴什博奕有点不同，这个要想去两个石子必须要相邻才可以，我们可以又少至多的分析：首先分析1或2个石子，不用说肯定是小牛获胜，当为3个时，见下图

当为4个点是见下图

就是说当小牛选1 时，小客选 3，最后还剩两个不连续的，每次只能拿一个，最后小牛输，所以4也是必败点，从而就可以推知当 n > 2时，对于小牛都是必败点

参考代码

#include<bits/stdc++.h>using namespace std;int main(){int n;cin>>n;if(n >= 3) cout<<"XiaoKe"<<endl;else cout<<"XiaoNiu"<<endl;return 0;
}

• 如有错误或遗漏，请私聊下UP，thx