【POJ1704】Georgia and Bob（博弈论）

2024-09-11 01:02:09

【POJ1704】Georgia and Bob（博弈论）

题面

题解

这种一列格子中移动棋子的问题一般可以看做成一个阶梯博弈。

将一个棋子向左移动时，它和前面棋子的距离变小，和后面棋子的距离变大，并且减小的值和增大的值是相等的，因此，这个过程我们就可以等价成一个阶梯博弈了。

#include<cstdio>

#include<iostream>

#include<algorithm>

using namespace std;

int a[1010];

int main()

{

	int T;cin>>T;

	while(T--)

	{

		int n,s=0;cin>>n;

		for(int i=1;i<=n;++i)cin>>a[i];

		sort(&a[1],&a[n+1]);

		for(int i=1;i<=n;i+=2)s^=a[n-i+1]-a[n-i]-1;

		puts(!s?"Bob will win":"Georgia will win");

	}

	return 0;

}

最新文章

热门文章