电子商务网站建设的目的,网站建设公司如何开拓客户,温州网页制作模板,网站seo可以做吗题目 思路和解题方法 计算给定数组中子数组异或和的问题。它采用了前缀异或的方法来预处理数组#xff0c;然后对于每个查询#xff0c;通过异或操作计算子数组的异或和。 读取输入的数组#xff0c;并计算每个位置的前缀异或和。对于每个查询#xff0c;读取查询的左右边界…
题目 思路和解题方法 计算给定数组中子数组异或和的问题。它采用了前缀异或的方法来预处理数组然后对于每个查询通过异或操作计算子数组的异或和。 读取输入的数组并计算每个位置的前缀异或和。对于每个查询读取查询的左右边界计算对应子数组的异或和并输出。 复杂度 时间复杂度:O(nm) 预处理数组的时间复杂度为 O(n)每个查询的时间复杂度为 O(1)因此总体时间复杂度为 O(n m)其中 n 是数组长度m 是查询次数。 空间复杂度:O(n) 程序的空间复杂度取决于数组大小和其他常量因此为 O(n)。 c 代码
#include iostream
using namespace std;const int N 1e510;int main() {// 关闭输入输出流的同步提高速度ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);int n, m;cin n m;int a[N], prefix[N];// 读取数组并计算前缀异或和for (int i 1; i n; i) {cin a[i];prefix[i] prefix[i - 1] ^ a[i];}while (m--) {int l, r;cin l r;// 计算子数组的异或和int ans prefix[r] ^ prefix[l - 1];cout ans \n;}return 0;
}Java 版本仅供参考
import java.util.*;public class Main {static final int N 100009;public static void main(String[] args) {Scanner scanner new Scanner(System.in);int n scanner.nextInt();int m scanner.nextInt();int[] a new int[N];int[] prefix new int[N];for (int i 1; i n; i) {a[i] scanner.nextInt();prefix[i] prefix[i - 1] ^ a[i];}while (m-- 0) {int l scanner.nextInt();int r scanner.nextInt();int ans prefix[r] ^ prefix[l - 1];System.out.println(ans);}}
}Python 版本仅供参考
n, m map(int, input().split())
a list(map(int, input().split()))
prefix [0] * (n 1)for i in range(1, n 1):prefix[i] prefix[i - 1] ^ a[i - 1]for _ in range(m):l, r map(int, input().split())ans prefix[r] ^ prefix[l - 1]print(ans)代码细节
同异或0 所以不用管奇数还是偶数 觉得有用的话可以点点赞支持一下。
如果愿意的话关注一下。会对你有更多的帮助。 每天都会不定时更新哦 人 。
