Luogu2575高手过招|题解

AKN玩游戏玩累了，于是他开始和同伴下棋了，玩的是跳棋！对手是wwx！这两位上古神遇在一起下棋，使得棋局变得玄幻莫测，高手过招，必有一赢，他们都将用最佳策略下棋，现在给你一个n*20的棋盘，以及棋盘上有若干个棋子，问谁赢？akn先手！

游戏规则是这样的：

对于一个棋子，能将它向右移动一格，如果右边有棋子，则向右跳到第一个空格，如果右边没有空格，则不能移动这个棋子，如果所有棋子都不能移动，那么将输掉这场比赛。

显然每行游戏状态相互独立,可以分解为子问题.

每个子问题规模$20$,考虑压缩状态.

问题在于如何求得子问题的$SG$函数

阶梯Nim

一个阶梯有n阶，每一阶上面都可以存放个数不限的硬币。现在我们用n元组(x1,x2,…,xn) 来代表第 i (1 ≤ i ≤
n)个硬币存放在第xi个阶梯上面。阶梯博弈中的一次移动可以把任意正整数个的硬币从某一阶移动到下面的一阶，也即是从第 j 阶移动到第j -
1阶。当硬币到达地面（第0阶）时，这个硬币就不可再移动了。双方轮流落子，直到有一方不能再落子。

在阶梯Nim中我们遵循以下策略:

• 若对手将奇数阶的硬币移到偶数阶,我们不作为
• 若对手将偶数阶的硬币移到奇数阶,我们将相同的这些硬币移至下一级偶数阶

由于所有硬币最后都会到达第$0$阶,所以根据以上策略,移至偶数阶的硬币相当于被拿走了

也就是问题变为对奇数阶的Nim游戏

---

而这个问题可以归结为阶梯Nim:将两个空位之间的间隙视为一级阶梯即可

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <string>
#include <algorithm>
#include <set>
#define LL long long
using namespace std;
LL T,n,sg_mem[2000000];
const LL N = 20;
LL sg(LL status){
        LL ans = 0,cnt = 0,j = 0;
        while(status){
                if (status & 1){
                        ++ cnt;
                        status >>= 1;
                        continue;
                }
                if (j % 2)
                        ans ^= cnt;
                cnt = 0;
                ++ j;
                status >>= 1;
        }
        if (j % 2)
                ans ^= cnt;
        return ans;
}
int main (){
        LL al,n,m;
        memset(sg_mem,-1,sizeof(sg_mem));
        cin >> T;
        while(T--){
                scanf("%lld",&n);
                LL ans = 0;
                for (LL i = 1;i <= n;++ i){
                        LL s = 0;
                        scanf("%lld",&m);
                        for (LL i = 1;i <= m;++ i){
                                scanf("%lld",&al);
                                s |= (1 << (20 - al));
                        }
                        ans ^= sg(s);
                }
                if (ans)
                        printf("YES\n");
                else
                        printf("NO\n");
        }
        return 0;
}

文结.