A2013 取石子游戏4

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

/*
取石子游戏 4：一排石子堆，每次从最左或最右的一堆取走任意正数颗。

核心结论（区间 DP）：
  对一段区间 M，记 Match(M) = 所有使 (w, M, z) 处于必败态的 (w, z) 集合。
  Match(M) 恒等于两个有序序列的「按序配对」：
      W(M) = 正整数去掉 fw(M)      （左端候选）
      Z(M) = 正整数去掉 fz(M)      （右端候选）
  把 W(M) 与 Z(M) 从小到大一一配对即得 Match(M)。
  其中
      fz([i..j]) = rmin_{[i+1..j]}(a[i])   （去掉后缀后，a[i] 在 Match 里配到的右端值）
      fw([i..j]) = cmin_{[i..j-1]}(a[j])   （去掉前缀后，a[j] 在 Match 里配到的左端值）
  rmin/cmin 都能 O(1) 算出：把某个值在「去掉一个数」的有序序列里的名次求出来，
  再映射回另一条序列即可。

最终整堆 (a[1..n]) 必败 <=> (a[1], a[n]) 落在 Match(a[2..n-1]) 里。
*/

static const long long INF = (1LL << 60);

// 在 Match 中，w 对应的右端值；w 被排除时返回 INF。
long long rminOf(long long w, long long p, long long q) {
    if (p != INF && w == p) return INF;
    long long rank = (p == INF || w < p) ? w : w - 1;
    if (q == INF) return rank;
    return (rank < q) ? rank : rank + 1;
}

// 在 Match 中，z 对应的左端值；z 被排除时返回 INF。
long long cminOf(long long z, long long p, long long q) {
    if (q != INF && z == q) return INF;
    long long rank = (q == INF || z < q) ? z : z - 1;
    if (p == INF) return rank;
    return (rank < p) ? rank : rank + 1;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T;
    cin >> T;
    while (T--) {
        int n;
        cin >> n;
        vector<long long> a(n);
        for (long long &x : a) cin >> x;

        vector<vector<long long>> fw(n, vector<long long>(n, INF));
        vector<vector<long long>> fz(n, vector<long long>(n, INF));

        for (int len = 1; len <= n; len++) {
            for (int i = 0; i + len <= n; i++) {
                int j = i + len - 1;
                if (len == 1) {
                    fz[i][j] = a[i];
                    fw[i][j] = a[i];
                    continue;
                }
                // fz[i][j] = 去掉 a[i] 之后它在 Match([i+1..j]) 里配到的右端值
                fz[i][j] = rminOf(a[i], fw[i + 1][j], fz[i + 1][j]);
                // fw[i][j] = 去掉 a[j] 之后它在 Match([i..j-1]) 里配到的左端值
                fw[i][j] = cminOf(a[j], fw[i][j - 1], fz[i][j - 1]);
            }
        }

        bool lose;
        if (n == 1) {
            lose = false;                      // 一堆石子：先手一次取完，必胜
        } else if (n == 2) {
            lose = (a[0] == a[1]);
        } else {
            long long p = fw[1][n - 2], q = fz[1][n - 2];
            long long w = a[0], z = a[n - 1];
            lose = true;
            if (p != INF && w == p) lose = false;
            if (q != INF && z == q) lose = false;
            if (lose && !(w <= cminOf(z, p, q))) lose = false;
            if (lose && !(z <= rminOf(w, p, q))) lose = false;
        }
        cout << (lose ? 0 : 1) << "\n";
    }
    return 0;
}