Giả sử chúng ta có một mảng được sắp xếp trước gọi là nums có kích thước n và cũng có một giá trị b. Chúng ta muốn thực hiện truy vấn sau n lần -
-
Tìm kiếm giá trị không âm k <2 ^ m sao cho XOR của tất cả các phần tử ở dạng num và k được tối đa hóa. Vậy k là câu trả lời cho truy vấn thứ i.
-
Xóa phần tử cuối cùng khỏi số mảng hiện tại.
-
Chúng ta phải tìm một câu trả lời mảng, trong đó answer [i] là câu trả lời cho truy vấn thứ i.
Vì vậy, nếu đầu vào giống như nums =[0,1,1,3], m =2, thì đầu ra sẽ là [0,3,2,3], bởi vì
-
nums =[0,1,1,3], k =0 vì 0 XOR 1 XOR 1 XOR 3 XOR 0 =3.
-
nums =[0,1,1], k =3 vì 0 XOR 1 XOR 1 XOR 3 =3.
-
nums =[0,1], k =2 vì 0 XOR 1 XOR 2 =3.
-
nums =[0], k =3 vì 0 XOR 3 =3.
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
-
x:=2 ^ m - 1
-
đối với tôi trong phạm vi từ 0 đến kích thước của nums - 1, thực hiện
-
nums [i]:=nums [i] XOR x
-
x:=nums [i]
-
-
trả về số sau khi đảo ngược
Ví dụ
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
def solve(nums, m):
x=2**m-1
for i in range(len(nums)):
nums[i]^= x
x = nums[i]
return(nums[::-1])
nums = [0,1,1,3]
m = 2
print(solve(nums, m))
Đầu vào
[0,1,1,3], 2
Đầu ra
[0, 3, 2, 3]