โปรแกรม C++ เพื่อค้นหาจำนวนคู่ lr ซึ่ง XORed ให้ผลลัพธ์เหมือนกับ summation

สมมติว่าเรามีอาร์เรย์ A ที่มีองค์ประกอบ N เราต้องหาจำนวนคู่ของจำนวนเต็ม l และ r ที่ตรงกับ A[l] XOR A[l+1] XOR ... XOR A[r-1] XOR A[r] =A[l] + A[ l+1 + ... A[r].

ดังนั้น หากอินพุตเป็น A =[2, 5, 4, 6] ผลลัพธ์จะเป็น 5 เพราะสำหรับคู่ (1,1), (2,2), (3,3), (4, 4) และ (1,2).

ขั้นตอน

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

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

ตัวอย่าง

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

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

อินพุต

{ 2, 5, 4, 6 }

ผลลัพธ์

5