Để giải quyết một vấn đề trong đó chúng ta được cung cấp một mảng và một số truy vấn. Bây giờ trong mỗi truy vấn, chúng tôi được cung cấp một phạm vi. Bây giờ chúng ta cần tìm một số sao cho tổng xor của chúng với x là cực đại, chẳng hạn
Input : A = {20, 11, 18, 2, 13}
Three queries as (L, R) pairs
1 3
3 5
2 4
Output : 2147483629
2147483645
2147483645 Trong bài toán này, chúng ta sẽ đếm tiền tố của 1 trong các số ở mỗi vị trí bây giờ vì chúng ta đã tính toán trước số hàng của chúng ta, do đó, để tìm số lượng các đơn vị trong phạm vi đã cho từ L đến R, chúng ta cần trừ được giả định cho đến R với giả định cho đến L.
Phương pháp tiếp cận để tìm giải pháp
Trong cách tiếp cận này, vì chúng ta được yêu cầu phải tìm tổng lớn nhất, vì vậy chúng ta cần làm cho phần lớn các bit của x hoặc bằng 1; do đó chúng tôi kiểm tra xem đối với bất kỳ bit nào nếu một bit nhiều hơn số 0, vì vậy chúng tôi đặt lại bit đó của x vì bây giờ phần lớn số có bit đó bằng 1 vì vậy khi chúng tôi ghép phần lớn số 1 với số 0, vì vậy cuối cùng chúng tôi có phần lớn bit đó bằng 1 do đó đây là cách chúng tôi tối đa hóa câu trả lời của mình.
Ví dụ
Mã C ++ cho phương pháp tiếp cận trên
#include <bits/stdc++.h>
using namespace std;
#define MAX 2147483647 // 2^31 - 1
int prefix[100001][32]; // the prefix array
void prefix_bit(int A[], int n){ // taking prefix count of 1's present
for (int j = 0; j < 32; j++) // we keep 0th count as 0 and our prefix array starts with index 1
prefix[0][j] = 0;
for (int i = 1; i <= n; i++){ // making our prefix array
int a = A[i - 1]; // ith element
for (int j = 0; j < 32; j++){ // as our number is less than 2^32 so we traverse for bit 0 to 31
int x = 1 << j; // traversing in bits
if (a & x) // if this bit is one so we make the prefix count as prevcount + 1
prefix[i][j] = 1 + prefix[i - 1][j];
else
prefix[i][j] = prefix[i - 1][j];
}
}
}
int maximum_num(int l, int r){
int numberofbits = r - l + 1; // the number of elements in the range hence the number of bits
int X = MAX; // we take the max value such that all of it's bits are one
// Iterating over each bit
for (int i = 0; i < 31; i++){
int x = prefix[r][i] - prefix[l - 1][i]; // calculating the number of set bits in the given range
if (x >= numberofbits - x){ // is number of 1's is more than number of 0's
int currentbit = 1 << i; // we set the current bit to prefix for toggling that bit in x
X = X ^ currentbit; // we make toggle that bit from 1 to 0
}
}
return X; // answer
}
int main(){
int n = 5, q = 3; // number of element in our array and number of queries present
int A[] = { 210, 11, 48, 22, 133 }; // elements in our array
int L[] = { 1, 4, 2 }, R[] = { 3, 14, 4 }; // given queries
prefix_bit(A, n); // creating prefix bit array
for (int i = 0; i < q; i++)
cout << maximum_num(L[i], R[i]) << "\n";
return 0;
} Đầu ra
2147483629 2147483647 2147483629
Giải thích về Quy tắc trên
Trong cách tiếp cận này, trước tiên, chúng tôi tính toán số tiền tố của 1 hiện tại cho mỗi bit. Bây giờ khi chúng tôi có được số lượng này, chúng tôi đã giải quyết được vấn đề lớn nhất của mình đó là duyệt các truy vấn. Hiện tại, chúng tôi sẽ không đi qua từng phạm vi. Vì vậy, chúng tôi có thể tính toán điều đó thông qua mảng tiền tố của chúng tôi ngay bây giờ. Logic chính của chúng tôi là chúng tôi tính toán số lần đặt lại và đặt các bit trong phạm vi khi chúng tôi gặp vị trí mà số bit đặt nhiều hơn số bit đặt lại. Do đó, chúng tôi đặt lại bit đó trong x của chúng tôi ngay bây giờ vì chúng tôi đã khởi tạo x với 2 ^ 31 - 1 để tất cả các bit của nó sẽ được đặt và chúng tôi tìm ra câu trả lời của mình bằng cách chuyển đổi các bit trong x.
Kết luận
Trong hướng dẫn này, chúng tôi giải quyết một vấn đề để tìm số có tổng XOR với một phạm vi mảng nhất định là lớn nhất. Chúng tôi cũng đã học chương trình C ++ cho vấn đề này và cách tiếp cận hoàn chỉnh (Bình thường) mà chúng tôi đã giải quyết vấn đề này. Chúng ta có thể viết cùng một chương trình bằng các ngôn ngữ khác như C, java, python và các ngôn ngữ khác. Chúng tôi hy vọng bạn thấy hướng dẫn này hữu ích.