Binary Array Game

GitHub跳转原题关系图返回列表

最后一步必含首或尾；Alice 胜当且仅当 a1=1 或 an=1。

OJ: codeforces

题目 ID: 2183A

难度:普及-

标签:博弈分类讨论

日期: 2026-07-14 23:50

目录

  1. 题意
  2. 思路
  3. 代码
  4. 复杂度
  5. 总结

题意

0/10/1 数组上 Alice 先手轮流操作：选长度至少 22 的区间，压成一个数 1−min⁡1-\min。全 11 变 00，否则变 11。只剩一个数时：为 00 则 Alice 胜，为 11 则 Bob 胜。双方最优，判胜者。

思路

先看特殊情况：若整段全是 11，Alice 直接对 [1,n][1,n] 操作，得到 00，立刻获胜。

注意到最后一次操作一定覆盖 a1a_1 或 ana_n 中的至少一个（因为最后一次要把长度 ⩾2\geqslant 2 的序列压成一个数，两端至少有一个被吃进这段）。于是按 a1a_1、ana_n 分类：

  1. a1=1a_1 = 1
    Alice 直接操作 [2,n][2,n]。此时 a2∼ana_2\sim a_n 中必有至少一个 00（否则就是全 11，上面已处理），所以 min⁡=0\min=0，插入 11，数组变成 [1,1][1,1]。Bob 只能再合并成 00，Alice 胜。

  2. an=1a_n = 1
    对称地，Alice 操作 [1,n−1][1,n-1]，同样得到 [1,1][1,1]，Alice 胜。

  3. a1=0a_1 = 0 且 an=0a_n = 0
    Alice 若操作整段，有 00 → 得 11，立刻输。
    因此 Alice 不能同时吃掉 a1a_1 和 ana_n。操作后序列里至少还剩一个 00。
    轮到 Bob 时，他对整段操作，得 11，Bob 胜。

综上：Alice 胜当且仅当 a1=1a_1=1 或 an=1a_n=1。 读入后看两端即可。

代码

cpp
/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-07-14 23:50
 * update_at: 2026-07-14 23:50
 */
#include <bits/stdc++.h>
using namespace std;

std::vector<int> a;
int T;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    std::cin >> T;
    while (T--) {
        int n;
        std::cin >> n;
        a.clear();
        for(int i = 1;i <= n ;++i ) // i: 1->n
        {
            int t;
            std::cin >> t;
            a.push_back(t);
        }
        if(a[0] == 1 || a[a.size() - 1])
            std::cout << "Alice" << "\n";
        else
            std::cout << "Bob" << "\n";
    }

    return 0;
}

复杂度

时间 O(∑n)O(\sum n)，空间 O(n)O(n)。

总结

关键观察：最后一手必含首或尾，从而把博弈压成对 a1a_1、ana_n 的三分讨论。两端有 11 时 Alice 一步构造 [1,1][1,1]；两端都是 00 时 Alice 消不掉全部 00，Bob 整段收掉。