Hello 2026——A. Binary Array Game（01 串的首尾很重要，博弈论很少轮次最优）

题目大意

这道题是 Alice 和 Bob 的博弈游戏题。

游戏规则:

• 两人在一个长度为 n 的数组上进行游戏,数组只包含 0 和 1

• Alice 先手,双方轮流操作

• 每次操作选择区间 [l, r],将该区间替换为单个数字 $1 - min(a_l, ..., a_r)$

• 如果区间全是 1,则替换为 0;否则替换为 1

• 游戏持续到数组只剩一个数字为止

获胜条件:

• 如果最终剩下的数字是 0,Alice 获胜

• 否则 Bob 获胜

输入格式:

• 第一行:测试用例数 t (1 ≤ t ≤ 100)

• 每个测试用例第一行:数组长度 n (3 ≤ n ≤ 100)

• 每个测试用例第二行:n 个整数 a_i (0 ≤ a_i ≤ 1)

输出格式:

• 对于每个测试用例,输出 “Alice” 或 “Bob”(大小写不敏感)

要求: 判断在双方最优策略下谁会获胜

思路讲解

这种题目一般是这样的，看起来这个操作非常复杂，但是实际上是只需要很少轮次的最优操作，就可以得出答案。`

首先，如果整个序列都是$1$，Alice 就可以通过对整个序列进行操作立即获胜。

注意最后一次操作必须涉及至少一个$a_1$或$a_n$。我们根据$a_1$和$a_n$的值进行讨论：

如果$a_1 = 1$，那么Alice 可以直接在区间$[2,n]$上操作以获胜，因为$a_{2 \sim n}$必须包含至少一个$0$。

如果$a_n = 1$，那么Alice 可以直接在区间$[1,n-1]$上操作以获胜，因为$a_{1 \sim n-1}$必须包含至少一个$0$。

如果$a_1 = 0$且$a_n = 0$，那么在整个序列上进行操作肯定会导致Alice 失败。这意味着Alice 不能同时操作$a_1$和$a_n$。因此，在Alice 操作后，序列$a$中仍然至少会有一个$0$。Bob 然后可以在整个序列上操作以获胜。因此，在这种情况下，Bob 获胜。（这么讲有点奇怪，其实就是，你无论第一次你怎么操作，第二次 Bob 都可以直接掀桌子，得到 1）

时间复杂度：$O(\sum n)$。

void Solve() {
    ll N;
    cin >> N;
    vector<ll> A(N);
    for (int i=0;i<N;++i) {
        cin>>A[i];
    }
    // 全 1 的情况
    if (find(all(A),0)==A.end()) {
        cout<<"Alice\n";
        return;
    }
    // 只要首尾有一个是 1
    if (A.front() || A.back()) {
        cout<<"Alice\n";
        return;
    }
    // 首尾都为 0
    cout<<"Bob\n";
}

AC代码

AC

https://codeforces.com/contest/2183/submission/358031419

源代码

/**
 * Problem: A. Binary Array Game
 * Contest: Hello 2026
 * Judge: Codeforces
 * URL: https://codeforces.com/contest/2183/problem/A
 * Created: 2026-01-16 10:40:44
 * Author: Gospel_rock
 */

#include <bits/stdc++.h>
#include <ranges>
#define all(vec) vec.begin(),vec.end()
#define lson(o) (o<<1)
#define rson(o) (o<<1|1)
#define SZ(a) ((long long) a.size())
#define debug(var) cerr << #var <<":"<<var<<"\n";
#define cend cerr<<"\n-----------\n"
#define fsp(x) fixed<<setprecision(x)

using namespace std;

using ll = long long;
using ull = unsigned long long;
using DB = double;
using LD = long double;
// using i128 = __int128;
using CD = complex<double>;

static constexpr ll MAXN = (ll)1e6+10, INF = (1ll<<61)-1;
static constexpr ll mod = 998244353; // (ll)1e9+7; 
static constexpr double eps = 1e-8;
const double pi = acos(-1.0);

ll lT;

/*
 *
 */

void Solve() {
    ll N;
    cin >> N;
    vector<ll> A(N);
    for (int i=0;i<N;++i) {
        cin>>A[i];
    }
    if (find(all(A),0)==A.end()) {
        cout<<"Alice\n";
        return;
    }
    if (A.front() || A.back()) {
        cout<<"Alice\n";
        return;
    }
    cout<<"Bob\n";
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    
    cin >> lT;
    while(lT--)
        Solve();
    return 0;
}

/*

*/

心路历程（WA，TLE，MLE……）