题解 P2575 【高手过招】

· · 题解

博弈论

感觉前面dalao并没有讲清怎么转换为阶梯nim，所以希望我能讲清qwq

思路：

首先我们要找到阶梯分界,也就是区分每一堆的分界线，那么我们当然得找一个不变量，而我们发现，不管怎么移动，空格的数量是不变的（废话），那么我们就以白格子为阶梯分界，来区分每一堆

例如下图就可以分为两个阶梯：

那么假如我们把第二个黑棋向右移动，就是下图：

原先的地方变为了空格，那么不就是相当于从2阶梯移了一颗棋子到1阶梯吗，这不就是裸地阶梯nim吗？话不多说，直接上模板qwq

下面是美滋滋的代码时间~~~

#include<iostream>
#include<cstdio>
#include<cstring>
#define N 27
using namespace std;
int T,n;
bool vis[N];
int main()
{
    scanf("%d",&T);
    while(T--)
    {
        int ans=0;
        scanf("%d",&n);
        for(int i=1;i<=n;++i)
        {
            int now=0,num;
            memset(vis,0,sizeof(vis));
            scanf("%d",&num);
            for(int j=1;j<=num;++j)
            {
                int in;
                scanf("%d",&in);
                vis[in]=1;
            }
            int cnt=0,tot=0;
            for(int j=20;j>=0;--j)
            {
                if(!vis[j])
                {
                    if(tot)
                    {
                        ans^=tot;
                        tot=0;
                    }
                    cnt^=1;
                }
                else
                    if(cnt)
                        ++tot;
            }
            if(tot)
                ans^=tot;
        }
        printf("%s\n",ans?"YES":"NO");
    }
    return 0;
}
/*
1
2
5 5 10 12 13 14
6 1 2 6 7 8 9

*/