给定N个整数，找到小于或等于K的所有整数的XOR。 [英] Given N integers find XOR of all the integers less than or equal to K.
问题描述
给定N个整数A [1]，A [2]，... A [N]的数组。我们的任务是回答Q查询。
每个查询都是数字K，我们的任务是查找数组中小于或等于K的所有整数的XOR。
输入格式： -
第一行包含N.
第二行包含N个空格分隔的整数。
第三行包含Q.
下一行Q行包含整数K.
输出格式： -
对应每个K输出单行答案。
约束条件： -
1< = N< = 10 ^ 5
1< = Q< = 10 ^ 5
1< ; = A [i]< = 10 ^ 9
1< = K< = 10 ^ 9
时间限制： - 1秒
样本输入： -
4
5 1 2 10
4
5
10
1
8
样品输出： -
6
12 br />
1
$
W帽子我试过了：
一个简单的方法是遍历每个查询的数组并进行小于或等于的数字的XOR。等于K.这将花费O（Q * N）运行时复杂度，这给出了TLE（超出时间限制）。
我想知道我们可以实现更好的时间复杂度吗？
我有一个想法，但告诉你将为你做功课，这不会发生。
分配的时间限制是要解决的问题的一个约束。
所以，如果你是在纸上做这个，你怎么避免扫描每一个每个查询中数组中的整数查找小于或等于查询的值？
所需要的只是一点想法。
< blockquote>
引用：我想知道我们可以实现更好的时间复杂度吗？
是的，这是比赛的对象。
你必须仔细研究这个陈述并找到如何减少工作量。
如果你只是想要某人为你解决这个问题，考虑聘请一名专业程序员。
建议：你需要学习算法并练习它们。只有经验可以帮助您。
如果您需要帮助，请显示您的代码。
Given an array of N integers A[1], A[2], ... A[N]. Our task is to answer Q queries.
Each query is a number K and our task is to find XOR of all the integers which are less than or equal to K in the array.
Input Format :-
First line contains N.
Second line contains N space separated integers.
Third line contains Q.
Next Q lines contains an integer K.
Output Format :-
Corresponding to each K output the answer in single line.
Constraints :-
1 <= N <= 10^5
1 <= Q <= 10^5
1 <= A[i] <= 10^9
1 <= K <= 10^9
Time Limit :- 1 sec
Sample Input :-
4
5 1 2 10
4
5
10
1
8
Sample Output :-
6
12
1
6
What I have tried:
A simple way to do this is traversing the array for each query and doing the XOR of the number which is less than or equal to K. This will take O(Q*N) running time complexity which gives TLE(Time Limit Exceeded).
I want to know is there a better time complexity that we can achieve ?
I have an idea but telling you would be doing your homework for you and that's not going to happen.
The Time Limit in the assignment is a constraint in the problem to be solved.
So, if you were doing this on paper, how do you avoid scanning every integer in the array on every query looking for values less or equal to the query?
All it takes is a little thought.
Quote:I want to know is there a better time complexity that we can achieve ?
Yes and that is the object of the contest.
You have to study carefully the statement and find how to reduce the workload.
If you just want someone to solve this for you, think about hiring a professional programmer.
Advice: you need to study algorithms and practice them. Only experience can help you.
If you want help, show your code.
这篇关于给定N个整数，找到小于或等于K的所有整数的XOR。的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
