Member 12847424 Ответов: 2

Учитывая N целых чисел, найдите XOR всех целых чисел, меньших или равных K.

Дан массив из N целых чисел A[1], A[2], ... НЕОПРЕДЕЛЕННАЯ ВЕЛИЧИНА]. Наша задача-ответить на Q запросов.
Каждый запрос - это число K, и наша задача состоит в том, чтобы найти XOR всех целых чисел, которые меньше или равны K в массиве.

входной формат :-
Первая строка содержит 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
1
6

Что я уже пробовал:

Простой способ сделать это-обойти массив для каждого запроса и сделать XOR числа, которое меньше или равно K. Это займет O(Q*N) времени выполнения сложности, которая дает TLE (превышение лимита времени).
Я хочу знать, есть ли лучшая временная сложность, которую мы можем достичь ?

2 Ответов

Рейтинг:
2

Patrice T

Цитата:
Я хочу знать, есть ли лучшая временная сложность, которую мы можем достичь ?

Да, и в этом заключается цель конкурса.
Вы должны внимательно изучить заявление и найти способ уменьшить нагрузку.
Если вы просто хотите, чтобы кто-то решил эту проблему за вас, подумайте о найме профессионального программиста.

Совет: вам нужно изучать алгоритмы и практиковать их. Только опыт может помочь вам.

Если вам нужна помощь, покажите свой код.

Рейтинг:
1

Dave Kreskowiak

У меня есть идея, но сказать тебе об этом-значит сделать за тебя домашнее задание, а этого не произойдет.

Ограничение по времени в задании является ограничением в решаемой задаче.

Итак, если бы вы делали это на бумаге, как бы вы избежали сканирования каждого целого числа в массиве при каждом запросе в поисках значений, меньших или равных запросу?

Все, что требуется, - это немного подумать.

Member 12847424

Это не моя домашняя работа, и я не учусь в школе или колледже. Я учусь на дому.
Я просто делал эту задачу для удовольствия, которое где-то нашел.

Dave Kreskowiak

Извини, но я не собираюсь рисковать. Если бы я сказал что-нибудь о решении, это означало бы отказ от ответа и лишило бы вас возможности думать о возможных решениях.

Member 12847424

Ну, если вы не хотите отвечать, то просто не пишите ответ в первую очередь. Зачем вам вообще писать все это ?

Dave Kreskowiak

Потому что кто-то должен сказать вам, почему вы не получите ответа на проблему.

Member 12847424

Если вы не собираетесь помогать, то почему вообще находитесь на этом сайте ? Просто писать такие ответы ?? И ты делаешь так, чтобы это выглядело как большое дело. Как будто ты самый умный человек в мире, и если ты не ответишь на этот вопрос, то мир остановится. Такое большое эго никому не идет на пользу.

Dave Kreskowiak

Ты не понимаешь. Любой намек на то, каков ответ, дает вам ответ полностью. Не будет никакой работы или мысли, вложенной вами в решение.

ЭТО ТЕБЕ НЕ ПОМОЖЕТ. ЭТО ДЕЛАЕТ ВАШУ РАБОТУ ЗА ВАС.