Luogu P2575 高手过招

题目链接 (Click) (Here)

关键在于转换成阶梯(Nim)的模型。最开始把题目看错了，理解正确后发现棋子可以向后跳不止一位，那么就比较简单了。

这里把空格看做阶梯，棋子看做硬币，这样整个模型就满足阶梯(Nim)的性质了。阶梯(Nim)的证明我不会，请自己(yy)。

#include <bits/stdc++.h>
using namespace std;

const int M = 30;
const int N = 1010;

int n, t, a[M], SG[M], cnt[M], fz[N];

int main () {
	cin >> t;
    while (t--) {
        cin >> n;
        int ans = 0, len = 0;
        for (int i = 1; i <= n; ++i) {
            memset (cnt, 0, sizeof (cnt));
            cin >> len;
            for (int i = 1; i <= len; ++i) {
                cin >> a[i], cnt[a[i]]++;
			}
            int tot = 0, p = 20, fg = 0;
            while (cnt[p]) --p;
			while (p != 0) {
                if (!cnt[p]) {
					ans ^= (fg ? tot : 0), fg ^= 1, tot = 0;
                } else {
					++tot;
				}
				p = p - 1;
		    }
            ans ^= (fg ? tot : 0);
        }
        cout << (ans ? "YES" : "NO") << endl;
    }
}