网站开发工程师 北大青鸟,小程序定制开发外包风险,做网站价格多少,如何给别人做网站挣钱Georgia and Bob
思路
每个棋子只能向左移动并且不能越过其左边的棋子#xff0c;这就有点像是经典的nim博弈了#xff0c;
但是在这里后一个石子会受到其前一个石子位置的影响#xff0c;这里就需要转化一下了。
我们假设只有两个棋子#xff0c;x,y,x0,yxx, …Georgia and Bob
思路
每个棋子只能向左移动并且不能越过其左边的棋子这就有点像是经典的nim博弈了
但是在这里后一个石子会受到其前一个石子位置的影响这里就需要转化一下了。
我们假设只有两个棋子x,y,x0,yxx, y , x 0, y xx,y,x0,yx显然先手可以第一步移动后面的棋子到与第一颗棋子临近的地方
然后无论后手如何移动棋子一先手只要走与后手移动的步数相同也就是保证了两者一定相邻
这个时候假设一个结论当所有间隔异或起来为0的时候先手必输后手必胜
我们再看一个例子1,3,51, 3, 51,3,5间隔异或为000所以先手输了但是事实并不是啊
先手可以操纵5走到4然后无论后手如何操作先手都按照他的操作copy走。
所以我么先前的假设有问题但是似乎我们能大概得到最后操作最后面的棋子是总能是最优的
但是最后面的棋子会受其前面的棋子的影响因此我们从右向左给棋子两两分组显然如果移动左侧的棋子我们可以移动右侧的棋子
使状态保持不变移动左侧的棋子就是他们中间的空位一直减小当没一对棋子的空隙都为零时显然胜负状态就已经决定了
所以这里就成功转换为了一个nim博弈。
写min_25写废了水一水简单博弈
代码
/*Author : lifehappy
*/
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#include iostream
#include cstdio
#include cstring
#include algorithm
#include cmath
#include cstring
#include vector
#include stdlib.h
#include mapusing namespace std;typedef long long ll;const int inf 0x3f3f3f3f;
const double eps 1e-6;const int N 1e4 10;int a[N], n;int main() {// freopen(in.txt, r, stdin);// freopen(out.txt, w, stdout);// ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);int T;scanf(%d, T);while(T--) {scanf(%d, n);for(int i 1; i n; i) {scanf(%d, a[i]);}sort(a 1, a 1 n);int ans 0;for(int i n; i 0; i - 2) {ans ^ (a[i] - a[i - 1] - 1);}if(ans) puts(Georgia will win);else puts(Bob will win);}return 0;
}
