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 khác. Xét hai người chơi đang chơi trò chơi. Chúng được đánh số 0 và 1. Có một biến x giá trị ban đầu là 0. Trò chơi có N vòng. Ở vòng thứ i, người S[i] làm một trong sau: thay x bằng x XOR A[i], hoặc không làm gì. Người 0 muốn 0 ở cuối trò chơi 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í dụ, nếu đầu vào là A = [1, 2]; S = "10", thì đầu ra sẽ là 1, vì người 1 thay x bằng 0 XOR 1 = 1, nên nó luôn là 1 bất kể lựa chọn của người 0.
Các bước
Để giải quyết bài toán này, chúng ta sẽ làm theo các bước sau:
N := kích thước của A Định nghĩa mảng judge kích thước: 60. z := 0 điền judge với 0 for khởi tạo n := N - 1, khi 0 <= n, cập nhật (giảm n đi 1), do: x := A[n] lặp vô điều kiện, do: if x giống 0, thì: Thoát khỏi vòng lặp y := x I := -1 for khởi tạo i := 0, khi i < 60, cập nhật (tăng i lên 1), do: if y mod 2 giống 1, thì: I := i y := y / 2 if judge[I] giống 0, thì: judge[I] := x Thoát khỏi vòng lặp x := x XOR judge[I] if S[n] không bằng '0', thì: if x không bằng 0, thì: z := 1 return z
Ví dụ
Xem 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