数组数组 - 题解

标签与难度

标签: 博弈论, 思维题, 对称性, Impartial Game, Game Theory, 构造难度: 1500

题目大意喵~

各位Master，大家好喵~ 今天我们来玩一个有趣的游戏，呐！

游戏是这样玩的：我们有一个只包含 1 和 -1 的数组。Alice 和 Bob 两位玩家轮流操作。每一次，玩家需要选出一个连续的、非空的子数组，并且这个子数组所有元素的乘积必须是 1。然后，把这个子数组从原数组中“咻”地一下删除掉！剩下的部分会拼接起来形成一个新的数组，给下一位玩家操作。

如果轮到谁的时候，他找不到任何可以删除的子数组了，那他就输了哦。Alice是先手，而且她和Bob都超级聪明，会选择最优的策略。我们的任务就是预测，最后谁会是胜利者呢？喵~

举个栗子：如果数组是 [1, -1, -1, 1]。 Alice 可以选择删除整个数组，因为 1 * -1 * -1 * 1 = 1。删除后数组变空，Bob 没有可以操作的子数组了，所以 Bob 输，Alice 赢！

解题思路分析

这道题是一个典型的博弈论问题，喵~ 这种双方轮流操作，可用操作仅与当前局面有关的游戏，我们称之为“公平组合游戏”（Impartial Game）。我们的目标就是找出必胜策略或者判断初始局面是必胜态还是必败态，呐。

首先，我们来分析一下什么样的子数组可以被删除。因为数组里只有 1 和 -1，一个子数组的乘积是 1，当且仅当它包含偶数个 -1。

让我们从整体来考虑，根据数组中 -1 的数量（我们叫它 neg_count 吧）来分情况讨论，这通常是解决这类问题的有效切入点哦！

情况一：`-1` 的数量是偶数

如果初始数组中 -1 的数量 neg_count 是偶数，那么整个数组所有元素的乘积就是 1 呀！这意味着，Alice 在她的第一回合，就可以选择删除整个数组！(✪ω✪) 这当然是一个合法的操作，因为整个数组是连续非空的，并且乘积为 1。

Alice 一次性把数组清空，轮到 Bob 的时候，他面对的是一个空空如也的局面，什么也做不了，直接就输掉了呢。所以，只要 neg_count 是偶数，Alice 就有必胜策略！太简单了喵！

结论 1：如果 -1 的数量是偶数，Alice 必胜。

情况二：`-1` 的数量是奇数

当 neg_count 是奇数时，事情就变得有趣起来了，喵~

此时，整个数组的乘积是 -1，所以 Alice 不能一次性清空数组了。她必须选择一个乘积为 1 的子数组来删除，也就是说，她删除的子数组 S 必须包含偶数个 -1。

