xor 게임 결과 0을 확인하는 C++ 프로그램

N개의 요소가 있는 배열 A와 다른 이진 문자열 S가 있다고 가정합니다. 두 명의 플레이어가 게임을 하고 있다고 가정합니다. 0과 1로 번호가 매겨집니다. 초기 값이 0인 변수 x가 하나 있습니다. 게임에는 N 라운드가 있습니다. i번째 라운드 사람 S[i]는 다음 중 하나를 수행합니다. x를 x XOR A[i]로 교체하고, 그렇지 않으면 아무 것도 하지 않습니다. 사람 0은 이 게임이 끝날 때 0을 원하지만 사람 1은 0이 아닌 것을 원합니다. x가 마지막에 0이 되는지 여부를 확인해야 합니다.

따라서 입력이 A =[1, 2]와 같으면; S ="10"이면 출력은 1이 됩니다. 왜냐하면 person1은 x를 0 XOR 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