首页 > 代码库 > POJ 1704-Georgia and Bob(阶梯博弈)

POJ 1704-Georgia and Bob(阶梯博弈)

题目链接:点击打开链接

题意:n个棋子分布在x正半轴上,现在两人轮流往左移动棋子,要求不能碰到其他棋子不能越界(不能移动到负半轴),最后不能移动者拜。

等价成阶梯博弈,比如 2  5  7  9 ,如果5向左移动到3(移动了2格),那么7可以移动的范围就增大了两格。

具体阶梯博弈的了解看这里:点击打开链接

注意:最右边的阶梯相当于编号为1,而非最左边的。(因为总是往左移动)还有,这题要排序。。。

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <string>
#include <cctype>
#include <vector>
#include <cstdio>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <set>
#define maxn 1002
#define _ll __int64
#define ll long long
#define INF 0x3f3f3f3f
#define Mod 10000007
#define pp pair<int,int>
#define ull unsigned long long
using namespace std;
int n,a[maxn];
void solve()
{
	a[0]=0;int tem=0;
	for(int i=1;i<=n;i++){
		scanf("%d",a+i);
	}
	sort(a,a+n+1);
	for(int i=n;i>=1;i-=2){
		int d=a[i]-a[i-1]-1;
		tem^=d;
	}
	if(tem)puts("Georgia will win");
	else puts("Bob will win");
}
int main()
{

	int T;scanf("%d",&T);
	while(T--){
		scanf("%d",&n);
		solve();
	}
	return 0;
}


 

POJ 1704-Georgia and Bob(阶梯博弈)