我是不会告诉你我学了5min就学会了的
值得注意的是SG函数是 公平类型游戏，而公平类型游戏具有三个特点：
1 两人进行博弈时交替行动
2 在博弈的任意时刻 ，可以执行的合法行动和轮到哪名玩家无关。
3 不能操作的玩家判负。
这样来看我们发现游戏的结果之和游戏的初始局面和谁是先后手有关..所以对于这类游戏如何快速判断胜负就是SG函数干的事情了。
具体的对于一个局面来说我们定义(SG(G)=mex(SG(y_1),SG(y_2),...)的G的后继局面的最小的没有出现过的局面)。
这样显然我们根据SG函数就可以轻易的解决一些类型的博弈问题。
LINK：高手过招
好像很困难的样子 但是 利用SG函数可以轻易解决这个问题。
有多个局面显然对于总局面SG((G))=SG((n_1))^SG((n_2))...对于单个局面 SG(n)=mex(SG((y_1)),SG((y_2)),SG((y_3))...); 对于本题我们求出SG((n))即可。
但是好像并不好求 状压？应该不太行...因为复杂度高且不太容易实现。我也没有比较好的办法 直接爆搜记忆化好了..
还真的被我搜出来了...wa了一个点 T了好多 正常...再想一个比较好的解决方法。
发现了一个很棒的东西发现每一行的东西必败态都是一样的也就是说我只需要爆搜一次预处理即可 复杂度2^(20)*20+nT..噢哟我有点蠢..
关于SG函数的整体局面证明我还没有习会等学到了再说..
const int MAXN=21;
int T,n,ans;
int f[1<<MAXN];//f[x]表示当前局面为x的SG
inline int dfs(int s)
{
int vis[MAXN];
memset(vis,0,sizeof(vis));
if(f[s]!=-1)return f[s];
int mark=0,last=-1;
for(int i=19;i>=0;--i)
{
if(!(s&(1<<i)))last=i;
else
{
if(!(s&(1<<(i+1)))&&i<=18)vis[dfs((s^(1<<i))|(1<<(i+1)))]=1;
else if(last!=-1)vis[dfs((s^(1<<i))|(1<<last))]=1;
}
}
while(vis[mark])++mark;
f[s]=mark;
return f[s];
}
int main()
{
//freopen("1.in","r",stdin);
T=read();
memset(f,-1,sizeof(f));
for(int i=1;i<(1<<20);++i)dfs(i);
//for(int i=0;i<=19;++i)cout<<f[1<<i]<<endl;
while(T--)
{
n=read();ans=0;
for(int i=1;i<=n;++i)
{
int x=read();
int s=0;
for(int j=1;j<=x;++j)s|=1<<(read()-1);
ans=ans^f[s];
}
if(ans>0)puts("YES");
else puts("NO");
}
return 0;
}
题解中还给出了阶梯NIM的模型..可以了解一下。
阶梯NIM 模型：有n个位置 每个位置上有(a_i)个石子 有两个人轮流操作 操作步骤是：挑选(1...n)中任一一个存在石子的位置(i)，将至少(1)个石子移动至(i−1)位置,也就是最后所有石子都堆在在0这个位置。
谁不能操作谁输,问先手必胜还是必败。考虑SG？其实没有那么麻烦其本质上还是NIM游戏。
这等价于 求位置上奇数的(a_i)异或和。证明：如果大家都只动奇数堆的游戏那么这将等价于NIM游戏。如果有人动偶数堆了 我们把刚才动的棋子数都再移到另一堆偶数堆处。
这样归纳一下发型其实就是只动了奇数堆的石子强制对方玩NIM游戏 当然如果后手的话也会这样强制对手玩NIM。
所以这就是阶梯NIM。考虑刚刚这道题目，经过非常巧妙的推敲的确是一个非常不容易看出来的阶梯NIM。
以每一个白格子为阶 最后一个位置后再加一个白格子意味着0阶 也就是说到了0阶的点都不能再动了 奇偶接着往下分。
那么则有考虑一下2种操作一种是直接向右移一种是跳跃 对于偶数阶来说如果其能向右移到奇阶之上那么显然奇阶也是可以向右移的奇阶向右移抵消即可。
如果是向右跳跃 那么则有偶数阶直接全移到奇数阶上那么显然奇数阶也是可以跳跃的 跳跃抵消刚才带来的效果即可。
考虑对于奇阶 由于每次必须操作 那么奇阶要么就向右移动一个 也可以移动两个使用跳跃直接移动所以这根阶梯NIM模型一样了。
const int MAXN=21;
int T,n,ans;
int a[MAXN];
int main()
{
freopen("1.in","r",stdin);
T=read();
while(T--)
{
n=read();
int target=0;
for(int i=1;i<=n;++i)
{
int x=read();
int s=0,mark=0;
for(int j=1;j<=x;++j)a[read()]=1;
for(int j=20;j>=1;--j)
{
while(a[j])
{
++mark;
a[j]=0;--j;
}
if(s)target=target^mark;
s=s^1;mark=0;a[j]=0;
}
}
if(target>0)puts("YES");
else puts("NO");
}
return 0;
}
LINK：SDOI E&D
这道题 考虑 各个组中的石子个数是不影响的所以我们只需要求出每一组的石子的SG 然后异或起来即可。
发现一堆石子中两个数字只要有一个数字是偶数那么对于这个局面是必胜的但是这不能帮助我们判断胜局。
LINK：一个写的比较好的SG函数入门
接下来其实就是 生成SG函数了 这个还是比较难看出来的 我们打表之后发现一个数字的SG函数是其n-1
那么两个数字的SG就是或起来了 那么就利用异或判断即可。
const int MAXN=20010;
int T,n;
int a[MAXN],ans;
int main()
{
freopen("1.in","r",stdin);
T=read();
while(T--)
{
ans=0;n=read();
for(int i=1;i<=n;++i)
{
a[i]=read();
int cnt=0;
if(!(i&1))
{
int w=(a[i]-1)|(a[i-1]-1);
while(w&1)++cnt,w=w>>1;
}
ans=ans^cnt;
}
if(ans)puts("YES");
else puts("NO");
}
return 0;
}