Trong bài toán này, chúng ta được cung cấp một ma trận N x N và một số truy vấn, mỗi truy vấn chứa góc trên cùng bên trái và dưới cùng bên phải của ma trận con được tạo từ ma trận này. Nhiệm vụ của chúng ta là tìm XOR của tất cả các phần tử của submatrix được xác định bởi các truy vấn.
Hãy lấy một ví dụ để hiểu vấn đề,
Đầu vào
arr[][] = {{1, 2, 3}
{4, 5, 6}
{7, 8, 9}}
Querries: {0,0, 1,2} , {1, 2, 2, 2} Đầu ra
1 15
Giải thích
querry 1 : 1^2^3^4^5^6 querry 2 : 6^9
Để giải quyết vấn đề này, chúng tôi sẽ tìm một ma trận tiền tố-XOR để giải quyết các truy vấn. Giá trị của ma trận ở vị trí (R, C) là XOR của ma trận con từ góc trên bên trái (0, 0) và góc dưới bên phải ở vị trí (R, C).
Trước tiên, chúng tôi sẽ tìm thấy tiền tố -XOR cho tất cả các hàng của ma trận từng hàng một. Sau đó, tính toán tiền tố XOR cho từng cột một.
Để tìm XOR của ma trận con cho một truy vấn được cung cấp bởi (r1, c1) cho (r2, c2) được tính bằng prefixXor [r2] [c2] ^ prefixXor [r1-1] [c2] ^ prefixXor [r2] [c1 -1] ^ prefixXor [r1-1] [c1-1].
Chương trình cho thấy việc triển khai giải pháp của chúng tôi,
Ví dụ
#include <iostream>
using namespace std;
#define n 3
void preXOR(int arr[][n], int prefix_xor[][n]) {
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++) {
if (j == 0)
prefix_xor[i][j] = arr[i][j];
else
prefix_xor[i][j]
= (prefix_xor[i][j - 1] ^ arr[i][j]);
}
for (int i = 0; i < n; i++)
for (int j = 1; j < n; j++)
prefix_xor[j][i]
= (prefix_xor[j - 1][i] ^ prefix_xor[j][i]);
}
int XORSubMatrix(int prefix_xor[][n], int querry[2]) {
int xor_1 = 0, xor_2 = 0, xor_3 = 0;
if (querry[0] != 0)
xor_1 = prefix_xor[querry[0] - 1][querry[3]];
if (querry[1] != 0)
xor_2 = prefix_xor[querry[2]][querry[1] - 1];
if (querry[2] != 0 and querry[1] != 0)
xor_3 = prefix_xor[querry[0] - 1][querry[1] - 1];
return ((prefix_xor[querry[2]][querry[3]] ^ xor_1) ^ (xor_2 ^ xor_3));
}
int main() {
int arr[][n] = { { 1, 2, 3 },
{ 4, 5, 6 },
{ 7, 8, 9 } };
int prefix_xor[n][n];
preXOR(arr, prefix_xor);
int querry1[] = {0,0, 2,2} ;
int querry2[] = {1,2, 2,2} ;
cout<<"The XOR of submatrix created by querries :\n";
cout<<"Querry 1 : "<<XORSubMatrix(prefix_xor, querry1)<<endl;
cout<<"Querry 2 : "<<XORSubMatrix(prefix_xor, querry2)<<endl;
return 0;
} Đầu ra
Querry 1 : 1 Querry 2 : 15