• 首页 首页 icon
  • 工具库 工具库 icon
    • IP查询 IP查询 icon
  • 内容库 内容库 icon
    • 快讯库 快讯库 icon
    • 精品库 精品库 icon
    • 问答库 问答库 icon
  • 更多 更多 icon
    • 服务条款 服务条款 icon

[每日一题]138石子游戏 IX

武飞扬头像
AngelDg
帮助1


题目描述

Alice 和 Bob 再次设计了一款新的石子游戏。现有一行 n 个石子,每个石子都有一个关联的数字表示它的价值。给你一个整数数组 stones ,其中 stones[i] 是第 i 个石子的价值。

Alice 和 Bob 轮流进行自己的回合,Alice 先手。每一回合,玩家需要从 stones 中移除任一石子。

如果玩家移除石子后,导致 所有移除石子 的价值 总和 可以被 3 整除,那么该玩家就 输掉游戏
如果不满足上一条,且移除后没有任何剩余的石子,那么 Bob 将会直接获胜(即便是在 Alice 的回合)。

假设两位玩家均采用 最佳 决策。如果 Alice 获胜,返回 true ;如果 Bob 获胜,返回 false 。

示例 1:

输入:stones = [2,1]
输出:true
解释:游戏进行如下:
- 回合 1:Alice 可以移除任意一个石子。
- 回合 2:Bob 移除剩下的石子。 
已移除的石子的值总和为 1   2 = 3 且可以被 3 整除。因此,Bob 输,Alice 获胜。

示例 2:

输入:stones = [2]
输出:false
解释:Alice 会移除唯一个一个地个石子,已移除石子的值总和为 2 。 
由于所有石子都已移除,且值总和无法被 3 整除,Bob 获胜。

示例 3:

输入:stones = [5,1,2,4,3]
输出:false
解释:Bob 总会获胜。其中一种可能的游戏进行方式如下:
- 回合 1:Alice 可以移除值为 1 的第 2 个石子。已移除石子值总和为 1 。
- 回合 2:Bob 可以移除值为 3 的第 5 个石子。已移除石子值总和为 = 1   3 = 4 。
- 回合 3:Alices 可以移除值为 4 的第 4 个石子。已移除石子值总和为 = 1   3   4 = 8 。
- 回合 4:Bob 可以移除值为 2 的第 3 个石子。已移除石子值总和为 = 1   3   4   2 = 10.
- 回合 5:Alice 可以移除值为 5 的第 1 个石子。已移除石子值总和为 = 1   3   4   2   5 = 15.
Alice 输掉游戏,因为已移除石子值总和(15)可以被 3 整除,Bob 获胜。

提示:

  • 1 <= stones.length <= 105
  • 1 <= stones[i] <= 104

题解思路

方法一:构造

由于玩家的目标是使得已经被移除的石子的价值总和不是 3 的倍数,因此我们可以把石子分成三类,它们的价值除以 3 的余数分别为 0, 1, 2。我们可以直接用 0, 1, 2 代表它们的价值,对应的石子数量分别为 cnt_0, cnt_1, cnt_2。

可以发现,移除类型 0 的石子并不会对总和产生影响,因此类型 0 的石子可以看成是「先后手」交换。具体地,例如当前是 Alice 在进行操作,它发现如果自己选择移除类型 1 或 2 的石子,那么她在最后一定不能获胜。这时它就可以选择移除一个类型 0 的石子,将同样的局面交给 Bob。如果类型 0 的石子还没有移除完,那么 Bob 同样可以通过移除一个类型 0 的石子将局面重新交给 Alice。这样不断地往复下去,我们可以得到结论:

  • 如果类型 0 的石子的个数为 偶数,那么胜负情况等价于没有类型 0 的石子的胜负情况;
  • 如果类型 0 的石子个数为 奇数,那么胜负情况等价于只有 1 个类型 0 的石子的胜负情况。注意这里不能单纯地等价于「没有类型 0 的石子的胜负情况」的相反情况,这是因为如果所有的石子都被移除完,无论谁移除了最后一个石子,都算 Alice 输。因此如果 Alice 发现自己选择移除类型 1 或 2 的石子不能获胜,于是选择移除类型 0 的石子,并且它不能获胜的原因是「石子会移除完」,那么 Alice 仍然会输。

将类型 0 的石子考虑完全之后,我们就还剩下类型 1 和 2 的石子了。可以发现,为了保证移除石子的和不为 3 的倍数,操作顺序只有可能为下面的两种情况:

  • 如果 Alice 首先移除类型 1 的石子,那么 Bob 只能移除类型 1 的石子,在这之后 Alice 只能移除类型 2 的石子,Bob 同样只能移除类型 1 的石子。以此类推,移除石子的类型序列为:

1121212121 ⋯ 1121212121⋯ 1121212121

  • 如果 Alice 首先移除类型 2 的石子,我们可以类似得到移除石子的类型序列为:

