Цифровой бор: различия между версиями

Материал из Algocode wiki
Перейти к: навигация, поиск
(Новая страница: «Мы уже познакомились с бором, в некоторых задачах появляется идея хранить числа в боре, к...»)
 
Строка 15: Строка 15:
 
Запрос третьего типа уже сложнее.
 
Запрос третьего типа уже сложнее.
  
Заметим, что если мы можем взять $a$ из массива чисел, такой что $(a & 2^i) != (x & 2^i)$(то есть они не равны в $i$-ом бите), то это выгоднее, чем взять любое число $b$, такое что $(b & 2^i) == (x & 2^i)$ и при этом префикс $b$  до $i$ бита равен префиксу $a$ до $i$ бита, тогда давайте жадно спускаться по бору, каждый раз пытаясь пойти в ветку у которой $i$ бит не равен $i$-му биту $x$.
+
Заметим, что если мы можем взять $a$ из массива чисел, такой что $(a and 2^i) != (x and 2^i)$(то есть они не равны в $i$-ом бите), то это выгоднее, чем взять любое число $b$, такое что $(b & 2^i) == (x & 2^i)$ и при этом префикс $b$  до $i$ бита равен префиксу $a$ до $i$ бита, тогда давайте жадно спускаться по бору, каждый раз пытаясь пойти в ветку у которой $i$ бит не равен $i$-му биту $x$.
  
 
{{Автор|Глеб Лобанов|glebodin}}
 
{{Автор|Глеб Лобанов|glebodin}}

Версия 10:20, 11 марта 2020

Мы уже познакомились с бором, в некоторых задачах появляется идея хранить числа в боре, как строке, такая структура называется цифровой бор. Чаще всего числа надо записывать в двоичной системе счисления и тогда все очень просто, но в некоторых задачах требуется какая-то другая Система счисления, так как сравнивать числа в лексикографическом порядке в 10 системе счисления нельзя(2 > 11), то давайте заранее считать, что все числа $ < 10^x$ и тогда будем просто добивать число ведущими нулями. Теперь 02 < 11.

Какие же задачи можно решать такой структурой :

Задача

Дан массив чисел, подаются три вида запросов :

1) Добавить число $x$ 2) Удалить число $x$ 3) Найти число в массиве, у которого $\bigoplus$ c $x$ максимален

Первые 2 вида запросов мы умеем легко делать в цифровом боре.

Запрос третьего типа уже сложнее.

Заметим, что если мы можем взять $a$ из массива чисел, такой что $(a and 2^i) != (x and 2^i)$(то есть они не равны в $i$-ом бите), то это выгоднее, чем взять любое число $b$, такое что $(b & 2^i) == (x & 2^i)$ и при этом префикс $b$ до $i$ бита равен префиксу $a$ до $i$ бита, тогда давайте жадно спускаться по бору, каждый раз пытаясь пойти в ветку у которой $i$ бит не равен $i$-му биту $x$.



Автор конспекта: Глеб Лобанов

По всем вопросам пишите в telegram @glebodin