题目:见这里
题意:n个位置有东西,然后现在每次要把这些东西向左移动,只能移动到最左边或者被其他东西挡住的位置,谁先无法移动就输,问最后谁赢
解法:不会。只好看网上的解题报告了,看了之后才发现真的妙啊。。。具体是这样转化的。很巧妙的转化为Nim游戏,首先相邻的两个作为1组,如果是奇数,就第一个和0作为1组,然后如果移动每组的前一个棋子,其实是没有影响的,因为后手可以跟他一样,把后面的棋子移动一样的步数,而移动后手,相当于把一个区间缩短,这样一个区间的长度就等同于Nim游戏中石子的数量,转化为了Nim游戏。。以我的智商好像也只能理解记住这种方法。。。要是碰到新的模型感觉好GG。。。悲伤中QAQ
//POJ 1704
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
const int maxn = 1005;
int n, a[maxn];
int main()
{
int T;
scanf("%d", &T);
while(T--){
scanf("%d", &n);
for(int i = 0; i < n; i++) scanf("%d", &a[i]);
sort(a, a + n);
int SG = 0;
if(n & 1) SG = a[0] - 1;
for(int i = n&1; i < n; i += 2){
SG ^= (a[i+1] - a[i] - 1);
}
if(SG == 0) puts("Bob will win");
else puts("Georgia will win");
}
return 0;
}