Hello 2026——A. Binary Array Game（01 串的首尾很重要，博弈论很少轮次最优） · znzryb
## 题目大意
这道题是 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)$。
```cpp
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](https://codeforces.com/contest/2183/submission/358031419)
::: 源代码
```cpp
/**
* 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……）