6
POJ1704 Georgia and Bob（尼姆博弈）
source link: https://arminli.com/poj1704/
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
Armin's Blog
POJ1704 Georgia and Bob（尼姆博弈）
March 08, 2016
题意：x 轴（从 1 开始）上有 n 个点，每个人可以将某个点向左移动，不能超过或覆盖左边的点。不能移动的人就输了。给定点的位置输出胜者。
如果 n 是奇数，在 0 的位置填一个点构成偶数。把这些点按照顺序两两分成一组，每组间的距离可以看成尼姆博弈中的一堆石子的个数，移动后一个棋子相当于从石头堆中取出若干个石头，移动前一个棋子可以通过移动后一个棋子恢复到原来的状态，接下来就是个裸的尼姆博弈的题了。
#include<cstring>
#include<cstdio>
#include<cstring>
#include<cmath>
#include <vector>
#include<string>
#include<iostream>
#include<algorithm>
using namespace std;
int a[10002];
int main(){
//freopen("a.txt", "r", stdin);
int t, n;
cin >> t;
while(t--){
cin >> n;
for(int i = 0; i < n; i++)
cin >> a[i];
if(n&1) a[n++] = 0;
sort(a, a+n);
int ans = 0;
for(int i = 0; i < n-1; i+=2){
ans ^= (a[i+1]-a[i]-1);
}
if(ans) cout<<"Georgia will win"<<endl;
else cout << "Bob will win" << endl;
}
return 0;
}
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK