hud 1846巴什博弈(简单的解法 或 Sprague-Grundy解法)

各位勇敢者要玩的第一个游戏是什么呢？很简单，它是这样定义的：
1、 本游戏是一个二人游戏;
2、 有一堆石子一共有n个；
3、 两人轮流进行;
4、 每走一步可以取走1…m个石子；
5、 最先取光石子的一方为胜；

如果游戏的双方使用的都是最优策略，请输出哪个人能赢。

Input
输入数据首先包含一个正整数C(C<=100)，表示有C组测试数据。
每组测试数据占一行，包含两个整数n和m（1<=n,m<=1000），n和m的含义见题目描述。

Output
如果先走的人能赢，请输出“first”，否则请输出“second”，每个实例的输出占一行。

Sample Input
2
23 2
4 3
思路：

1.当n <= m时，先手可以直接取完先手胜。

2.当n = m+1时，先手必败。

using namespace std;

int main()
{
    int T,n,m;
    cin>>T;
    while(T--){
        cin>>n>>m;  
        if(n %(m-1) == 0) printf("second\n");
        else  printf("first\n");
    }
}

用图游戏与Sprague-Grundy函数的解法：

图游戏的规律是规定一个有向无环图，在一个起点上放一枚棋子，两个玩家交替将这枚棋子沿有向边进行移动，无法移动者判负。

   x表示石子的数量，当石子为0是，先手是必败的状态（先手是指当前轮到去这个石子的人），让后先后递推。

#define _CRT_SECURE_NO_WARNINGS 1	
#include<iostream>
using namespace std;
const int MAX = 1001;
int n, m, sg[MAX], s[MAX];
void getSG() {
	memset(sg, 0, sizeof(sg));
	for (int i = 1; i <= n; i++) {
		memset(s, 0, sizeof(s));
		for (int j = 1; j <= m && i - j >= 0; j++) {
			s[sg[i - j]] = 1;
		}
		for (int j = 0; j <= n; j++) {
			if (!s[j]) {
				sg[i] = j;
				break;
			}
		}
	}
}
int main() {
	int c;
	cin >> c;
	while (c--) {
		cin >> n >> m;
		getSG();
		if (sg[n]) cout << "first" << endl;
		else cout << "second" << endl;
	}
	return 0;
}