小程序做视频网站,网站备案幕布ps,做阿里巴巴网站,流程图制作Acwing 236. 格鲁吉亚和鲍勃
题意#xff1a;
一排网格#xff0c;将网格从左到右依次编号 1,2,3#xff0c;…#xff0c;并将 N 个西洋棋棋子放在不同的网格上#xff0c;如下图所示#xff1a; 两个人轮流移动棋子 每次玩家选择一个棋子#xff0c;并将其向左移动…Acwing 236. 格鲁吉亚和鲍勃
题意
一排网格将网格从左到右依次编号 1,2,3…并将 N 个西洋棋棋子放在不同的网格上如下图所示 两个人轮流移动棋子 每次玩家选择一个棋子并将其向左移动但是不能越过任何其他西洋棋棋子或超过左边界。
玩家可以自由选择棋子移动的步数其限制是棋子必须至少移动一步一个网格最多可以包含一个棋子。
无法移动任何棋子的玩家将输掉游戏。 1N1000 每个棋子的位置不超过10000
题解
看题目可知每个棋子的位置不超过10000 说明状态可以达到210000,那用sg函数记忆化搜索求无法实现这么大的范围说明题目会有更为精妙的解法 如图红色圈住的为棋子所在位置我们考虑6和9这两个位置的棋子如果先手移动6位置的棋子x步那么后手也可以移动9位置的棋子x步相当于后手可以复制前者的操作相当于大家都没操作。但是如果先手移动9后手就不一定可以复制先手的操作你可能会问为什么先手移动9后者为社么不一定能够11呢我们这里是将两个棋子为一组看待的6和9为一组如果先手移动9后手移动其他组的棋子(比如11)那先手还可以移动那个组剩下的棋子(比如12)这样消除了后手刚刚的操作因此比赛的关键取决于每组的间隙。如果是奇数个呢我们就让第一个棋子与左边界为一组剩下偶数个相邻两两一组。 这样问题就变成了 假设现在有m组每组都有空隙大小为a[i]每次操作可以减小任意一组的空隙大小(1~a[i]),两个人轮流操作如果有一方无法操作则游戏结束 现在这个游戏像什么不就是nim游戏吗再想想是不是所有我们直接将空隙大小异或就可以得到游戏结果 妙啊这个题的思路
代码
#includebits/stdc.h
#define debug(a,b) printf(%s %d\n,a,b);
typedef long long ll;
using namespace std;inline int read(){int s0,w1;char chgetchar();while(ch0||ch9){if(ch-)w-1;chgetchar();}while(ch0ch9) ss*10ch-0,chgetchar();//s(s3)(s1)(ch^48);return s*w;
}
int main()
{int t;cint;while(t--){int n;cinn;for(int i1;in;i)cina[i];if(n1)a[n]0;sort(a1,a1n);int s0;for(int i2;in;i2){s^(a[i]-a[i-1]-1);}if(s)coutGeorgia will winendl;else puts(Bob will win);} return 0;
}
