C++での黒板XORゲーム

numsという配列があり、nums[i]が黒板に書かれているとします。ラムとサムは交代で黒板から正確に1つの要素を消去し、ラムが最初に開始します。数字を消去すると、黒板のすべての要素のビット単位のXORが0になる場合、そのプレーヤーは負けます。 1つの要素のビット単位のXORはその要素自体であり、要素のないビット単位のXORは0です。いずれかのプレーヤーが黒板のすべての要素のビット単位のXORが0に等しい状態でターンを開始すると、そのプレーヤーが勝ちます。配列が[1、2、1]を保持しているとすると、Ramは1または2を削除できます。Ramが1を削除すると、配列は[2,1]になります。これは、要素1のXOR XOR 2 =3であり、Samはすべての要素を削除します。これは、Ramが最後の要素を消去するものであり、彼が失うためです。最初に2を削除することを選択した場合、配列は[1,1]になり、XORは0になるため、Ramは失われます。

これを解決するには、次の手順に従います-

• n：=numsのサイズ
• x：=0
• すべての要素iのnums-
  • x：=x XOR i
• return xは0と同じか、nmod2は0です

理解を深めるために、次の実装を見てみましょう-

例

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
   bool xorGame(vector<int>& nums) {
      int n = nums.size();
      int x = 0;
      for(int i : nums) x ^= i;
      return x == 0 || n % 2 == 0;
   }
};
main(){
   Solution ob;
   vector<int> v = {1,2,1};
   cout << (ob.xorGame(v));
}

入力

{1,2,1}

出力

0