HDOJ5724

好久没有更新博客了……最近集训的题都是规定不能上传到外网的，也情有可原嘛= =
刚才算是自己第一次独立ac了一道sg函数的题目。

题意是给你一个20*n的棋盘，对于每一行，你都可以选择一个棋子，把其往右移动一格，如果右边有棋子就继续往右移直到遇到空格为止。问你先手胜还是后手胜。

对于每一行其实都是单独考虑的一个sg状态，既然有20格，那就可以用sg[1 << 20]来存储所有的状态。然后推一推状态就好了……

#include <iostream> 
#include <cstdio>
#include <string>
#include <cstring>
#include <cmath>
#include <vector>
#include <algorithm>
using namespace std;
typedef  long long ll;
#define PB push_back
#define UB upper_bound
#define LB lower_bound
#define MP make_pair
#define pii pair<int,int>
#define vi vector<int>
#define vii vector<vi>
#define mst(x,y) memset(x,y,sizeof(x))
#define fr(x) freopen(x,"r",stdin)
#define fw(x) freopen(x,"w",stdout)
#define iin(x) scanf("%d",&x)
#define sp system("pause")
#define INF 1e9+250
#define MAXN 1000005
#define hash hhash
#define PI acos(-1.0)
#define eps 1e-4
#define left lgg
#define right rgg
#define vll vector<ll>

int sg[1 << 21];
int vis[25];

void sg_solve()
{
    for (int i = 1; i < (1 << 20); i++)
    {
         mst(vis, -1);
        int pos = -1;
        for (int j = 0; j < 20; j++)
        {
            if ((i >> j) & 1)
            {
                if (pos != -1)
                {
                    vis[sg[i - (1 << j) + (1 << pos)]] = 1;//需要注意的是用sg值来标记，而不是裸的位置值
                }
            }
            else
            {
                pos = j;
            }
        }
        int j = 0;
        for (; vis[j] != -1; j++);
        sg[i] = j;
    }
}

int main()
{
    sg_solve();
    int t;
    cin >> t;
    while (t--)
    {
        int n;
        iin(n);
        int s = 0,now = 0;
        for (int i = 0; i < n; i++)
        {
            int a; iin(a); s = 0;
            for (int j = 0; j < a; j++)
            {
                int b; iin(b);
                s ^= (1 << (20 - b));
            }
            now ^= sg[s];
        }

        if (now)
            cout << "YES\n";
        else
            cout << "NO\n";
    }
#ifndef ONLINE_JUDGE
    sp;
#endif
}