做网站收录的网站有哪些,网站建设分金手指排名十一,百度贴吧官网,太原免费自助建站模板2029. 石子游戏 IX
Alice 和 Bob 再次设计了一款新的石子游戏。现有一行 n 个石子#xff0c;每个石子都有一个关联的数字表示它的价值。给你一个整数数组 stones #xff0c;其中 stones[i] 是第 i 个石子的价值。
Alice 和 Bob 轮流进行自己的回合#xff0c;Alice 先手…2029. 石子游戏 IX
Alice 和 Bob 再次设计了一款新的石子游戏。现有一行 n 个石子每个石子都有一个关联的数字表示它的价值。给你一个整数数组 stones 其中 stones[i] 是第 i 个石子的价值。
Alice 和 Bob 轮流进行自己的回合Alice 先手。每一回合玩家需要从 stones 中移除任一石子。
如果玩家移除石子后导致 所有已移除石子 的价值 总和 可以被 3 整除那么该玩家就 输掉游戏 。 如果不满足上一条且移除后没有任何剩余的石子那么 Bob 将会直接获胜即便是在 Alice 的回合。 假设两位玩家均采用 最佳 决策。如果 Alice 获胜返回 true 如果 Bob 获胜返回 false 。
示例 1输入stones [2,1]
输出true
解释游戏进行如下
- 回合 1Alice 可以移除任意一个石子。
- 回合 2Bob 移除剩下的石子。
已移除的石子的值总和为 1 2 3 且可以被 3 整除。因此Bob 输Alice 获胜。示例 2输入stones [2]
输出false
解释Alice 会移除唯一一个石子已移除石子的值总和为 2 。
由于所有石子都已移除且值总和无法被 3 整除Bob 获胜。示例 3输入stones [5,1,2,4,3]
输出false
解释Bob 总会获胜。其中一种可能的游戏进行方式如下
- 回合 1Alice 可以移除值为 1 的第 2 个石子。已移除石子值总和为 1 。
- 回合 2Bob 可以移除值为 3 的第 5 个石子。已移除石子值总和为 1 3 4 。
- 回合 3Alices 可以移除值为 4 的第 4 个石子。已移除石子值总和为 1 3 4 8 。
- 回合 4Bob 可以移除值为 2 的第 3 个石子。已移除石子值总和为 1 3 4 2 10.
- 回合 5Alice 可以移除值为 5 的第 1 个石子。已移除石子值总和为 1 3 4 2 5 15.
Alice 输掉游戏因为已移除石子值总和15可以被 3 整除Bob 获胜。解题思路
因为如果玩家移除石子后导致 所有已移除石子 的价值 总和 可以被 3 整除那么该玩家就 输掉游戏 。所以我们已移除石头和3的整除关系就可以了所以我们只需要把石头分为3类mod3为012的三类称为mod1mod2和mod3mod1和mod2两类的石头相加必然会被3整除而已经移除的石头总数在移除的过程中是不断变化状态的例如原来是mod1状态移除一堆mod1状态的石头后就会转化为mod2状态为了使得不产生mod0状态Alice和BOb的最佳拿法必然是 Alice先拿mod1或者mod2以mod1为例11212121212产生12循环0可以随意穿插不影响结果一旦哪一方不能继续产生12循环那方就失败
代码
class Solution {
public:bool stoneGameIX(vectorint stones) {vectorint a(3);for (auto i:stones) a[i%3];vectorint b{a[0],a[2],a[1]};return check(a)|check(b);}bool check(vectorint a){if (a[1]0) return false;a[1]--;int tmin(a[1],a[2])*21a[0];if (a[1]a[2]){a[1]--;t;}return t%21a[1]!a[2];}
};
