喵~ 主人，今天由咱来为你讲解一道有趣的博弈论题目，Blackboard Game (A. Blackboard Game) 吧！这道题看起来有点复杂，但其实只要找到其中的小秘密，就会变得非常简单哦~ ฅ'ω'ฅ

题目大意

在一个黑板上，最初写着从 0 到 n-1 的所有整数。

Alice 和 Bob 轮流玩一个游戏：

1. 首先，Alice 从黑板上选择一个数字 a 并擦掉它。
2. 然后，Bob 从黑板上选择一个数字 b 并擦掉它。
3. Bob 的选择必须满足一个条件：a + b 除以 4 的余数必须是 3，也就是 a + b ≡ 3 (mod 4)。

他们就这样一轮一轮地进行下去。如果轮到某个人，但他无法做出合法的选择（比如 Alice 找不到数字可擦，或者 Bob 找不到满足条件的 b），那么这个人就输了。

假设 Alice 和 Bob 都非常聪明，总会选择最优的策略。我们需要判断谁会赢得这场游戏，喵~

---

题解方法

这道题是典型的博弈论问题，关键在于分析游戏的核心规则 a + b ≡ 3 (mod 4)。这个规则完全是基于数字除以 4 的余数来决定的，所以我们可以把黑板上的数字按照它们 mod 4 的余数分成四类，这样问题就清晰多啦！

1. 数字分类

我们将 0 到 n-1 的所有数字根据它们除以 4 的余数分成四组：

• 第 0 组 (Type 0): x ≡ 0 (mod 4) 的数字。
• 第 1 组 (Type 1): x ≡ 1 (mod 4) 的数字。
• 第 2 组 (Type 2): x ≡ 2 (mod 4) 的数字。
• 第 3 组 (Type 3): x ≡ 3 (mod 4) 的数字。

2. 发现配对关系

现在我们来看看 a + b ≡ 3 (mod 4) 这个条件意味着什么：

• 如果 Alice 选了一个第 0 组的数 (a ≡ 0)，那么 Bob 必须选一个第 3 组的数 (b ≡ 3)，因为 0 + 3 = 3。
• 如果 Alice 选了一个第 1 组的数 (a ≡ 1)，那么 Bob 必须选一个第 2 组的数 (b ≡ 2)，因为 1 + 2 = 3。
• 反过来也是一样的，如果 Alice 选第 2 组，Bob 就必须选第 1 组；Alice 选第 3 组，Bob 就必须选第 0 组。

看到了吗，主人？这个游戏本质上就是在消耗两种配对：(第 0 组, 第 3 组) 和 (第 1 组, 第 2 组)。

3. 游戏如何结束？

每一轮，Alice 选一个数，Bob 必须从配对的组里选一个数来回应。只要 Bob 能回应，游戏就继续。

• Bob 什么时候会输？ 当 Alice 选了一个数 a，但是 a 所在配对组的另一个组已经空了，Bob 就找不到对应的 b，他就输了。
• Alice 什么时候会输？ 当轮到 Alice 时，黑板上已经没有数了，她就输了。

4. 谁会赢呢？

让我们用 c0, c1, c2, c3 分别表示四个组里数字的数量。

• (第 0 组, 第 3 组) 最多可以配成 min(c0, c3) 对。
• (第 1 组, 第 2 组) 最多可以配成 min(c1, c2) 对。

总共可以进行的、双方都能成功操作的轮数就是 P = min(c0, c3) + min(c1, c2)。 在 P 轮之后，一共会用掉 2 * P 个数字，然后又轮到 Alice。

此时，会出现两种情况：

1. 黑板上还有数字剩下： 这意味着 n > 2 * P。为什么会有数字剩下呢？因为有的组的数字比它的配对组多。比如，如果 c0 > c3，那么在消耗完所有 c3 个第 3 组的数之后，第 0 组还会有 c0 - c3 个数剩下。 这时轮到 Alice，她可以从这些“落单”的数字里随便选一个（比如一个第 0 组的数）。Bob 需要找一个第 3 组的数来配对，但是第 3 组已经空了！所以 Bob 无法行动，Bob 输了，Alice 获胜。

