HDU 1730 Northcott Game 博弈论 尼姆博弈

原题链接：HDU 1730 Northcott Game

题目描述

---

思路

我们先从最终态也就是必败态看，最终所有黑白两棋之间的距离为0，也就是说，每个黑白棋之间的距离异或起来是0，这就是必败态。
为什么呢，我们来推一下，当前一个人走完，后一个人一定可以走到使得所有距离异或起来为0的某个位置，而另一个人只能面对这个状态走棋而不能再创造这个状态，如此反复，直到最后一轮，其面对的状态仍是必败态，也就是最终态，所有黑白棋距离为0，则其必输。注： 博弈时，每个人都会走当前最优策略，所以每个人都会尽量给对方创造必败态，给自己创造必胜态。
那么我们就看最初时刻，每行的黑白棋距离异或起来是否为0，若为0，先手必输，因为这就已经是必败态了；若不为0，则先手必赢，因为先手可以首先创造一个必败态给后手。
这就是四大博弈之一的尼姆博弈。

---

代码解析

#include<iostream>
#include<algorithm>
using namespace std;

int main()
{
	int n,m,a,b,s;
	while(cin >> n >> m)
	{
		s = 0;
		for(int i = 0;i < n;i++)
		{
			cin >> a >> b;
			int d = max(a,b) - min(a,b) - 1;
			s ^= d;
		}
		if(s)
			cout << "I WIN!" << endl;
		else
			cout << "BAD LUCK!" << endl;
	}

	return 0;
}