难度：提高+/省选-

题目描述

        AKN玩游戏玩累了，于是他开始和同伴下棋了，玩的是跳棋！对手是wwx！这两位上古神遇在一起下棋，使得棋局变得玄幻莫测，高手过招，必有一赢，他们都将用最佳策略下棋，现在给你一个n*20的棋盘，以及棋盘上有若干个棋子，问谁赢？akn先手！
        游戏规则是这样的：
        对于一个棋子，能将它向右移动一格，如果右边有棋子，则向右跳到第一个空格，如果右边没有空格，则不能移动这个棋子，如果所有棋子都不能移动，那么将输掉这场比赛。

输入输出格式

输入格式：

        第一行一个T，表示T组数据
        每组数据第一行n，表示n*20的棋盘
        接下来n行每行第一个数m表示第i行有m个棋子
        随后跟着m个数pj表示第i行的棋子布局

输出格式：

        如果AKN能赢，则输出”YES”，否则输出”NO”。

输入输出样例

Sample input

2
1
2 19 20
2
1 19
1 18

Sample output

NO
YES

说明

        10%的数据T≤1，n≤1
        另外10%的数据m≤1
        100%的数据T≤100，n≤1000，m≤20，1≤pj≤20

题解

        比较裸的状态压缩类博弈论。注意到跳棋只能在一行内操作，不能跨行，于是就可以将每一行都看成是一个子游戏，整个游戏即为原游戏和。用二进制数表示每一行20个格子的有无状态，递推出SG值，最后根据SG定理求Nim和判断即可。SG函数值可以暴力求出。
        本题可以比较好地练习SG函数求法和SG定理应用，故加入博客。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include<iostream>
#include<cstring>

using namespace std;
int SG[1 << 20];
bool vis[20] = {false};

inline int solve(int x, int y) {
    for (int i = y - 1; i >= 0; i--)if ((x & (1 << i)) == 0)return i;
    return -1;
}

int main() {
    SG[0] = 0;
    for (int i = 1; i < (1 << 20); i++) {//暴力求SG函数值
        memset(vis, false, sizeof(vis));
        for (int j = 0; (1 << j) <= i; j++) {
            if ((i & (1 << j)) > 0) {
                int p = solve(i, j);
                if (p != -1) {
                    vis[SG[((~(1 << j)) & i) | (1 << p)]] = true;//这是一个玄学的式子，用于mex运算
                }
            }
        }
        for (int j = 0; j < 20; j++)
            if (!vis[j]) {
                SG[i] = j;
                break;
            }
    }
    int T;
    cin >> T;
    for (int ti = 0; ti < T; ti++) {
        int n, ans = 0;
        cin >> n;
        for (int i = 1; i <= n; i++) {
            int k, p = 0;
            cin >> k;
            for (int j = 0; j < k; j++) {
                int x;
                cin >> x;
                p |= (1 << (20 - x));
            }
            ans ^= SG[p];//求Nim和
        }
        if (ans == 0)cout << "NO" << endl;//根据SG函数值判断结果
        else cout << "YES" << endl;
    }
    return 0;
}

        其实这个方法很粗暴，并不优，但可以在SG函数求取时优化。
        下面介绍一种洛谷大佬想出的方法：用阶梯Nim方法解决本问题。要理解该做法，需要先了解什么是阶梯Nim，可以参考这篇博客。
        将两个空位之间的部分看做阶梯，其中的棋子数目就是阶梯上的石子数目，那么本问题就相当于做阶梯Nim游戏。比如若仅有18、19处有棋子，那么阶梯就是：第一阶梯2个棋子，之后的阶梯没有棋子，共17个阶梯；又比如仅有18、19、20处有棋子，则阶梯相当于所有阶梯都没有石子，共16个阶梯。
        为什么可以将这个跳棋问题看作阶梯Nim游戏呢？这是由游戏的操作性质决定的。考虑仅有16、17、18处有棋子，那么该局面的二进制表示为011100（只写后几位），对应阶梯为0、3、0（按阶梯编号升序，只写前几位）。这个局面可以转移到001110、010110、011010三个状态，对应的阶梯分别为：（3，0，0）、（2，1，0）、（1，2，0），正好对应了初始阶梯Nim局面的三种移动石子的方式，可见本游戏的棋子移动规则就是阶梯Nim游戏的变形。
        于是可以用阶梯Nim的方法去求SG值，该方法效率很高，时间复杂度O(20Tn)。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include<iostream>
#include<cstring>

using namespace std;
bool vis[21];
int temp[20] = {0};

int main() {
    int T;
    cin >> T;
    for (int ti = 0; ti < T; ti++) {
        int n, ans = 0, ans0 = 0;
        cin >> n;
        for (int i = 0; i < n; i++) {
            int k, last = -1;
            ans0 = 0;
            cin >> k;
            memset(vis, false, sizeof(vis));
            temp[0] = 0;
            for (int j = 0; j < k; j++) {
                int x;
                cin >> x;
                vis[x] = true;
            }
            for (int j = 20; j > 0; j--) {
                if (!vis[j]) {
                    if (last != -1)temp[++temp[0]] = last - j - 1;
                    last = j;
                }
            }
            if (last != 1)temp[++temp[0]] = last - 1;
            for (int j = 1; j <= temp[0]; j += 2)ans0 ^= temp[j];
            ans ^= ans0;
        }
        if (ans == 0)cout << "NO" << endl;
        else cout << "YES" << endl;
    }
}