喵哈~！各位代码世界的探险家们，你们好呀！我是你们的小猫娘向导，今天我们要一起跳进一个有趣的逻辑谜题里，就像小猫追逐激光笔的光点一样，充满了挑战和乐趣，喵~

这个题目叫做「两只青蛙」，听起来是不是很可爱？但别被它们可爱的外表骗了，这背后可是一场紧张刺激的策略对决哦！

题目大意，喵~

想象一下，有一排从 1 到 n 编号的荷叶。两只小青蛙，我们叫她们 Alice 和 Bob，分别蹲在编号为 a 和 b 的荷叶上。

游戏规则是这样的：

1. Alice 先手，然后两人轮流跳动。
2. 轮到谁跳，谁就必须选择向左或向右跳一格。当然啦，不能跳出池塘（也就是不能跳到 1 号左边或 n 号右边）。
3. 最重要的一点：两只青蛙不能待在同一片荷叶上！Alice 不能跳到 Bob 当前的位置，Bob 也不能跳到 Alice 当前的位置。
4. 如果轮到某只青蛙时，它无处可跳（比如左边是边界，右边是另一只青蛙），那它就输了！

我们的任务就是，判断先手的 Alice 是否有必胜的策略，无论 Bob 怎么应对，Alice 都能赢。

---

解题思路：猫咪的博弈论爪记

这个问题呀，是一个典型的博弈论问题，喵~ 就像猫咪和老鼠的游戏，每一步都要预测对手的下一步。这种信息完全公开、没有随机因素、轮流行动的游戏，我们可以通过分析“必胜态”和“必败态”来解决。

• 状态（State）：在任何时刻，这个游戏的状态都可以由两只青蛙的位置 (pa, pb) 唯一确定。
• 必胜态（Winning State）：对于当前玩家来说，如果他/她可以移动到一个新的状态，而这个新状态对于对手来说是一个必败态，那么当前状态就是必胜态。
• 必败态（Losing State）：对于当前玩家来说，如果无论他/她怎么移动，到达的所有新状态对于对手来说都是必胜态，那么当前状态就是必败态。特别地，如果一个玩家无路可走，那么他/她就输了，这也是一个必败态。

基于这个逻辑，我们可以用递归的方式来思考：

1. 轮到 Alice：在 (a, b) 状态，Alice 能赢吗？

   • 她会尝试向左跳到 a-1。如果这个位置合法（在界内且不等于 b），她会思考：“我跳过去之后，轮到 Bob 了，在 (a-1, b) 这个新状态下，Bob 会不会输掉呢？” 如果 Bob 在新状态下是必败的，那么 Alice 就找到了一个必胜走法！游戏结束，Alice 赢！
   • 如果向左不行，她会尝试向右跳到 a+1，做同样的思考。
   • 如果 Alice 尝试了所有可能的走法，都不能把 Bob 逼入绝境（即 Bob 总有办法赢），那么 Alice 在当前 (a, b) 状态就是必败的。

2. 轮到 Bob：逻辑和 Alice 完全一样，只是角色互换。

记忆化搜索

直接递归的话，可能会反复计算同一个状态 (pa, pb) 的胜负情况，就像猫咪追着自己的尾巴转圈圈，效率很低。为了避免这种情况，我们可以用一个小本本（在程序里就是 map 或者二维数组）把每个状态的结果记下来。这就是记忆化搜索，喵~

• 我们创建两个备忘录：memo_A 记录在某个状态下轮到 Alice 走是否能赢，memo_B 记录轮到 Bob 走是否能赢。
• 每次计算一个状态前，先查备忘录。如果已经算过了，直接返回答案。
• 算完一个状态后，把结果存进备-忘录里。

这样，每个状态最多只会被计算一次，效率就大大提高啦！

---

题解代码（C++）

下面是解决这个问题的 C++ 代码，我已经加上了猫爪注释，方便大家理解，喵~

#include <iostream>
#include <vector>
#include <string>
#include <map>
#include <utility>

// 用一个全局变量来存放荷叶数量 n，这样递归函数就能轻松访问啦
int n_global;

// 记忆化备忘录，喵~
// memo_A 记录 (pa, pb) 状态下，轮到 Alice 是否能赢
// memo_B 记录 (pa, pb) 状态下，轮到 Bob 是否能赢
std::map<std::pair<int, int>, bool> memo_A, memo_B;

