数据结构
网络
关系数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济学
心理学
社会学
时尚研究
法律研究在 C++ 中最大化 XOR 为零的子数组数量
给定一个包含整数值的数组 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(int arr[], int len) 返回不满足条件 2 的子数组的数量。
将初始计数设置为 0。
使用 for 循环迭代数组并获取变量 sum 和 maxVal。
再使用一个 for 循环迭代 60 个子数组的范围，因为超过 60 后，条件 2 永远不会为假。
将元素添加到 sum 并获取 maxVal 中的最大值。
如果 sum 为偶数且 2 * maxVal > sum，则递增计数，因为条件 2 未满足。
在两个循环结束时返回计数。
函数 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
162 次查看
