[poj1704]Georgia and Bob_博弈论
Georgia and Bob poj-1704
题目大意：题目链接
注释：略。
想法：我们从最后一个球开始，每两个凑成一对。如果有奇数个球，那就让第一个球和开始位置作为一对。
那么如果对手移动的是一对球的后一个，我们就移动下一对球的前一个。
因为两个球挨着，所以对手动多少，我们动多少。
如果对手动的是一对球的前一个，我们考虑：
将对与对之间的格子当成一堆石子，那么对手移动一对球的前一个，就相当于在这堆石子中取走石子。
那么我们就对应的在另一堆中取石子。
这就相当于一个Nim游戏。如果对手不取石子（移动一对球的后一个），我们也不取石子，并且保证石子数不变（移动下一对球的前一个）。
如果对手取石子，我们就跟他取石子，玩Nim游戏。
通过游戏的和中的SG定理，而且Nim游戏中SG(x)=x。所以只需判断每对球之间的距离的异或和是否等于0即可。
最后，附上丑陋的代码... ...
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define N 200010
using namespace std;
int cases,a[N],b[N],n;
int main()
{
scanf("%d",&cases);
while(cases--)
{
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;i-=2)
{
int tmp;
if(i==1) tmp=a[i]-1;
else tmp=a[i]-a[i-1]-1;
ans^=tmp;
}
if(ans) puts("Georgia will win");
else puts("Bob will win");
} return 0;
}
小结：三大经典博弈真心牛逼。
查看6道真题和解析
美的集团公司福利 818人发布