【POJ】1704.Georgia and Bob

题解

感觉挺神奇的

我们把石子从后往前相邻的两个两两配对,这样他们之间的空格就相当于一堆石子

而配对后左边棋子移动,右边棋子也一定可以跟上取

转化成简单的nim游戏,最后只要看转化出的这(N - 1)/2 + 1堆石子异或起来等于0

代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
//#define ivorysi
#define MAXN 1005
#define eps 1e-8
using namespace std;
typedef long long int64;
typedef double db;
int N,T;
int a[MAXN];
void Solve() {
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 >= 1 ; i -= 2) {
ans ^= a[i] - a[i - 1] - 1;
}
if(!ans) puts("Bob will win");
else puts("Georgia will win");
}
int main() {
#ifdef ivorysi
freopen("f1.in","r",stdin);
#endif
scanf("%d",&T);
while(T--) {
Solve();
}
}
上一篇:aop


下一篇:浅谈数据结构-Boyer-Moore算法