2212121212 ⋯ 2212121212⋯ 2212121212

作为先手的 Alice 可以在二者中选择一个序列。例如 Alice 选择第一种,那么 Bob 永远移除类型 1 的石子,Alice 除了第一步移除类型 1 的石子之外,后续永远移除类型 2 的石子。因此 Alice 可以获胜当且仅当:

  • 类型 1 的石子恰好有 1 个,并且类型 2 的石子至少有 1 个。此时 Alice 在 Bob 完成第一步时获胜;

  • 类型 1 的石子至少有 2 个,并且不能比类型 2 的石子多:

    • 如果多 1 个,那么在 Alice 移除最后一个类型 2 的石子后,所有的石子都被移除,Bob 获胜;
    • 如果多 2 个,那么在 Bob 移除最后一个类型 1 的石子后,所有的石子都被移除,Bob 获胜;
    • 如果多超过 2 个,那么 Alice 会在某一步没有类型 2 的石子可以移除,Bob 获胜;
    • 如果一样多或类型 2 的石子更多,那么 Bob 会在某一步没有类型 1 的石子可以移除,Alice 获胜。

上面的两个条件可以归纳为同一个条件,即有类型 1 的石子,并且不能比类型 2 的石子多。

同理,如果 Alice 选择第二种,那么她获胜当且仅当有类型 2 的石子,并且不能比类型 1 的石子多。

上述的两种情况也可以归纳为同一种情况,即类型 1 和类型 2 的石子至少都有 1 个。

细节

回到前面关于类型 0 石子的讨论,可以得到 Alice 获胜的条件:

  • 如果类型 0 的石子的个数为偶数,那么 Alice 获胜当且仅当类型 1 和类型 2 的石子至少都有 1 个;
  • 如果类型 0 的石子的个数为奇数,那么 Alice 获胜当且仅当「在没有类型 0 石子的情况下,Bob 获胜且原因不是因为所有石子都被移除」。对应到上面的分析即为「类型 1 的石子比类型 2 多超过 2 个」或者「类型 2 的石子比类型 1 多超过 2 个」。

代码如下:

class Solution {
public:
    bool stoneGameIX(vector<int>& stones) {
        int cnt_0 = 0, cnt_1 = 0, cnt_2 = 0;
        for (int i = 0; i < stones.size();   i) {
            int num = stones[i] % 3;
            if (num == 0) {
                  cnt_0;
            }
            else if (num == 1) {
                  cnt_1;
            }
            else if (num == 2) {
                  cnt_2;
            }
        }

        if (cnt_0 % 2 == 0) {
            return cnt_1 >= 1 && cnt_2>= 1;
        }
        return cnt_1 - cnt_2 > 2 || cnt_2 - cnt_1 > 2;
    }
};
学新通

方法二:精简

  • 最终的和是对3取余,因此每个石头的价值可以对3取余后替代;
  • 不考虑0的情况时所取石子的序列有两种情况112121212…和221212121…。0可以插入在任意非首位的位置

当s[0]为偶数时,在所有的0取完后,最终Alice和bob的顺序均不会发生改变。

  • 若1或2个数为零,要么石头能取完,要么按序列111或222,Alice会拿到3的倍数也会输;
  • 若均不为零时,Alice先取少的一个则必赢,相等时取任一个均能赢。

相反当s[0]为奇数时,最终Alice和bob的顺序会调换,调换过程可以简单理解为alice需要在开头连续取两个价值一样的石子。Alice先取少则必输,故在Alice取两个多后序列变为少多少多。

  • 故当s[1]和s[2]个数相差大于2时,Alice先取多的一个则必赢;
  • 当s[1]和s[2]个数相差小于等于2时,等于2则能取完,小于2则alice所取值会先完。

代码如下:

class Solution {
public:
    bool stoneGameIX(vector<int>& stones) {
        int s[3] = {0, 0, 0};
        for (int i : stones)   s[i % 3];	 // 模 3 预处理
        if (s[0] % 2 == 0) return s[1] != 0 && s[2] != 0;	// 偶数个,相当于没3,如果有1,2A必赢,选定1或2中一个后,后续的保证不输的序列是固定的,哪个能赢用哪个,前提是有1,2可选
        return s[2] > s[1]   2 || s[1] > s[2]   2;		// 奇数个,相当于可以颠倒先后手,前提是个数够颠倒,成对的1,2可以相互抵消。如果剩余的足够颠倒,A可以在1,2中选择必赢策略。
    }
};

这篇好文章是转载于:学新通技术网

  • 版权申明: 本站部分内容来自互联网,仅供学习及演示用,请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系,请提供相关证据及您的身份证明,我们将在收到邮件后48小时内删除。
  • 本站站名: 学新通技术网
  • 本文地址: /boutique/detail/tanhggbchi
系列文章
更多 icon
同类精品
更多 icon
继续加载