資料結構
網路
關係資料庫管理系統
作業系統
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 次檢視
