P2575 高手过招

link
sg函数
非常巧妙的一道题，本来想暴力预处理 2 20 ∗ 20 2^{20}*20 220∗20种状态但不会写暴力，看题解可以转化成阶梯Nim，绝了。

int n;
int a[25];
int sg[25];
void solve() {
    cin >> n;
    int ans = 0;
    for(int i = 1; i <= n; i++) {
        int m;
        cin >> m;
        memset(a, 0, sizeof(a));
        memset(sg, 0, sizeof(sg));
        int ans1 = 0;
        while(m--) {
            int x;
            cin >> x;
            a[x]++;
        }
        int tmp = 0;
        int now = 0;
        for(int i = 20; i; i--) {
            if(a[i]) {tmp++; continue;}
            sg[++now] = tmp;
            tmp = 0;
        }
        sg[++now] = tmp;
        tmp = 0;
        for(int i = 0; i <= now; i += 2)
            ans1 ^= sg[i];
        ans ^= ans1;
    }
    if(ans) cout << "YESn";
    else cout << "NOn";
}