题解 | #我测你的马#

题目链接

我测你的马

题目描述

在一个 $N \cdot N$ 的棋盘上，Bob 和 Alice 轮流放置马。规则是新放置的马不能攻击到任何已经存在的马。当轮到某个玩家，而他无法放置新马时，该玩家输。Bob 先手，双方均采取最优策略，判断谁将获胜。

解题思路

这是一个经典的公平组合游戏。在这类游戏中，如果双方都采取最优策略，胜负在游戏开始时就已经确定。关键在于整个游戏能够进行的总步数是奇数还是偶数。

如果总步数是奇数，那么先手方下完最后一子后，后手方将无子可下，因此先手方必胜。
如果总步数是偶数，那么后手方下完最后一子后，先手方将无子可下，因此后手方必胜。

在本题中，“总步数”就是棋盘上最多可以放置的、互不攻击的马的数量。Bob 是先手，Alice 是后手。

我们可以通过分析小棋盘来寻找规律：

当 $N=1$ 时: 棋盘只有 1 个格子。可以放置 1 个马。总步数是 1 (奇数)。先手 Bob 必胜。
当 $N=2$ 时: 棋盘有 4 个格子。在 2x2 的棋盘上，任何位置的马都无法攻击到其他位置。因此可以放满 4 个马。总步数是 4 (偶数)。后手 Alice 必胜。
当 $N=3$ 时: 3x3 的棋盘上最多可以放置 5 个马。总步数是 5 (奇数)。先手 Bob 必胜。
当 $N=4$ 时: 4x4 的棋盘上最多可以放置 8 个马。总步数是 8 (偶数)。后手 Alice 必胜。

通过以上分析，我们发现一个清晰的规律：

如果棋盘边长 $N$ 是奇数，棋盘上能容纳的马的总数是奇数，因此先手 Bob 获胜。
如果棋盘边长 $N$ 是偶数，棋盘上能容纳的马的总数是偶数，因此后手 Alice 获胜。

这个规律对于所有 $N$ 都成立。因此，我们只需要根据 $N$ 的奇偶性来判断胜负即可。

代码

cpp
java
python

#include <iostream>

using namespace std;

int main() {
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        if (n % 2 != 0) {
            cout << "Bob" << endl;
        } else {
            cout << "Alice" << endl;
        }
    }
    return 0;
}

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();
        while (t-- > 0) {
            int n = sc.nextInt();
            if (n % 2 != 0) {
                System.out.println("Bob");
            } else {
                System.out.println("Alice");
            }
        }
    }
}

t = int(input())
for _ in range(t):
    n = int(input())
    if n % 2 != 0:
        print("Bob")
    else:
        print("Alice")

算法及复杂度

算法：博弈论、数学规律
时间复杂度：对于每个测试用例，我们只进行了一次取模和判断操作，所以复杂度是 $\mathcal{O}(1)$ 。总的时间复杂度为 $\mathcal{O}(T)$ ，其中 $T$ 是测试用例的数量。
空间复杂度：只需要常数空间存储变量，复杂度为 $\mathcal{O}(1)$ 。