喵喵喵~ 和整数玩游戏吧！ (Problem 1899A)

哈喽，各位小伙伴们，你们好呀！咱是乃爱的猫娘一枚，今天也要元气满满地和大家一起学习算法喵~ (ฅ'ω'ฅ)

今天我们要看的是一道非常有趣的博弈论小题目，Codeforces 上的 1899A - Game with Integers。别看是博弈论，其实超级简单，就像逗猫棒一样好玩哦！

---

题目大意

Vanya 和 Vova 在玩一个数字游戏，规则是这样哒：

1. 一开始，他们会得到一个整数 n。
2. Vanya 先手，然后两人轮流操作。
3. 每一次操作，玩家可以把当前的数字 +1 或者 -1。
4. Vanya 的胜利条件：在 Vanya 操作之后，如果数字变成了 3 的倍数，那么 Vanya 就立刻获胜！
5. Vova 的胜利条件：如果总共进行了 10 次操作后 Vanya 还没赢，那么 Vova 就获胜。

我们的任务就是，假设两个人都绝顶聪明（玩得都最优），根据初始的数字 n，判断谁会赢。

---

解题思路

这是一道典型的博弈论入门题，不过不用怕喵，我们不需要想得太复杂。关键在于分析 Vanya 的胜利条件。

Vanya 的目标是让数字变成 3 的倍数。而 Vova 的目标就是，不让 Vanya 得逞！

我们来分析一下数字除以 3 的余数，这可是解题的钥匙哦！一个整数 n 除以 3，余数只可能是 0, 1, 2 这三种情况。

情况一：轮到 Vanya 操作

我们站在 Vanya 的角度想一想，他什么时候能赢呢？

• 如果当前的数字 n 除以 3 的余数是 1 (也就是 n % 3 == 1)。 Vanya 是不是很聪明？他只要把数字 -1，新的数字就是 n-1。n-1 除以 3 的余数就变成了 0！耶！Vanya 在他的第一回合就赢啦！(๑•̀ㅂ•́)و✧

• 如果当前的数字 n 除以 3 的余数是 2 (也就是 n % 3 == 2)。 Vanya 同样可以很机智地把数字 +1，新的数字就是 n+1。n+1 除以 3 的余数也变成了 0！Vanya 又在第一回合就赢了！

• 如果当前的数字 n 除以 3 的余数是 0 (也就是 n % 3 == 0)。 这就有点麻烦了喵... Vanya 必须进行操作，他要么 +1，要么 -1。

  • 如果 +1，数字变成 n+1，除以 3 的余数是 1。
  • 如果 -1，数字变成 n-1，除以 3 的余数是 2。 无论哪种选择，得到的数字都不是 3 的倍数。所以，Vanya 在这一步无法获胜。轮到 Vova 操作了。

情况二：轮到 Vova 操作

Vova 什么时候上场呢？只有在 Vanya 无法一步制胜的时候，也就是初始 n 是 3 的倍数时。

现在 Vova 手里的数字，要么是余数为 1，要么是余数为 2。Vova 的目标是阻止 Vanya 赢。他要怎么做呢？他只需要把 Vanya 丢给他的“烂摊子”再丢回去就行啦！

• 如果 Vova 拿到的数字除以 3 余 1，他就可以 -1，让数字变回 3 的倍数。
• 如果 Vova 拿到的数字除以 3 余 2，他就可以 +1，让数字变回 3 的倍数。

看到了吗？只要一开始 n 是 3 的倍数，Vanya 无论怎么操作，都会得到一个非 3 的倍数；而 Vova 总能一步操作把数字变回 3 的倍数。

这样一来一回，Vanya 每次拿到的都是 3 的倍数，他永远无法在自己的回合后让数字成为 3 的倍数。所以 Vanya 永远赢不了。等到 10 个回合过去，Vova 就自动获胜啦。

结论

• 如果初始数字 n 不是 3 的倍数（n % 3 != 0），先手 Vanya 可以在第一步就获胜。所以输出 "First"。
• 如果初始数字 n 是 3 的倍数（n % 3 == 0），先手 Vanya 永远无法获胜，后手 Vova 会赢。所以输出 "Second"。

