首页 > 代码库 > HDU 5724 Chess（博弈论）
HDU 5724 Chess（博弈论）
【题目链接】 http://acm.hdu.edu.cn/showproblem.php?pid=5724
【题目大意】
给出一个n行，每行有20格的棋盘，棋盘上有一些棋子，每次操作可以选择其中一个棋子，将其移至最左端的空位，两个人轮流操作，无法操作者输，判断游戏胜负。
【题解】
首先对于单行20格的游戏，这是一个NIM游戏，将20格的情况状态压缩，对于每种情况递归求其mex集合，计算其sg值，sg值为0的状态为必败态。
而对于可以拆分为多组NIM游戏的游戏，其sg值为拆分出的多组游戏的sg值的异或和。
预处理所有状态的sg值，对于每种读入的棋盘情况，直接求出解即可。
【代码】
#include <cstdio>#include <cstring>using namespace std; const int N=1<<20;int sg[N],T,n,m,x;int dfs(int x){ if(sg[x]!=-1)return sg[x]; int mex[50]={0},pos=-1; for(int i=0;i<20;i++){ if((x&(1<<i))==0)pos=i; else if(pos!=-1)mex[dfs(x^(1<<i)|(1<<pos))]=1; }for(int i=0;i<N;i++)if(!mex[i])return sg[x]=i;}void init(){ memset(sg,-1,sizeof(sg)); for(int i=0;i<=20;i++)sg[(1<<i)-1]=0; for(int i=1;i<N;i++)dfs(i);}int main(){ init(); scanf("%d",&T); while(T--){ int SG=0; scanf("%d",&n); for(int i=1;i<=n;i++){ scanf("%d",&m); int tmp=0; for(int j=1;j<=m;j++)scanf("%d",&x),tmp|=(1<<(20-x)); SG^=sg[tmp]; }if(SG)puts("YES"); else puts("NO"); }return 0;}
HDU 5724 Chess（博弈论）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。