資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會學
時尚學
法律學C++ 中子矩陣查詢的異或
在這個問題中，我們給定了一個 N x N 矩陣和一些查詢，每個查詢包含用該矩陣建立的子矩陣的左上角和右下角。我們的任務是找到這裡查詢所定義的子矩陣中所有元素的異或。
舉一個例子來理解此問題：
輸入
arr[][] = {{1, 2, 3}
{4, 5, 6}
{7, 8, 9}}
Querries: {0,0, 1,2} , {1, 2, 2, 2}輸出
1 15
解釋
querry 1 : 1^2^3^4^5^6 querry 2 : 6^9
為了解決此問題，我們將找到一個字首異或矩陣來解決查詢。矩陣在位置 (R, C) 的值是左上角 (0, 0) 和右下角在位置 (R, C) 的子矩陣的異或。
我們首先找到矩陣所有行的異或字首。然後逐一計算每一列的字首異或。
對於查詢給出 (r1, c1) 到 (r2, c2) 的子矩陣的異或使用 prefixXor[r2][c2] ^ prefixXor[r1-1][c2] ^ prefixXor[r2][c1-1] ^ prefixXor[r1-1][c1-1] 計算。
展示解決方案實現的程式：
示例
#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;
}輸出
Querry 1 : 1 Querry 2 : 15
更新時間：2020-04-17
106 瀏覽
廣告