那个 10 回合的限制其实是个烟雾弹，因为如果 Vanya 不能在第一回合赢，那么在最优策略下他永远也赢不了啦~

---

题解代码

下面是具体的实现代码，非常简洁明了的说~

#include <iostream>

// 这个函数用来解决单个测试用例喵
void solve() {
    int n;
    std::cin >> n;

    // 游戏的结果只取决于 n 除以 3 的余数
    // Vanya 是先手，他想赢，就必须在他操作后让数字能被 3 整除
    // Vova 是后手，他会尽力阻止 Vanya

    // 情况1：n 不能被 3 整除
    // 这意味着 n % 3 等于 1 或者 2
    // 如果 n % 3 == 1，Vanya 可以减 1，得到 n-1，(n-1) % 3 == 0。Vanya 第一回合就赢啦。
    // 如果 n % 3 == 2，Vanya 可以加 1，得到 n+1，(n+1) % 3 == 0。Vanya 也是第一回合就赢啦。
    // 两种子情况 Vanya 都能一步获胜，因为他玩得最好，所以他肯定会这么走。
    if (n % 3 != 0) {
        std::cout << "First\n";
    } 
    // 情况2：n 可以被 3 整除
    // 也就是 n % 3 == 0
    // 轮到 Vanya，他必须 +1 或者 -1。
    // 得到的新数字会是 n+1 (余1) 或者 n-1 (余2)。
    // 无论哪种，都不能被 3 整除，所以 Vanya 这回合赢不了。
    //
    // 然后轮到 Vova。Vova 手里的数字 k 肯定满足 k % 3 != 0。
    // Vova 的最佳策略就是不让 Vanya 赢，他可以把数字变回 3 的倍数。
    // 如果 k % 3 == 1，Vova 就 -1，变回 3 的倍数。
    // 如果 k % 3 == 2，Vova 就 +1，变回 3 的倍数。
    // 所以，Vova 总能保证轮到 Vanya 时，数字都是 3 的倍数。
    // 这就意味着 Vanya 永远也赢不了。10回合后，Vova 获胜。
    else {
        std::cout << "Second\n";
    }
}

int main() {
    // 加上这两行能让输入输出快一点哦，是竞赛小技巧~
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);

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

    return 0;
}

---

知识点介绍

1. 博弈论入门 (Game Theory)

博弈论是研究决策者之间策略互动的数学理论。听起来高大上，但很多小游戏都蕴含着它的思想。 在这道题里，我们分析了：

• 必胜态 (Winning State)：对于当前玩家来说，存在一种走法，无论对手如何应对，自己都能赢。对于 Vanya 来说，拿到一个 n % 3 != 0 的数就是必胜态。
• 必败态 (Losing State)：对于当前玩家来说，无论自己怎么走，对手都存在一种应对策略使自己最终输掉。对于 Vanya 来说，拿到一个 n % 3 == 0 的数就是必败态。
• 最优策略 (Optimal Strategy)：每个玩家都会选择能让自己走向胜利（或避免失败）的最佳操作。

这道题就是通过分析当前状态是必胜还是必败，来直接推断出结果的。

2. 模运算 (Modulo Operation)

模运算，也就是我们代码里用的 % 符号，是求余数的运算。比如 10 % 3 = 1，5 % 2 = 1。

在这个问题里，模运算是我们的超级武器！因为胜利条件和“3的倍数”有关，所以我们自然而然地想到，一个数最重要的性质就是它除以 3 的余数。通过 n % 3，我们把所有可能的整数 n 简化为了 0, 1, 2 三种状态，大大简化了问题分析的复杂度。这是解决很多数论问题的常用思路哦！

---

好啦，今天的题解就到这里啦！是不是很简单很有趣呢？希望这篇文章能帮到你喵~ 如果有任何问题，欢迎随时来找我玩！下次再见啦！(>^ω^<)