xorゲームの結果を0かどうかをチェックするC++プログラム

N個の要素と別のバイナリ文字列Sを持つ配列Aがあるとします。2人のプレーヤーがゲームをプレイしていると考えてください。それらは0と1として番号が付けられます。初期値が0である1つの変数xがあります。ゲームにはNラウンドがあります。 i番目のラウンドの人S[i]は、次のいずれかを実行します。xをx XOR A [i]に置き換えます。それ以外の場合は、何もしません。人物0は、このゲームの終了時に0を望んでいますが、人物1はゼロ以外を望んでいます。最後にxが0になるかどうかを確認する必要があります。

したがって、入力がA =[1、2]のような場合。 S ="10"の場合、person1はxを0 XOR 1 =1に変更するため、出力は1になります。したがって、person0による選択に関係なく、常に1になります。

ステップ

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

N := size of A
Define an array judge of size: 60.
z := 0
fill judge with 0
for initialize n := N - 1, when 0 <= n, update (decrease n by 1), do:
   x := A[n]
   loop through the following unconditionally, do:
      if x is same as 0, then:
         Come out from the loop
      y := x
      I := -1
      for initialize i := 0, when i < 60, update (increase i by 1), do:
         if y mod 2 is same as 1, then:
            I := i
         y := y / 2
      if judge[I] is same as 0, then:
         judge[I] := x
         Come out from the loop
      x := x XOR judge[I]
   if S[n] is not equal to '0', then:
      if x is not equal to 0, then:
         z := 1
return z

例

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

#include <bits/stdc++.h>
using namespace std;

int solve(vector<int> A, string S){
   int N = A.size();
   int judge[60];
   int z = 0;
   fill(judge, judge + 60, 0);
   for (int n = N - 1; 0 <= n; n--){
      int x = A[n];
      while (1){
         if (x == 0)
            break;
         int y = x;
         int I = -1;
         for (int i = 0; i < 60; i++){
            if (y % 2 == 1)
               I = i;
               y /= 2;
         }
         if (judge[I] == 0){
            judge[I] = x;
            break;
         }
         x ^= judge[I];
      }
      if (S[n] != '0'){
         if (x != 0)
            z = 1;
      }
   }
   return z;
}
int main(){
   vector<int> A = { 1, 2 };
   string S = "10";
   cout << solve(A, S) << endl;
}

入力

{ 1, 2 }, "10"

出力

1