資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究C++ 中所有子陣列異或的異或查詢
計算給定範圍內所有存在的子陣列的異或，並列印結果。例如
Input : arr[] = { 4, 1, 2, 3, 5 }, Q = 3
Queries
q1 = { 1, 2 }
q2 = { 2, 4 }
q3 = { 1, 4 }
Output : 0
2
0
Explanation : As the given problem states that we need to find XOR of all the subarrays present in the given range so as for query 2 the subarrays are :
{1}, {2}, {3}, {1, 2}, {2, 3}, (1, 2, 3}
So as you can see the number of occurrences of elements are :
1 is present 3 times
2 is present 4 times
3 is present 3 times
Now as we know the property of XOR is that the numbers that are present an even number of times get canceled out so out 2 got canceled out and just the XOR of 3 and 1 remained and that was our answer.我們需要觀察這個問題中形成的模式，然後根據模式進行相應的實現。
解決方法
在這個問題中，我們試圖找到問題中存在的中間模式。當我們看到那個模式時，我們相應地實現它並檢查結果。
示例
以上方法的 C++ 程式碼
#include <bits/stdc++.h>
using namespace std;
void ansQueries(int prefeven[], int prefodd[], int l, int r){
if ((r - l + 1) % 2 == 0) // if number of element present in the range is even
cout << "0";
else{
if (l % 2 == 0) // if l is even
cout << (prefeven[r] ^ prefeven[l - 1]) << "\n";
else // if l is odd
cout << (prefodd[r] ^ prefodd[l - 1]) << "\n";
}
}
int main(){
int arr[] = {4, 1, 2, 3, 5};
int n = sizeof(arr) / sizeof(int); // size of our array
int l[] = {1, 2, 1}; // given queries' left index
int r[] = {2, 4, 4}; // given queries' right index
int q = sizeof(l) / sizeof(int); // number of queries asked
int prefodd[n] = {0}, prefeven[n] = {0}; // different prefix xor for even and odd indices
for (int i = 1; i <= n; i++){
if ((i) % 2 == 0){ // if i is even then we change prefeven
prefeven[i] = arr[i - 1] ^ prefeven[i - 1];
prefodd[i] = prefodd[i - 1];
}else{
prefeven[i] = prefeven[i - 1];
prefodd[i] = prefodd[i - 1] ^ arr[i - 1];
}
}
for (int i = 0; i < q; i++){
ansQueries(prefeven, prefodd, l[i], r[i]);
}
return 0;
}輸出
02 0
以上程式碼的解釋
在這種方法中，我們首先觀察到，如果我們的範圍大小是偶數，那麼我們的答案將為零，因為當我們列印所有子陣列時，每個數字都會出現偶數次，因此透過取它們的異或，答案將簡單地為 0。現在對於我們的下一部分，其中範圍的大小是奇數，在這種情況下，出現奇數次的數字在給定範圍的偶數位置，而我們的答案將簡單地是給定範圍中偶數位置上出現的數字的異或。我們維護兩個字首陣列，它們包含交替位置的異或，因為我們的 prefeven 包含所有偶數索引的異或，而 prefodd 包含所有奇數索引的異或。現在當我們解決查詢時，我們只需要檢查我們的 l 是偶數還是奇數，並相應地給出我們的答案。
結論
在本教程中，我們解決了一個問題，以解決所有子陣列異或的異或查詢。我們還學習了這個問題的 C++ 程式以及我們解決此問題的完整方法（普通方法）。我們可以在其他語言（如 C、Java、Python 和其他語言）中編寫相同的程式。我們希望您覺得本教程有所幫助。
更新於： 2021 年 11 月 26 日
183 次瀏覽
廣告