使用 C++ 查找与给定数组范围进行 XOR 运算后总和最大的数字

c++server side programmingprogramming

为了解决给定数组和一些查询的问题。现在，在每个查询中，我们都会给出一个范围。现在我们需要找到一个数字，使得它们与 x 的异或之和最大化，例如

输入:A = {20, 11, 18, 2, 13}
三个查询作为 (L, R) 对
1 3
3 5
2 4
输出:2147483629
2147483645
2147483645

在这个问题中，我们现在要取每个位置数字中存在的 1 的前缀计数，因为我们已经预先计算了 1 的数量，因此为了找到从 L 到 R 的给定范围内的 1 的数量，我们需要用 presumed till R 减去 presumed till L。

寻找解决方案的方法

在这种方法中，因为我们需要找到最大和，所以我们需要xor 的大多数位等于 1;因此我们检查任何位是否大于 0 的数量，所以我们重置 x 的该位，因为现在大多数数字的该位等于 1，所以当我们将大多数 1 与 0 配对时，最终我们会得到该位的大多数等于 1，这就是我们最大化答案的方法。

示例

上述方法的 C++ 代码

#include <bits/stdc++.h>
using namespace std;
#define MAX 2147483647 // 2^31 - 1
int prefix[100001][32]; // 前缀数组
void prefix_bit(int A[], int n){ // 取当前前缀中 1 的计数
    for (int j = 0; j < 32; j++) // 我们将第 0 个计数保留为 0，并且我们的前缀数组从索引 1 开始
        prefix[0][j] = 0;
    for (int i = 1; i <= n; i++){ // 制作我们的前缀数组
        int a = A[i - 1]; // 第 i 个元素
        for (int j = 0; j < 32; j++){ // 因为我们的数字小于 2^32，所以我们遍历位 0 到 31
            int x = 1 << j; // 按位遍历
            if (a & x) // 如果此位为 1，则我们将前缀计数为 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; // 范围内元素的数量，因此位数
    int X = MAX; // 我们取最大值，使得它的所有位都是 1
    // 迭代每个位
    for (int i = 0; i < 31; i++){
        int x = prefix[r][i] - prefix[l - 1][i]; // 计算给定范围内的设置位数
        if (x >= numberofbits - x){ // 1 的数量大于 0 的数量
            int currentbit = 1 << i; // 我们将当前位设置为前缀，以在 x 中切换该位
            X = X ^ currentbit; // 我们将该位从 1 切换到 0
        }
    }
    return X; // answer
}
int main(){
    int n = 5, q = 3; // 数组中元素的数量和存在的查询数量
    int A[] = { 210, 11, 48, 22, 133 }; // 数组中的元素
    int L[] = { 1, 4, 2 }, R[] = { 3, 14, 4 }; // 给定查询
    prefix_bit(A, n); // 创建前缀位数组
    for (int i = 0; i < q; i++)
        cout << maximum_num(L[i], R[i]) << "\n";
    return 0;
}

输出

2147483629
2147483647
2147483629

上述代码的解释

在这种方法中，我们首先计算每个位中存在的 1 的前缀计数。现在，当我们得到这个计数时，我们已经解决了遍历查询的最大问题。截至目前，我们不会遍历每个范围。所以我们现在可以通过前缀数组来计算。我们的主要逻辑是，当我们遇到设置位数大于重置位数的位置时，我们计算范围内的重置和设置位数。因此，我们现在重置 x 中的该位，因为我们已经用 2^31 - 1 初始化了 x，所以它的所有位都将被设置，我们通过切换 x 中的位来找到答案。