在C++中，最大化具有零XOR的子數組的數量

我們得到一個包含整數值的陣列 Arr[]。目標是找到 XOR 為 0 的子數組的最大數量。任何子數組的位元都可以交換任意次數。

注意：- 118

為了透過交換位元使任意子陣列的異或為0，必須滿足兩個條件：-

• 如果從左到右範圍內的設定位數為偶數。

• 對於任何給定範圍的位元總和

#讓我們看看各種輸入輸出場景-

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

#Out −

只滿足第一個條件的子陣列： 4

滿足兩個條件的子陣列：3

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

Out −

只滿足第一個條件的子數組條件：6

在滿足兩個條件的子數組：3

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

在這種方法中，我們觀察到為了使透過交換位將任何子數組的XOR 為0，必須滿足兩個條件：- 如果從左到右範圍內的設置位數為偶數或對於任何給定範圍的位元總和

• 取得輸入數組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

#

以上是在C++中，最大化具有零XOR的子數組的數量的詳細內容。更多資訊請關注PHP中文網其他相關文章！