C++中异或为零的子数组数量最大化
我们得到一个包含整数值的数组Arr[]。目标是找到XOR为0的最大子数组数。任何子数组的位都可以交换任意次数。
注意：-1<=Arr[i]<=1018
为了通过交换位使任何子阵列的XOR为0，必须满足两个条件：-
如果从左到右范围内的设置位数为偶数。
对于任何给定范围的位总和<=2（设置位中的最大数）
让我们看看这个的各种输入输出场景-
在 -Arr[]={1,2,5,4}
出 -
仅满足第一个条件的子数组：4
满足两个条件的子数组：3
在 -Arr[]={3,7,2,9}
出 -
仅满足第一个条件的子数组：6
满足两个条件的子数组：3
以下程序中使用的方法如下-
在这种方法中，我们观察到，为了通过交换位使任何子阵列的XOR为0，必须满足两个条件：-如果从左到右范围内的设置位数量是偶数或对于任何给定范围的位总和<=2（设置位中的最大数）
取输入数组Arr[]并计算其长度。
函数removeSubarr(intarr[],intlen)返回不满足条件2的子数组的数量。
取初始计数为0。
使用for循环迭代数组并取变量sum和maxVal。
使用另一个for循环在60个子数组的范围内进行迭代，因为超过60个，条件2永远不会为假。
将元素添加到sum并在maxVal中取最大值。
如果sum为偶数且2*maxVal>sum则增加count作为条件2不满足。
在两个循环结束时返回计数。
函数findSubarrays(intarr1[],intlen1)接受一个输入数组及其长度，并返回满足上述两个条件的子数组的计数。
取一个前缀数组来计算仅遵循条件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;
//计算不满足条件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 << "仅满足第一个条件的子数组： "<<result << endl;
cout << "满足两个条件的子数组： ";
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;
}输出结果如果我们运行上面的代码，它将生成以下输出
仅满足第一个条件的子数组： 4 满足两个条件的子数组： 3