Chương trình C ++ để tìm số cặp l-r mà kết quả XORed giống như phép tính tổng

Giả sử chúng ta có một mảng A với N phần tử. Ta phải tìm số cặp số nguyên l và r thỏa mãn A [l] XOR A [l + 1] XOR ... XOR A [r-1] XOR A [r] =A [l] + A [ l + 1] + ... A [r].

Vì vậy, nếu đầu vào là A =[2, 5, 4, 6], thì đầu ra sẽ là 5, vì đối với các cặp (1,1), (2,2), (3,3), (4, 4) và (1,2).

Các bước

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

n := size of A
Define some arrays of size (n + 1) each, a, s and sx
for initialize i := 1, when i <= n, update (increase i by 1), do:
   a[i] := A[i - 1]
   s[i] := s[i - 1] + a[i]
   sx[i] := sx[i - 1] XOR a[i]
res := 0
for initialize l := 1, when l <= n, update (increase l by 1), do:
   bg := l, en = n, r = l
   while bg <= en, do:
      mi := (bg + en) / 2
      if s[mi] - s[l - 1] is same as (sx[mi] XOR sx[l - 1]), then:
         r := mi
         bg := mi + 1
      Otherwise
         en := mi - 1
      res := res + (r - l + 1)
return res

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

#include <bits/stdc++.h>
using namespace std;

int solve(vector<int> A){
   int n = A.size();
   vector<int> a(n + 1), s(n + 1), sx(n + 1);
   for (int i = 1; i <= n; i++){
      a[i] = A[i - 1];
      s[i] = s[i - 1] + a[i];
      sx[i] = sx[i - 1] ^ a[i];
   }
   int res = 0;
   for (int l = 1; l <= n; l++){
      int bg = l, en = n, r = l;
      while (bg <= en){
         int mi = (bg + en) / 2;
         if (s[mi] - s[l - 1] == (sx[mi] ^ sx[l - 1])){
            r = mi;
            bg = mi + 1;
         }
         else
            en = mi - 1;
      }
      res += (r - l + 1);
   }
   return res;
}
int main(){
   vector<int> A = { 2, 5, 4, 6 };
   cout << solve(A) << endl;
}

Đầu vào

{ 2, 5, 4, 6 }

Đầu ra

5