那么，她操作后剩下的新数组 A' 中 -1 的数量会是多少呢？ neg_count(A') = neg_count(A) - neg_count(S) 因为 neg_count(A) 是奇数，neg_count(S) 是偶数，所以 neg_count(A') 必然还是奇数！

这意味着，只要游戏没有结束，无论谁操作，盘面上 -1 的数量永远是奇数。游戏什么时候会结束呢？当一个玩家无法操作时。对于一个非空数组，唯一无法操作的情况就是，它里面任何一个连续子数组的乘积都是 -1。这种情况只可能在数组本身就是 [-1] 时发生。

所以，这个游戏的本质，其实是看谁最后被“将军”，轮到他时，数组恰好是 [-1]。

子情况 2.1: `neg_count` 是奇数且大于 1

如果 -1 的数量是奇数，比如 3, 5, 7...，Alice 有很多选择。比如说，她可以找到数组中第一个 -1 和第二个 -1，然后把从第一个 -1 到第二个 -1 的整个子数组（包括这两个 -1）都删除掉。这个子数组里有两个 -1，乘积为 1，是合法的操作。

这个操作会把两个 -1 从游戏中移除，剩下的 -1 数量变成了 neg_count - 2，依然是奇数。但关键是，Alice 通过这种方式，可以把原本被 -1 分隔开的两个部分连接起来，极大地改变了数组的结构。她拥有非常高的操作自由度，总能找到一种方式避免自己陷入绝境。在这种情况下，可以证明 Alice 总是有办法取得胜利的，所以我们大胆猜测：

结论 2：如果 -1 的数量是奇数且大于 1，Alice 必胜。

子情况 2.2: `neg_count` 恰好为 1

这是最核心、最微妙的情况了！此时，数组的形式是 [1, 1, ..., 1, -1, 1, ..., 1]。任何合法的操作都只能是删除一个不包含 -1 的、纯 1 构成的子数组。

这像不像一个经典的游戏？我们把中间的 -1 看作一个分界线，左边的 1 串和右边的 1 串看作是两堆石子。每次操作，相当于从某一堆石子里取走任意数量的石子（删除一个 1 的子数组）。这不就是尼姆游戏 (Game of Nim) 嘛！

根据尼姆游戏的结论，先手必败的条件是所有堆石子数量的异或和为 0。在这里，就意味着： （左边 1 的数量）XOR（右边 1 的数量） == 0 也就是 （左边 1 的数量） ==（右边 1 的数量）

如果左右两边 1 的数量相等，那么 Alice（先手）就处在一个必败的局面。无论她从左边（或右边）拿走多少个 1，Bob 只要在另一边也拿走同样数量的 1，就能维持局面的“对称性”，让左右两边 1 的数量再次相等。这样下去，最终会是 Alice 先把一边拿空，然后 Bob 拿空另一边，把 [-1] 这个必输局面留给 Alice。

这个对称局面什么时候会出现呢？

数组中只有一个 -1。
-1 的左边和右边 1 的数量相等。
这也就意味着，-1 必须在数组的正中央，整个数组的长度 n 必须是奇数。

结论 3：如果 -1 的数量为 1，且 n 为奇数，且唯一的 -1 位于数组正中央，Bob 必胜。

在其他 neg_count = 1 的情况下（比如 n 是偶数，或者 -1 不在中间），左右两边 1 的数量不相等。Alice 就可以在她的第一步操作中，从数量多的那一堆里拿走一些 1，使得两堆数量相等，从而把必败局面丢给 Bob。所以，Alice 必胜。

最终总结，喵~

把所有情况整合一下，我们发现 Alice 几乎总是赢的！只有一种非常特殊的情况 Bob 能赢： 当且仅当，数组中 -1 的数量为 1，数组总长度 n 为奇数，并且那个 -1 正好在数组的中心位置时，Bob 才能获胜。 在所有其他情况下，都是 Alice 获胜！

代码实现

现在，让我们把这个思路变成优雅的代码吧，喵~

cpp

#include <iostream>
#include <vector>
#include <numeric>

// 为了让代码更清晰，我们把每个测试用例的逻辑封装成一个函数，喵~
void solve() {
    int n;
    std::cin >> n;
    std::vector<int> a(n);
    
    int neg_count = 0;
    int neg_pos = -1; // 用来记录唯一一个 -1 的位置 (0-indexed)

    for (int i = 0; i < n; ++i) {
        std::cin >> a[i];
        if (a[i] == -1) {
            neg_count++;
            neg_pos = i;
        }
    }

    // 根据我们的分析，只有一种情况Bob会赢
    // 1. 负一的数量恰好为 1 (neg_count == 1)
    // 2. 数组总长度 n 是奇数 (n % 2 != 0)
    // 3. 那个唯一的 -1 在数组正中间 (neg_pos == n / 2)
    //    对于一个长度为 n 的0-indexed数组，中间位置的索引就是 n / 2
    if (neg_count == 1 && (n % 2 != 0) && (neg_pos == n / 2)) {
        std::cout << "Bob" << std::endl;
    } else {
        // 其他所有情况，Alice都有必胜策略！
        std::cout << "Alice" << std::endl;
    }
}

int main() {
    // 加速输入输出，让程序跑得更快，像猫一样敏捷！
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int t;
    std::cin >> t;
    while (t--) {
        solve();
    }

    return 0;
}

复杂度分析

时间复杂度: 对于每个测试用例，我们只需要遍历一次数组来统计 -1 的数量和位置。所以时间复杂度是 $O(N)$ ，其中 $N$ 是数组的长度。因为有 $T$ 个测试用例，总时间复杂度是 $O(\sum N)$ 。
空间复杂度: 我们需要一个 vector 来存储输入的数组，所以空间复杂度是 $O(N)$ 。

知识点总结

这道题虽然代码很简单，但背后蕴含的博弈论思想非常有趣呢，呐！

公平组合游戏 (Impartial Game): 核心是分析必胜态和必败态。
分类讨论: 从最容易分析的特征（-1 的数量奇偶性）入手，是解决问题的金钥匙。
对称性与模仿策略: 在 neg_count = 1 的情况下，游戏可以转化为对称的尼姆游戏。当局面处于对称状态时，后手可以通过模仿先手的操作来维持对称，从而获胜。这是博弈论中一个非常强大的思想！
化繁为简: 看起来复杂的游戏规则，最终可以归结为一个非常简单的判断条件。找到这个核心条件是解题的关键。

希望这篇题解能帮助到你，喵~ 如果还有不懂的地方，随时可以再来问我哦！

数组数组 - 题解 ​

标签与难度 ​

题目大意喵~ ​

解题思路分析 ​

情况一：-1 的数量是偶数 ​

情况二：-1 的数量是奇数 ​

子情况 2.1: neg_count 是奇数且大于 1 ​

子情况 2.2: neg_count 恰好为 1 ​

最终总结，喵~ ​

代码实现 ​

复杂度分析 ​

知识点总结 ​