首页 > 代码库 > 【POJ3537】Crosses and Crosses 博弈,SG函数,Multi-SG博弈
【POJ3537】Crosses and Crosses 博弈,SG函数,Multi-SG博弈
转载请注明出处:http://blog.csdn.net/vmurder/article/details/42654067
其实我就是觉得原创的访问量比未授权盗版多有点不爽233。。。
题意:有个一维棋盘,两人轮流下棋,然后谁连成三个谁赢。
题解:
我们考虑到一个长度为n的棋盘,在i处下子,相当于把游戏转化成两个游戏GAME(x-i-2)和GAME(i-3)。
原因:左边一部分将不再能下子,右边一部分将不再能下子(准确地说是两个)。
然后就成了当前状态俩子状态,然后就是裸SG转移了。
Multi-SG博弈就是指一个游戏可以转化成俩子游戏。
代码:
#include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #define N 2015 using namespace std; int sg[N]; int SG(int x) { if(x<0)return 0; if(sg[x]+1)return sg[x]; bool vis[N]={0}; int i; for(i=1;i<=x;i++)vis[SG(x-i-2)^SG(i-3)]=true; for(i=0;vis[i];i++); return sg[x]=i; } int main() { // freopen("test.in","r",stdin); memset(sg,-1,sizeof sg); sg[0]=0,sg[1]=sg[2]=sg[3]=1; for(int x;scanf("%d",&x)!=EOF;) printf("%d\n",SG(x)?1:2); return 0; }
【POJ3537】Crosses and Crosses 博弈,SG函数,Multi-SG博弈
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。