HDU 5724 Chess(博弈论)

发布时间:2017-2-20 9:49:43 编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"HDU 5724 Chess(博弈论) ",主要涉及到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;

上一篇:百度地图API--信息窗口
下一篇:使用KRPano资源分析工具一键下载全景网站切片图

相关文章

相关评论