C++ では、ゼロ XOR を使用してサブ配列の数を最大化します。

整数値を含む配列 Arr[] を取得します。目標は、XOR が 0 であるサブ配列の最大数を見つけることです。サブ配列のビットは何度でも交換できます。

注:- 118

ビットを交換してサブ配列の XOR を 0 にするには、2 つの条件を満たす必要があります:-

• 左から右の範囲の設定桁数が偶数の場合。
• #任意の範囲のビットの合計については、

さまざまな入出力シナリオを見てみましょう -

#In

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

Out

−最初の条件を満たすサブ配列のみ: 4

2 つの条件を満たすサブ配列: 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 になることはありません。

• 合計する要素を追加し、maxVal の最大値を取得します。

• 合計が偶数で、2 * maxVal > 合計の場合、条件 2 としてのカウントの増加は満たされません。

• 両方のループは最後に count を返します。

• 関数 findSubarrays(int arr1[], int len1) は、入力配列とその長さを受け入れ、上記の 2 つの条件を満たすサブ配列の数を返します。

• プレフィックス配列を使用して、条件 1 のみを満たすサブ配列の数を数えます。

• for ループを使用して配列を走査し、設定します。それぞれの要素 __builtin_popcountll(arr1[i]) これは、それに設定されているビット数です。

• for ループを使用してプレフィックス配列を設定し、最初の要素を除いて prefix[i] = prefix[i] prefix [i - 1] を設定します。

• プレフィックス配列の奇数と偶数の値を計算します。

• tmp1 = ( oddcount * (oddcount-1) )/2 および tmp2= ( Evencount * (evencount-1) )/2 を設定し、結果を 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 中国語 Web サイトの他の関連記事を参照してください。