欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

HDU 1730 Northcott Game 博弈论 尼姆博弈

程序员文章站 2022-06-09 17:40:27
...

原题链接:HDU 1730 Northcott Game

题目描述

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;
}