[poj1704]Georgia and Bob

Georgia and Bob poj-1704

题目大意：题目链接

注释：略。

想法：我们从最后一个球开始，每两个凑成一对。如果有奇数个球，那就让第一个球和开始位置作为一对。

那么如果对手移动的是一对球的后一个，我们就移动下一对球的前一个。

因为两个球挨着，所以对手动多少，我们动多少。

如果对手动的是一对球的前一个，我们考虑：

　　将对与对之间的格子当成一堆石子，那么对手移动一对球的前一个，就相当于在这堆石子中取走石子。

　　那么我们就对应的在另一堆中取石子。

这就相当于一个Nim游戏。如果对手不取石子（移动一对球的后一个），我们也不取石子，并且保证石子数不变（移动下一对球的前一个）。

如果对手取石子，我们就跟他取石子，玩Nim游戏。

通过游戏的和中的SG定理，而且Nim游戏中SG(x)=x。所以只需判断每对球之间的距离的异或和是否等于0即可。

最后，附上丑陋的代码... ...

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

#define N 200010

using namespace std;

int cases,a[N],b[N],n;

int main()

{

	scanf("%d",&cases);

	while(cases--)

	{

		scanf("%d",&n);

		for(int i=1;i<=n;i++) scanf("%d",&a[i]);

		sort(a+1,a+n+1); int ans=0;

		for(int i=n;i;i-=2)

		{

			int tmp;

			if(i==1) tmp=a[i]-1;

			else tmp=a[i]-a[i-1]-1;

			ans^=tmp;

		}

		if(ans) puts("Georgia will win");

		else puts("Bob will win");

	} return 0;

}

小结：三大经典博弈真心牛逼。

巴特西

[poj1704]Georgia and Bob_博弈论

最新文章

热门文章