Chương trình C ++ để kiểm tra kết quả trò chơi xor 0 hay không

Giả sử chúng ta có một mảng A với N phần tử và một chuỗi nhị phân S. Coi hai người chơi đang chơi một trò chơi. Chúng được đánh số là 0 và 1. Có một biến x có giá trị ban đầu là 0. Trò chơi có N vòng. Ở vòng thứ i, người S [i] thực hiện một trong những điều sau:thay x bằng x XOR A [i], nếu không thì không làm gì cả. Người 0 muốn 0 ở cuối trò chơi này nhưng người 1 muốn khác 0. Chúng ta phải kiểm tra xem x có trở thành 0 ở cuối hay không.

Vì vậy, nếu đầu vào giống như A =[1, 2]; S ="10", thì đầu ra sẽ là 1, bởi vì person1 thay đổi x bằng 0 XOR 1 =1, vì vậy nó sẽ luôn là 1 bất kể lựa chọn của người0.

Các bước

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

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

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

#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;
}

Đầu vào

{ 1, 2 }, "10"

Đầu ra

1