在C++中，最大化具有零XOR的子数组的数量- 技术经验 -卓越飞翔博客

在C++中，最大化具有零XOR的子数组的数量

我们得到一个包含整数值的数组 Arr[]。目标是找到 XOR 为 0 的子数组的最大数量。任何子数组的位都可以交换任意次数。

注意：- 1<=Arr[i]<=10¹⁸

为了通过交换位使任意子数组的异或为0，必须满足两个条件：-

< p>如果从左到右范围内的设置位数为偶数。
对于任何给定范围的位数总和 <= 2（设置位中的最大数）

让我们看看各种输入输出场景 -

In −Arr[] = { 1,2,5,4 }

Out −

仅满足第一个条件的子数组：4

满足两个条件的子数组：3

In − Arr[] = { 3,7,2,9 }

Out −

仅满足第一个条件的子数组条件：6

满足两个条件的子数组：3

下面的程序中使用的方法如下 -

在这种方法中，我们观察到为了使通过交换位将任何子数组的 XOR 为 0，必须满足两个条件：- 如果从左到右范围内的设置位数为偶数或对于任何给定范围的位总和 <= 2（设置位中的最大数）

获取输入数组Arr[]并计算其长度。
函数removeSubarr(int arr[], int len) 返回不满足条件 2 的子数组的个数。
将初始计数设为 0。
迭代数组使用 for 循环并采用变量 sum 和 maxVal。
采用另一个 for 循环在 60 个子数组的范围内进行迭代，因为超过 60 个子数组，条件 2 永远不会为 false。
将元素添加到 sum 中，并在 maxVal 中取最大值。
如果 sum 为偶数且 2 * maxVal > sum，则将计数作为条件 2 递增不满足。
两个循环结束时都返回 count。
函数 findSubarrays(int arr1[], int len1) 接受一个输入数组及其长度，并返回满足上述两个条件的子数组的数量。
采用前缀数组来计算仅满足条件 1 的子数组的数量.
使用for循环遍历数组并设置每个元素 __builtin_popcountll(arr1[i]) 这是其中设置的位数。
使用 for 循环填充前缀数组并设置 prefix[i] = prefix[i] + prefix [i - 1] 除第一个元素外的位置。
计算前缀数组中的奇数和偶数值。
设置 tmp1 = ( oddcount * (oddcount-1) )/2 和 tmp2= ( Evencount * (evencount-1) )/2 并将结果作为两者之和。
结果将是仅满足条件 1 的子数组之和。
打印结果。
现在用 result=result 更新结果 - removeSubarr( arr1, len1)。
现在结果包含满足这两个条件的子数组。
再次打印结果。

示例

#include <bits/stdc++.h>
using namespace std;
// Function to count subarrays not satisfying condition 2
int removeSubarr(int arr[], int len){
   int count = 0;
   for (int i = 0; i < len; i++){
      int sum = 0;
      int maxVal = 0;

      for (int j = i; j < min(len, i + 60); j++){
         sum = sum + arr[j];
         maxVal = arr[j] > maxVal ? arr[j]: maxVal;

         if (sum % 2 == 0){
            if( 2 * maxVal > sum)
               { count++; }
         }
      }
   }
   return count;
}
int findSubarrays(int arr1[], int len1){
   int prefix[len1];
   int oddcount, evencount;
   int result;
   for (int i = 0; i < len1; i++)
   { arr1[i] = __builtin_popcountll(arr1[i]); }

   for (int i = 0; i < len1; i++){
      prefix[i] = arr1[i];
      if (i != 0)
         { prefix[i] = prefix[i] + prefix[i - 1]; }
      }
      oddcount = evencount = 0;
      for (int i = 0; i < len1; i++){
         if (prefix[i] % 2 == 0)
            { evencount = evencount +1; }
         else
            { oddcount = oddcount +1; }

      }
      evencount++;
      int tmp1= ( oddcount * (oddcount-1) )/2;
      int tmp2= ( evencount * (evencount-1) )/2;
      result = tmp1+tmp2;
      cout << "Subarrays satisfying only 1st condition : "<<result << endl;
      cout << "Subarrays satisfying both condition : ";
      result = result - removeSubarr(arr1, len1);
      return result;
   }
   int main()
   { int Arr[] = { 1,2,5,4 };
   int length = sizeof(Arr) / sizeof(Arr[0]);
   cout << findSubarrays(Arr, length);
   return 0;
}

输出

如果我们运行上面的代码，它将生成以下输出

Subarrays satisfying only 1st condition : 4
Subarrays satisfying both condition : 3

下面的程序中使用的方法如下 -

示例

输出

相关推荐