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 解釋：游戲進行如下： - 回合 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 獲勝。

解題思路

因為如果玩家移除石子后，導致 所有已移除石子 的價值 總和 可以被 3 整除，那么該玩家就 輸掉游戲 。所以我們已移除石頭和3的整除關系就可以了，所以我們只需要把石頭分為3類，mod3為0，1，2的三類，稱為mod1，mod2和mod3，mod1和mod2兩類的石頭相加必然會被3整除，而已經移除的石頭總數在移除的過程中是不斷變化狀態的，例如原來是mod1狀態，移除一堆mod1狀態的石頭后，就會轉化為mod2狀態，為了使得不產生mod0狀態，Alice和BOb的最佳拿法必然是
Alice先拿mod1或者mod2，以mod1為例，11212121212，產生12循環，0可以隨意穿插，不影響結果，一旦哪一方不能繼續產生12循環，那方就失敗

代碼

class Solution { public:bool stoneGameIX(vector<int> stones) {vector<int> a(3);for (auto i:stones) a[i%3]++;vector<int> b{a[0],a[2],a[1]};return check(a)|check(b);}bool check(vector<int> a){if (a[1]==0) return false;a[1]--;int t=min(a[1],a[2])*2+1+a[0];if (a[1]>a[2]){a[1]--;t++;}return t%2==1&&a[1]!=a[2];} };

總結

以上是生活随笔為你收集整理的2029. 石子游戏 IX的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。