admin管理员组文章数量:1621657
Alice 和 Bob 再次设计了一款新的石子游戏。现有一行 n 个石子,每个石子都有一个关联的数字表示它的价值。
给你一个整数数组 stones ,其中 stones[i] 是第 i 个石子的价值。Alice 和 Bob 轮流进行自己的回合,Alice 先手。
每一回合,玩家需要从 stones 中移除任一石子。
1.如果玩家移除石子后,导致 所有已移除石子 的价值 总和 可以被 3 整除,那么该玩家就 输掉游戏 。
2.如果不满足上一条,且移除后没有任何剩余的石子,那么 Bob 将会直接获胜(即便是在 Alice 的回合)。
假设两位玩家均采用 最佳 决策。如果 Alice 获胜,返回 true ;如果 Bob 获胜,返回 false。
易知Alice只有“在Bob移除石子后,导致所有已移除石子的价值的总和可以被3整除”的情况下获胜。
对数组stones的每一个数取模,即可得到A、B、C(分别代表1、2、0的个数)
情况1:A+B+C=1,Bob-->win
情况2:A+B=0,Bob-->win
情况3:C=2N(N自然数)
Alice的选择(1or2)决定了游戏的动向(由于C为偶数,故C对游戏的动向没有影响)
只考虑Alice-->win的情况
即偶数位导致的“在Bob移除石子后,导致所有已移除石子的价值的总和可以被3整除”
以1为例(若以2为例,把数值1与数值2、A与B调换位置即可):
(1)A=1&&B>=1
1-2
(2)B>A-2&&A>=2&&B>1
1-1-{N*[2-1]}-2-2
情况3:C=2N+1(N自然数)
Alice的选择(1or2)决定了游戏的动向(由于C为奇数数,故C对游戏的动向产生了影响,为出手顺序的转换)
只考虑Alice-->win的情况
即奇数位(大于1的奇数位)导致的“在Bob移除石子后,导致所有已移除石子的价值的总和可以被3整除”
给出例子来解释:
数组{0,0,0,1,1,2,2,2,2,2}
一:
1-1-2-2(C=2N情况下,Alice-->win)
1-{N1*[0]}-1-{N2*[0]}-2-{N3*[0]}-2
(由于C!=2N且Bob同为超级计算机,势必造成N1+N2+N3=2k+1,k=0,1,2,...)
因此末尾的2实际上的位数为奇数。
二:
2-2-1-2-1-2-2(C=2N情况下,Alice-->fail)
2-{N1*[0]}-2-{N2*[0]}-1-{N3*[0]}-2-{N4*[0]}-1-{N5*[0]}-2-{N6*[0]}-2
(由于C!=2N且Alice同为超级计算机,势必造成N1+N2+N3+N4+N5+N6=2k+1,k=0,1,2,...)
因此末尾的2实际上的位数为偶数。
以1为例(若以2为例,把数值1与数值2、A与B调换位置即可):
B>A-2
1-1-2-1-2-1-1
对于C=2N(N为自然数)的情况仍然存在2个测试点没过
代码如下:
class Solution {
public:
bool stoneGameIX(vector<int>& stones) {
bool Awin=true,Bwin=false;
if(stones.size()==1){
return Bwin;
}
vector<int>cnt(3,0);
for(int stone:stones){
cnt[stone%3]++;
}
if(cnt[1]==0&&cnt[2]==0) return Bwin;
else if(cnt[0]%2==0){
if(cnt[2]>cnt[1]-2&&cnt[1]>=2&&cnt[2]>1)return Awin;
else if(cnt[1]>cnt[2]-2&&cnt[2]>=2&&cnt[1]>1)return Awin;
else if((cnt[1]=1&&cnt[2]>=1)||(cnt[2]=1&&cnt[1]>=1))return Awin;
else return Bwin;
}
else{
if(cnt[1]-2>cnt[2]) return Awin;
if(cnt[2]-2>cnt[1]) return Awin;
return Bwin;
}
}
};
版权声明:本文标题:2029. 石子游戏 IX 内容由热心网友自发贡献,该文观点仅代表作者本人, 转载请联系作者并注明出处:https://www.elefans.com/xitong/1728850809a1176654.html, 本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容,一经查实,本站将立刻删除。
发表评论