「洛谷 P2575」高手过招

一行棋盘，若干个棋子，初始状态给出，每次可将棋子移到右侧第一个空格（棋子与空格不一定相邻 如：1101->1011/0111），不能移者输。

---

暴力好像是可以的，毕竟 $2^{20}$ 挺小的

发现一块棋子

011110
->
011101
011011
010111
001111

Vexalwig_Goodwcoffin

首先，我们在整个序列前面加上一个空格（设此时空格个数为 $C+1$ ），然后从右到左将所有空格编号为 $0$ 至 $C$ 。令第 $i$ 级阶梯上的棋子数为编号为ii的空格右边的连续棋子个数。

以下用■表示棋子，□表示空格。则对于这个场景：

(□)□■□□□□□□□□□□□□□□□□■■

有第 $0$ 至 $17$ 级阶梯（容易数出有 $18$ 个空格）棋子个数分别是 $\{2,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0\}$ 。

将一个棋子移至右边第一个空格时，相当于将其与其右边相邻的所有棋子移到下一级阶梯。如这样：

(□)□■□□□□□□□□□□□□□□□□■■变成

(□)□□■□□□□□□□□□□□□□□□■■时相当于

$\{2,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0\}$ 变成

$\{2,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0\}$（第1616层一颗棋子下移一级阶梯），又如：

(□)■■■□□■变成

(□)■□■■□■时相当于

$\{1,0,3\}$ 变成

$\{1,2,1\}$（第 $2$ 层两颗棋子下移一级阶梯）。

我们发现，当所有棋子都在第 $0$ 级阶梯时，先手无法操作，必败。

转化为阶梯博弈模型

#include <algorithm>
#include <bitset>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <deque>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <utility>
#include <vector>
#define rep(i, l, r) for (int i = (l); i <= (r); ++i)
#define per(i, l, r) for (int i = (l); i >= (r); --i)
using std::cerr;
using std::cin;
using std::cout;
using std::endl;
using std::make_pair;
using std::pair;
typedef pair<int, int> pii;
typedef long long ll;
typedef unsigned int ui;
typedef unsigned long long ull;
int main() {
#ifdef LOCAL
    freopen("input", "r", stdin);
#endif
    std::ios::sync_with_stdio(false);
    cout.tie(0);
    int T;
    cin >> T;
    std::bitset<25> a;
    while (T--) {
        int n;
        cin >> n;
        int ans = 0;
        rep(i, 1, n) {
            a = 0;
            int m;
            cin >> m;
            rep(i, 1, m) {
                int x;
                cin >> x;
                a[x] = 1;
            }
            int cnt = 0, tot = 0, ans1 = 0;
            per(i, 20, 0) {
                if (a[i] == 0) {
                    if (cnt & 1) ans1 ^= tot;
                    cnt++, tot = 0;
                } else
                    tot++;
            }
            ans ^= ans1;
        }
        cout << (ans ? "YES" : "NO") << endl;
    }
    return 0;
}