题解 P2575 【高手过招】

# 博弈论 感觉前面$dalao$并没有讲清怎么转换为阶梯$nim$，所以希望我能讲清$qwq$ ------------ # 思路： 首先我们要找到阶梯分界,也就是区分每一堆的分界线，那么我们当然得找一个不变量，而我们发现，不管怎么移动，空格的数量是不变的~~（废话）~~，那么我们就以白格子为阶梯分界，来区分每一堆 例如下图就可以分为两个阶梯：  那么假如我们把第二个黑棋向右移动，就是下图：  原先的地方变为了空格，那么不就是相当于从$2$阶梯移了一颗棋子到$1$阶梯吗，这不就是裸地阶梯$nim$吗？话不多说，直接上模板$qwq$ 下面是美滋滋的代码时间~~~ ~~~cpp #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 */ ~~~