数据结构
网络
关系数据库管理系统
操作系统
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 次浏览
广告