2. 黑板上没有数字了： 这意味着 n = 2 * P。这说明所有的数字都完美地配成了对，一个不多一个不少。轮到 Alice 时，黑板是空的，她无法选择数字，所以 Alice 输了，Bob 获胜。

所以，Bob 获胜的唯一条件是：所有数字都能完美配对，即 c0 = c3 并且 c1 = c2。

5. 计算各组数量

现在我们来算一下对于给定的 n，c0, c1, c2, c3 分别是多少。 设 q = n / 4，r = n % 4。

• 在 0, 1, ..., n-1 中，每连续 4 个数（如 0,1,2,3）都恰好包含一个 0、1、2、3 模 4 的数。这样的完整块有 q 个。
• 所以，c0, c1, c2, c3 的基础数量都是 q。
• 剩下的 r 个数会额外增加某些组的数量：
  • r=0: 无事发生。c0=q, c1=q, c2=q, c3=q。
  • r=1: 多一个 0。c0=q+1, c1=q, c2=q, c3=q。
  • r=2: 多一个 0, 1。c0=q+1, c1=q+1, c2=q, c3=q。
  • r=3: 多一个 0, 1, 2。c0=q+1, c1=q+1, c2=q+1, c3=q。

Bob 要赢，需要 c0 = c3 且 c1 = c2。我们来检查一下：

• c0 = c3 意味着 q + (r>0?1:0) = q，这只有在 r=0 时才成立。
• c1 = c2 意味着 q + (r>1?1:0) = q + (r>2?1:0)。
  • 如果 r=0，q = q，成立。
  • 如果 r=1，q = q，成立。
  • 如果 r=2，q+1 = q，不成立。
  • 如果 r=3，q+1 = q+1，成立。

两个条件必须同时满足，所以只有当 r = n % 4 = 0 时，Bob 才能赢。在所有其他情况下，Alice 都会赢！

结论就是这么简单喵~

---

题解

#include <iostream>

// 喵~ 这是解决问题的函数哦
void solve() {
    int n;
    std::cin >> n;

    // 根据我们上面的分析，主人~
    // 只有当 n 是 4 的倍数时，黑板上的数字才能完美配对。
    // 在这种情况下，Alice 进行了 n/2 轮后，黑板就空了，她就输了。
    // 所以 Bob 获胜！
    if (n % 4 == 0) {
        std::cout << "Bob\n";
    } 
    // 否则，总会有一些“落单”的数字。
    // Alice 可以在耗尽所有配对后，选择一个落单的数字。
    // 这样 Bob 就找不到对应的数字来回应，Bob 就会输掉。
    // 所以 Alice 获胜！
    else {
        std::cout << "Alice\n";
    }
}

int main() {
    // 加速一下输入输出，跑得快一点~
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int t; // 测试用例的数量
    std::cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

---

知识点介绍

这道题虽然简单，但背后也藏着一些有趣的知识点呢，喵~

1. 博弈论 (Game Theory): 博弈论是研究决策者之间策略互动的一个数学分支。这道题是一个公平组合游戏 (Impartial Game)，因为任何一个玩家可以做的操作只取决于当前的游戏状态，而与是哪个玩家在操作无关。

2. 必胜态与必败态 (Winning and Losing States): 在博弈论中，一个状态被称为必败态 (Losing Position)，是指无论当前玩家做什么，对手都有办法获胜。相反，一个状态被称为必胜态 (Winning Position)，是指当前玩家至少有一种走法，能让游戏进入一个对手的必败态。 在这道题里，当 n % 4 != 0 时，初始状态对 Alice 来说就是必胜态。当 n % 4 == 0 时，初始状态是必败态（对于先手 Alice 来说）。

3. 模运算 (Modular Arithmetic): 模运算是解决这道题的钥匙！a ≡ b (mod m) 表示 a 和 b 除以 m 的余数相同。通过模运算，我们将无限的整数世界划分成有限的几个等价类。在这道题里，我们把所有数分成了 4 个等价类，从而极大地简化了问题，把复杂的数字关系变成了简单的配对游戏。

希望我的讲解能帮助到主人哦！如果还有其他问题，随时可以再来找我，喵~ (ฅ'ω'ฅ)