3021. 爱丽丝和鲍勃玩花朵游戏

Medium

题目描述

爱丽丝和鲍勃在一个场地上玩回合制游戏，他们之间有两排花朵。第一排有 x 朵花，第二排有 y 朵花。

游戏规则如下：

• 爱丽丝先手
• 每回合，玩家必须选择其中一排，并从该排中摘取一朵花
• 回合结束时，如果任意一排都没有花朵了，当前玩家就捕获对手并获胜

给定两个整数 n 和 m，任务是计算满足以下条件的可能配对 (x, y) 的数量：

• 根据描述的规则，爱丽丝必须获胜
• 第一排的花朵数量 x 必须在范围 [1,n] 内
• 第二排的花朵数量 y 必须在范围 [1,m] 内

返回满足条件的可能配对 (x, y) 的数量。

示例 1：

输入：n = 3, m = 2
输出：3
解释：以下配对满足条件：(1,2), (3,2), (2,1)

示例 2：

输入：n = 1, m = 1
输出：0
解释：没有配对满足条件

约束：

• 1 <= n, m <= 10^5

提示：

• (x, y) 有效当且仅当它们具有不同的奇偶性

解题思路

解题思路

这是一个数学推理题。关键是理解游戏的获胜条件。

游戏分析：

• 游戏总共有 x + y 朵花
• 爱丽丝先手，所以她在第 1, 3, 5, … 回合行动
• 鲍勃在第 2, 4, 6, … 回合行动
• 摘完最后一朵花的玩家获胜

获胜条件：

• 如果总花朵数 x + y 是奇数，爱丽丝获胜（因为她在奇数回合行动）
• 如果总花朵数 x + y 是偶数，鲍勃获胜

数学转换：

• 爱丽丝获胜 ⟺ x + y 是奇数 ⟺ x 和 y 奇偶性不同
• 即：一个是奇数，另一个是偶数

计数方法：

1. 在 [1, n] 中，奇数有 ⌈n/2⌉ 个，偶数有 ⌊n/2⌋ 个
2. 在 [1, m] 中，奇数有 ⌈m/2⌉ 个，偶数有 ⌊m/2⌋ 个
3. 答案 = (n中奇数个数) × (m中偶数个数) + (n中偶数个数) × (m中奇数个数)

可以简化为：(n * m) / 2，因为恰好一半的组合满足奇偶性不同的条件。

代码实现

class Solution {
public:
    long long flowerGame(int n, int m) {
        return (long long)n * m / 2;
    }
};

class Solution:
    def flowerGame(self, n: int, m: int) -> int:
        return n * m // 2

public class Solution {
    public long FlowerGame(int n, int m) {
        return (long)n * m / 2;
    }
}

var flowerGame = function(n, m) {
    return Math.floor(n * m / 2);
};

复杂度分析