HDU 1730 Northcott Game 博弈论尼姆博弈

妖狐艹你老母 2022-12-02 10:54 158阅读 0赞

[原题链接：HDU 1730 Northcott Game][HDU 1730 Northcott Game]

#### 题目描述 ####

![hdu1730][]  
![1730][]

--------------------

#### 思路 ####

我们先从**最终态**也就是**必败态**看，最终所有黑白两棋之间的**距离为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;
    }

[HDU 1730 Northcott Game]: http://acm.hdu.edu.cn/showproblem.php?pid=1730
[hdu1730]: /images/20221123/e42bf9b2aab04e11982beb2287ad33ba.png
[1730]: /images/20221123/57ffad794d10470190bd3dd52a166f86.png