1025-除数博弈

Raphael Liu Lv10
  2023-09-13 00:47:26 2023-09-13 00:47:26 Created   2023-09-13 16:06:25 2023-09-13 16:06:25 Updated    

爱丽丝和鲍勃一起玩游戏，他们轮流行动。爱丽丝先手开局。

最初，黑板上有一个数字 n 。在每个玩家的回合，玩家需要执行以下操作：

  • 选出任一 x，满足 0 < x < n 且 n % x == 0 。
  • 用 n - x 替换黑板上的数字 n 。

如果玩家无法执行这些操作，就会输掉游戏。

只有在爱丽丝在游戏中取得胜利时才返回 true 。假设两个玩家都以最佳状态参与游戏。

示例 1：

**输入：** n = 2
**输出：** true
**解释：** 爱丽丝选择 1，鲍勃无法进行操作。

示例 2：

**输入：** n = 3
**输出：** false
**解释：** 爱丽丝选择 1，鲍勃也选择 1，然后爱丽丝无法进行操作。

提示：

  • 1 <= n <= 1000

方法一：数学

思路与算法

博弈类的问题常常让我们摸不着头脑。当我们没有解题思路的时候，不妨试着写几项试试：

  • n = 1 的时候，区间 (0, 1) 中没有整数是 n 的因数，所以此时 Alice 败。
  • n = 2 的时候，Alice 只能拿 1，n 变成 1，Bob 无法继续操作，故 Alice 胜。
  • n = 3 的时候，Alice 只能拿 1，n 变成 2，根据 n = 2 的结论，我们知道此时 Bob 会获胜，Alice 败。
  • n = 4 的时候，Alice 能拿 1 或 2，如果 Alice 拿 1，根据 n = 3 的结论，Bob 会失败，Alice 会获胜。
  • n = 5 的时候，Alice 只能拿 1，根据 n = 4 的结论，Alice 会失败。
  • ……

写到这里，也许你有了一些猜想。没关系，请大胆地猜想，在这种情况下大胆地猜想是 AC 的第一步。也许你会发现这样一个现象：n 为奇数的时候 Alice（先手）必败，n 为偶数的时候 Alice 必胜。 这个猜想是否正确呢？下面我们来想办法证明它。

证明

  1. n = 1 和 n = 2 时结论成立。

  2. n > 2 时，假设 n \leq k 时该结论成立，则 n = k + 1 时：

    • 如果 k 为偶数，则 k + 1 为奇数，x 是 k + 1 的因数，只可能是奇数，而奇数减去奇数等于偶数，且 k + 1 - x \leq k，故轮到 Bob 的时候都是偶数。而根据我们的猜想假设 n\le k 的时候偶数的时候先手必胜，故此时无论 Alice 拿走什么，Bob 都会处于必胜态，所以 Alice 处于必败态。
    • 如果 k 为奇数，则 k + 1 为偶数，x 可以是奇数也可以是偶数，若 Alice 减去一个奇数，那么 k + 1 - x 是一个小于等于 k 的奇数，此时 Bob 占有它，处于必败态，则 Alice 处于必胜态。

综上所述，这个猜想是正确的。

下面是代码实现。

代码

[sol1-C++]
1
2
3
4
5
6
class Solution {
public:
    bool divisorGame(int n) {
        return n % 2 == 0;
    }
};
[sol1-Java]
1
2
3
4
5
class Solution {
    public boolean divisorGame(int n) {
        return n % 2 == 0;
    }
}
[sol1-Golang]
1
2
3
func divisorGame(n int) bool {
    return n % 2 == 0
}
[sol1-C]
1
2
3
bool divisorGame(int n) {
    return n % 2 == 0;
}

复杂度分析

  • 时间复杂度：O(1)。
  • 空间复杂度：O(1)。

方法二：动态规划

思路与算法

在「方法一」中，我们写出了前面几项的答案，在这个过程中我们发现，Alice 处在 n = k 的状态时，他（她）做一步操作，必然使得 Bob 处于 n = m (m < k) 的状态。因此我们只要看是否存在一个 m 是必败的状态，那么 Alice 直接执行对应的操作让当前的数字变成 m，Alice 就必胜了，如果没有任何一个是必败的状态的话，说明 Alice 无论怎么进行操作，最后都会让 Bob 处于必胜的状态，此时 Alice 是必败的。

结合以上我们定义 f[i] 表示当前数字 i 的时候先手是处于必胜态还是必败态，true 表示先手必胜，false 表示先手必败，从前往后递推，根据我们上文的分析，枚举 i 在 (0, i) 中 i 的因数 j，看是否存在 f[i-j] 为必败态即可。

代码如下。

代码

[sol2-C++]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    bool divisorGame(int n) {
        vector<int> f(n + 5, false);

        f[1] = false;
        f[2] = true;
        for (int i = 3; i <= n; ++i) {
            for (int j = 1; j < i; ++j) {
                if (i % j == 0 && !f[i - j]) {
                    f[i] = true;
                    break;
                }
            }
        }

        return f[n];
    }
};
[sol2-Java]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public boolean divisorGame(int n) {
        boolean[] f = new boolean[n + 5];

        f[1] = false;
        f[2] = true;
        for (int i = 3; i <= n; ++i) {
            for (int j = 1; j < i; ++j) {
                if ((i % j) == 0 && !f[i - j]) {
                    f[i] = true;
                    break;
                }
            }
        }

        return f[n];
    }
}
[sol2-Golang]
1
2
3
4
5
6
7
8
9
10
11
12
13
func divisorGame(n int) bool {
    f := make([]bool, n + 5)
    f[1], f[2] = false, true
    for i := 3; i <= n; i++ {
        for j := 1; j < i; j++ {
            if i % j == 0 && !f[i - j] {
                f[i] = true
                break
            }
        }
    }
    return f[n]
}
[sol2-C]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
bool divisorGame(int n) {
    int f[n + 5];
    memset(f, 0, sizeof(f));

    f[1] = false;
    f[2] = true;
    for (int i = 3; i <= n; ++i) {
        for (int j = 1; j < i; ++j) {
            if (i % j == 0 && !f[i - j]) {
                f[i] = true;
                break;
            }
        }
    }

    return f[n];
}

复杂度分析

  • 时间复杂度：O(n^2)。递推的时候一共有 n 个状态要计算，每个状态需要 O(n) 的时间枚举因数，因此总时间复杂度为 O(n^2)。
  • 空间复杂度：O(n)。我们需要 O(n) 的空间存储递推数组 f 的值。
 Comments
On this page
1025-除数博弈