Maximieren Sie in C++ die Anzahl der Subarrays mit null XOR

Wir erhalten ein Array Arr[] mit ganzzahligen Werten. Das Ziel besteht darin, die maximale Anzahl von Subarrays zu finden, deren XOR 0 ist. Die Bits eines Subarrays können beliebig oft ausgetauscht werden.

Hinweis: - 118

Um das XOR eines beliebigen Subarrays durch Vertauschen von Bits auf 0 zu setzen, müssen zwei Bedingungen erfüllt sein: -

• Wenn die Anzahl der gesetzten Bits im Bereich von links nach rechts liegt ist eine gerade Zahl.

• Für die Summe der Bits in einem bestimmten Bereich

Schauen wir uns verschiedene Eingabe- und Ausgabeszenarien an –

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

Out −

Subarray, das nur die erste Bedingung erfüllt: 4

Subarray, das beide Bedingungen erfüllt: 3

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

Out −

Subarray, das erfüllt nur die erste Bedingung Bedingung: 6

Subarray, das beide Bedingungen erfüllt: 3

Die im folgenden Programm verwendete Methode ist wie folgt -

Bei dieser Methode beobachten wir, dass jedes Unterarray mit XOR verknüpft werden muss 0 durch Vertauschen von Bits, müssen zwei Bedingungen erfüllt sein: – Wenn die Anzahl der gesetzten Bits im Bereich von links nach rechts gerade ist oder für einen bestimmten Bereich die Summe der Bits

• Holen Sie sich das Eingabearray Arr[ ] und berechnen Sie seine Länge .

• Die Funktion removeSubarr(int arr[], int len) gibt die Anzahl der Subarrays zurück, die Bedingung 2 nicht erfüllen.

• Setzen Sie den Anfangszähler auf 0.

• Iterieren Sie mit einer for-Schleife über das Array und nehmen Sie die Variablen sum und maxVal.

• Verwenden Sie eine weitere for-Schleife, um über den Bereich von 60 Unterarrays zu iterieren, denn jenseits von 60 Unterarrays wird Bedingung 2 niemals falsch sein.

• Füge Elemente zur Summe hinzu und nimm den Maximalwert in maxVal.

• Wenn die Summe gerade ist und 2 * maxVal > Summe, ist das Erhöhen der Anzahl als Bedingung 2 nicht erfüllt.

• Beide Schleifen geben am Ende den Zählerstand zurück.

• Die Funktion findSubarrays(int arr1[], int len1) akzeptiert ein Eingabearray und seine Länge und gibt die Anzahl der Unterarrays zurück, die die beiden oben genannten Bedingungen erfüllen.

• Nehmen Sie ein Präfix-Array, um die Anzahl der Unterarrays zu zählen, die nur Bedingung 1 erfüllen.

• Verwenden Sie eine for-Schleife, um das Array zu durchlaufen und jedes Element festzulegen __builtin_popcountll(arr1[i]) Dies ist die Anzahl der darin gesetzten Bits.

• Verwenden Sie eine for-Schleife, um das Präfix-Array zu füllen und setzen Sie prefix[i] = prefix[i] + prefix [i - 1] mit Ausnahme des ersten Elements.

• Zählen Sie ungerade und gerade Werte im Präfix-Array.

• Setzen Sie tmp1 = ( oddcount * (oddcount-1) )/2 und tmp2= ( Evencount * (evencount-1) )/2 und nehmen Sie das Ergebnis als Summe der beiden.

• Das Ergebnis ist die Summe der Subarrays, die nur Bedingung 1 erfüllen.

• Drucken Sie die Ergebnisse aus.

• Aktualisieren Sie nun das Ergebnis mit result=result - removeSubarr( arr1, len1).

• Das Ergebnis enthält nun Subarrays, die beide Bedingungen erfüllen.

• Drucken Sie die Ergebnisse noch einmal aus.

Beispiel

#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;
}

Ausgabe

Wenn wir den obigen Code ausführen, wird die folgende Ausgabe generiert

Subarrays satisfying only 1st condition : 4
Subarrays satisfying both condition : 3

Das obige ist der detaillierte Inhalt vonMaximieren Sie in C++ die Anzahl der Subarrays mit null XOR. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!