資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
JavaScript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究C++ 程式，查詢 XOR 運算結果與求和結果相同的 l-r 對數
假設我們有一個 N 元素的陣列 A。需要查詢滿足 A[l] XOR A[l+1] XOR ... XOR A[r-1] XOR A[r] = A[l] + A[l+1] + ... A[r] 的整數對 l 和 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
更新時間： 2022 年 3 月 3 日
94 次瀏覽
廣告