【luogu P2148】 ED(SG函数)

参考另一位dalao的文章，无恶意

学习博弈论也可返回另一篇笔记

题目描述

小 E 与小 W 进行一项名为 E&D 游戏。

游戏的规则如下：桌子上有 $2n$ 堆石子，编号为 $1\sim 2n$。其中，为了方便起见，我们将第 $2k-1$ 堆与第 $2k$ 堆（$1\le k\le n$）视为同一组。第 $i$ 堆的石子个数用一个正整数 $S_i$ 表示。

一次分割操作指的是，从桌子上任取一堆石子，将其移走。然后分割它同一组的另一堆石子，从中取出若干个石子放在被移走的位置，组成新的一堆。操作完成后，所有堆的石子数必须保证大于 $0$。显然，被分割的一堆的石子数至少要为 $2$。两个人轮流进行分割操作。如果轮到某人进行操作时，所有堆的石子数均为 $1$，则此时没有石子可以操作，判此人输掉比赛。

小 E 进行第一次分割。他想知道，是否存在某种策略使得他一定能战胜小 W。因此，他求助于小 F，也就是你，请你告诉他是否存在必胜策略。例如，假设初始时桌子上有 $4$ 堆石子，数量分别为 $1,2,3,1$。小 E 可以选择移走第 $1$ 堆，然后将第 $2$ 堆分割（只能分出 $1$ 个石子）。接下来，小 W 只能选择移走第 $4$ 堆，然后将第 $3$ 堆分割为 $1$ 和 $2$。最后轮到小 E，他只能移走后两堆中数量为 $1$ 的一堆，将另一堆分割为 $1$ 和 $1$。这样，轮到小 W 时，所有堆的数量均为 $1$，则他输掉了比赛。故小 E 存在必胜策略。

输入格式

本题有多组数据。

第一行一个整数 $T$，表示数据组数。

对于每组数据：

第一行一个整数 $N$，表示桌子上共有 $N$ 堆石子，这里的 $N$ 即为题目描述中的 $2n$。

第二行 $N$ 个整数 $S_{1\dots N}$。

输出格式

对于每组数据，如果小 E 必胜，则一行一个字符串 YES，否则一行一个字符串 NO。

样例 #1

样例输入 #1

2
4
1 2 3 1
6
1 1 1 1 1 1

样例输出 #1

YES
NO

提示

对于 $20\%$ 的数据，$N=2$。

对于另外 $20\%$ 的数据，$N\le 4$，$S_i\le 50$。

对于 $100\%$ 的数据，$1\le T\le 20$，$1\le N\le 2\times 10^4$ 且 $N$ 为偶数，$1\le S_i\le 2\times 10^9$。

基本思路

这道题又会被恶心到了，但也不差这一次了吧。

被 $SG$ 函数玩弄这么久，我们应该有一种觉悟，即一个状态应该被单独考虑，因为到最后各个 $SG$ 值都会被异或起来，故而应该将每个点单独考虑，而不是将一整个联合的局面作为状态考虑。

这题是不是可以用状压做

那么就明晰了，我们不必为一排石子哪个被操作过而烦恼，我们把每个石子单独拿出来考虑。

依照题意，对于单独的石子而言，它会被分割成两堆，因为另一堆去掉了就没有了。那么分割出来的这两堆就是它的后继状态，但是注意是这两堆共同构成了它的一个后继状态，所以不能直接将它们的 $SG$ 值异或起来。

那么怎么计算呢？我们不是在计算每一堆时都会开一个 $vis$ 数组记录后继哪些 $SG$ 值出现过吗？那么我们直接将他们开成 $bitset$ 压缩空间，还可以直接进行或操作，因为两堆共同构成后继状态的话，我们要取它的并集才可以进行 $mex$ 运算。最后参考学习笔记中的第二题，循环枚举分割成什么数量的两堆就可以了。

贡献上我的 $30$ 分代码。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=100;
int t,n,sg[N],a[N],ans;
bitset<N> s[N];
inline int mex(bitset<N> x){int i=0;while(x[i]) i++;return i;
}
int main(){ios::sync_with_stdio(false);for(int i=2;i<=70;i++){for(int j=1,k=i-1;k;j++,k--)s[i].set(mex(s[j]|s[k]));}cin>>t;while(t--){cin>>n;ans=0;for(int i=1;i<=n;i++){cin>>a[i];if(i%2==0)ans^=mex(s[a[i]]|s[a[i-1]]);}if(ans) puts("YES");else puts("NO");}return 0;
}

特别注意不能直接将一组中两堆的数量加起来使用它的 $SG$ 值，因为 $SG$值的话代表它的分割是没确定的，而一组中的分割是确定的。

为什么只有 $30$ 分？因为题目的数据范围支撑不了。显然碰到这种情况想想我们博弈论有哪两项传统技能？那就是打表预处理和打表观察了，上面这个就是打表代码。

这种题目不要想着预处理了，我们把每个数的 $vis$ （代码中的 $s$ 数组）导出来看看（）。

1: 00000000000000000000
2: 00000000000000000001
3: 00000000000000000010
4: 00000000000000000011
5: 00000000000000000100
6: 00000000000000000101
7: 00000000000000000110
8: 00000000000000000111
9: 00000000000000001000
10: 00000000000000001001
11: 00000000000000001010
12: 00000000000000001011
13: 00000000000000001100
14: 00000000000000001101
15: 00000000000000001110
16: 00000000000000001111
17: 00000000000000010000
18: 00000000000000010001
19: 00000000000000010010
20: 00000000000000010011

我们可以轻而易举地发现$i$ 的 $vis$ 就是$i-1$ 的二进制表示。

那就十分容易了。

核心代码

待补

咕咕咕