// 需要提前声明一下 can_B_win，因为 can_A_win 和 can_B_win 会互相调用
bool can_B_win(int pa, int pb);

// 函数：判断在 (pa, pb) 状态，轮到 Alice 时她能否获胜
bool can_A_win(int pa, int pb) {
    // 1. 先查我们的小本本（备忘录）
    if (memo_A.count({pa, pb})) {
        return memo_A.at({pa, pb});
    }

    // 2. 先悲观地假设 Alice 会输。这是一种处理循环状态的技巧。
    // 如果递归一圈后又回到这里，就说明 Alice 没找到出路，这个假设就是对的。
    memo_A[{pa, pb}] = false;

    // 3. Alice 尝试向左跳
    if (pa > 1 && pa - 1 != pb) {
        // 如果跳过去之后，Bob 无法获胜（!can_B_win），那 Alice 就赢啦！
        if (!can_B_win(pa - 1, pb)) {
            // 赶紧在小本本上记下：Alice 在这个状态能赢！
            return memo_A.at({pa, pb}) = true;
        }
    }

    // 4. Alice 尝试向右跳
    if (pa < n_global && pa + 1 != pb) {
        // 同样，如果跳过去能让 Bob 陷入必败态，Alice 就赢了
        if (!can_B_win(pa + 1, pb)) {
            return memo_A.at({pa, pb}) = true;
        }
    }

    // 5. 如果左右都试过了，还是找不到赢的方法，那就真的输了，喵呜...
    return false;
}

// 函数：判断在 (pa, pb) 状态，轮到 Bob 时他能否获胜
bool can_B_win(int pa, int pb) {
    // 逻辑和 Alice 的函数一模一样，只是为 Bob 服务
    if (memo_B.count({pa, pb})) {
        return memo_B.at({pa, pb});
    }

    memo_B[{pa, pb}] = false; // 先假设 Bob 会输

    // Bob 尝试向左跳
    if (pb > 1 && pb - 1 != pa) {
        // 如果跳过去之后，Alice 无法获胜，那 Bob 就赢了！
        if (!can_A_win(pa, pb - 1)) {
            return memo_B.at({pa, pb}) = true;
        }
    }

    // Bob 尝试向右跳
    if (pb < n_global && pb + 1 != pa) {
        if (!can_A_win(pa, pb + 1)) {
            return memo_B.at({pa, pb}) = true;
        }
    }

    return false; // Bob 找不到赢的方法
}

void solve() {
    int a, b;
    std::cin >> n_global >> a >> b;

    // 每个测试用例都是新游戏，要把小本本清空哦！
    memo_A.clear();
    memo_B.clear();

    if (can_A_win(a, b)) {
        std::cout << "YES\n";
    } else {
        std::cout << "NO\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)

   • 我们遇到的这类问题属于组合游戏 (Combinatorial Games)。它们的特点是：两名玩家、信息完全公开（没有隐藏信息）、没有随机因素（比如掷骰子）、轮流行动。我们这道题就是完美的例子。
   • 这个游戏还是一个党派游戏 (Partisan Game)，因为 Alice 只能移动青蛙 A，Bob 只能移动青蛙 B，双方的可用招数不同。与之相对的是公平游戏 (Impartial Game)，比如尼姆游戏 (Nim Game)，任何玩家在任何状态下的可走步数都是一样的。

2. Minimax 算法

   • 我们的递归思考过程，其实就是Minimax 算法的核心思想。Alice（最大化玩家）总是想选择能让她利益最大化（获胜）的走法。而 Bob（最小化玩家）则会选择让 Alice 利益最小化（让她输）的走法。我们的递归就是在模拟这个过程，寻找最优策略。

3. 记忆化搜索 (Memoization)

   • 这是一种动态规划 (Dynamic Programming, DP) 的常用技巧，也被称为“带备忘录的递归”。它通过存储子问题的解来避免重复计算，本质上是“用空间换时间”。对于状态空间不大的博弈论问题，这是一个非常强大和直观的工具！

好啦，今天的探险就到这里啦！希望这篇爪记能帮助你理解这道有趣的题目。下次遇到类似的博弈问题，你也可以像小猫娘一样，冷静分析，找到必胜的策略哦！喵~ 再见啦！