hdu 5724 Chess 博弈

一个n行20列的棋盘。每一行有若干个棋子。两人轮流操作，每人每次可以将一个棋子向右移动一个位置，如果它右边有一个棋子，就跳过这个棋子，如果有若干个棋子，就将这若干个都跳过。但是棋子不能移出边界。

如果没有办法移动了，就算输。问你先走的能否赢。

只有20列，所以预处理出所有状态的sg值。然后直接异或就好了。

然后sg[(1<<20)-1] = 0, 这是必输态，其他的都可以dfs出来，具体看代码。

#include <bits/stdc++.h>

using namespace std;

#define pb(x) push_back(x)

#define ll long long

#define mk(x, y) make_pair(x, y)

#define lson l, m, rt<<1

#define mem(a) memset(a, 0, sizeof(a))

#define rson m+1, r, rt<<11

#define mem1(a) memset(a, -1, sizeof(a))

#define mem2(a) memset(a, 0x3f, sizeof(a))

#define rep(i, n, a) for(int i = a; i<n; i++)

#define fi first

#define se second

typedef pair<int, int> pll;

const double PI = acos(-1.0);

const double eps = 1e-;

const int mod = 1e9+;

const int inf = ;

const int dir[][] = { {-, }, {, }, {, -}, {, } };

int sg[<<];

int mex(int x)

{

    if(~sg[x])

        return x;

    bool vis[];

    memset(vis, false, sizeof(vis));

    for(int i = ; i < ; i++) {

        if(((<<i)&x)== && ((<<(i+))&x)) {

            int j;

            for(j = i + ; j < ; j++) {

                if(!(<<j&x))

                    break;

            }

            for(int k = i+; k <= j; k++) {

                int sta = x^(<<i)^(<<k);

                if(sta>=(<<))

                    break;

                mex(sta);

                vis[sg[sta]] = ;

            }

        }

    }

    for(int i = ; i < ; i++)

        if(!vis[i])

            return sg[x] = i;

}

void init()

{

    mem1(sg);

    sg[(<<)-] = ;

    for(int i = ; i < (<<); i++) {

        if(sg[i] == -) {

            mex(i);

        }

    }

}

int main()

{

    init();

    int t, n, m, x;

    cin>>t;

    while(t--) {

        cin>>n;

        int ans = ;

        for(int i = ; i < n; i++) {

            scanf("%d", &m);

            int sta = ;

            while(m--) {

                scanf("%d", &x);

                sta |= (<<(-x));

            }

            ans ^= sg[sta];

        }

        if(ans) {

            puts("YES");

        } else {

            puts("NO");

        }

    }

}

巴特西

hdu 5724 Chess 博弈

最新文章

热门文章