C++에서는 XOR이 0인 하위 배열 수를 최대화합니다.

정수 값을 포함하는 Arr[] 배열을 얻습니다. 목표는 XOR이 0인 하위 배열의 최대 개수를 찾는 것입니다. 모든 하위 배열의 비트는 원하는 만큼 교환될 수 있습니다.

참고: - 118

비트를 교환하여 하위 배열의 XOR을 0으로 만들려면 두 가지 조건을 충족해야 합니다. -

• 설정된 비트 수가 왼쪽에서 오른쪽으로 범위에 있는 경우 짝수입니다.

• 특정 범위의 비트 합계

다양한 입력 및 출력 시나리오를 살펴보겠습니다.

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

Out −

첫 번째 조건만 만족하는 하위 배열: 4

두 조건을 모두 만족하는 하위 배열: 3

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

Out −

첫 번째 조건만 만족 조건: 6

두 조건을 모두 만족하는 하위 배열: 3

다음 프로그램에서 사용된 방법은 다음과 같습니다. 0 비트를 교환하면 두 가지 조건이 충족되어야 합니다. - 왼쪽에서 오른쪽으로 범위에 설정된 비트 수가 짝수이거나 특정 범위에 대해 비트 합계

입력 배열 Arr[ ]을 가져와 길이를 계산합니다.
removeSubarr(int arr[], int len) 함수는 조건 2를 충족하지 않는 하위 배열의 수를 반환합니다.
초기 개수를 0으로 설정하세요.
for 루프를 사용하여 배열을 반복하고 변수 sum 및 maxVal을 사용합니다.
60개 하위 배열 범위를 반복하려면 또 다른 for 루프를 사용하세요. 왜냐하면 60개 하위 배열을 초과하면 조건 2가 결코 거짓이 되지 않기 때문입니다.
sum에 요소를 추가하고 maxVal에서 최대값을 취합니다.
합이 짝수이고 2 * maxVal > sum인 경우 조건 2로 ​​개수를 증가시키는 것은 만족되지 않습니다.
두 루프가 모두 끝나면 두 반환 횟수가 모두 계산됩니다.
findSubarrays(int arr1[], int len1) 함수는 입력 배열과 해당 길이를 받아들이고 위의 두 조건을 충족하는 하위 배열의 수를 반환합니다.
접두사 배열을 사용하여 조건 1만 만족하는 하위 배열의 수를 계산합니다.
for 루프를 사용하여 배열을 반복하고 각 요소를 설정합니다. __builtin_popcountll(arr1[i]) 여기에 설정된 비트 수입니다.
for 루프를 사용하여 접두사 배열을 채우고 첫 번째 요소를 제외하고 접두사[i] = 접두사[i] + 접두사 [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;
}

Output

위 코드를 실행하면 다음과 같은 출력이 생성됩니다

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

위 내용은 C++에서는 XOR이 0인 하위 배열 수를 최대화합니다.의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!