Битовые маски как маленькие множества
Представляйте подмножества целыми числами
«Битовые маски как маленькие множества» — бесплатный урок Competitive Programming Academy на CoddyKit. Это урок 4 из 4. Ты можешь прочитать весь урок бесплатно ниже — а потом практиковать его прямо в браузере с встроенным редактором кода и ИИ-репетитором 24/7. Это часть пути обучения Competitive Programming Academy, и твой прогресс синхронизируется между веб-версией и приложением CoddyKit. Курс Competitive Programming Academy содержит 4 уроков всего.
Целое число как множество
Одно целое число может представлять целое множество: если бит i равен 1, элемент i входит в множество. Так подмножество упаковывается в одно небольшое и быстро обрабатываемое значение. 🎒
Пустое и полное множества
Число 0 — это пустое множество, а значение, в котором младшие n битов включены, означает присутствие всех элементов.
empty = 0
full = (1 << 4) - 1 # 0b1111, four elementsДобавление элемента
Чтобы добавить элемент i в множество, установите его бит с помощью OR. Это тот же приём установки бита, который теперь можно рассматривать как объединение с одним элементом.
s = 0
s |= (1 << 2) # add element 2Удаление элемента
Чтобы удалить элемент i, выполните AND с инвертированным битом. Элемент покидает множество, а все остальные остаются на месте. Это разность множеств с одним удаляемым элементом.
s &= ~(1 << 2) # remove element 2Проверка принадлежности
Проверьте, принадлежит ли элемент i множеству, выполнив AND с его битом. Ненулевой результат означает, что элемент является членом множества.
if s & (1 << 2):
print('2 is in the set')Объединение и пересечение
Выполните OR над двумя масками, чтобы получить их объединение, и AND — чтобы получить их пересечение. Операции над целыми множествами превращаются в одну машинную инструкцию каждая.
union = a | b
inter = a & bРазмер множества — это popcount
Количество элементов в битовой маске — это просто количество установленных в ней битов. Используйте bit_count, чтобы мгновенно получить размер.
size = mask.bit_count()Перебор всех подмножеств
Для n элементов целые числа от 0 до 2 в степени n минус 1 перечисляют каждое подмножество. Один простой цикл по диапазону охватывает их все.
for mask in range(1 << n):
pass # mask is one subsetБыстрый перебор подмасок
Чтобы посетить только подмножества заданной маски, используйте классический цикл по подмаскам. Он проходит по каждому подмножеству в порядке убывания.
sub = mask
while sub:
sub = (sub - 1) & maskЗдесь применяется DP с битовыми масками
Битовые маски служат состоянием во многих задачах на DP, например в задаче о коммивояжёре, где маска отслеживает посещённые вершины.
Держите n небольшим
При наличии 2 в степени n подмножеств этот приём остаётся практичным только для небольших n, обычно примерно до 20. Дальше количество подмножеств стремительно растёт. ⚠️
Быстрая проверка
И последний вопрос о множестве, представленном маской.
Повторение: множества с битовыми масками
Вы можете хранить множество в одном целом числе, добавлять и удалять элементы с помощью масок и перебирать каждое подмножество. Это открывает быстрый DP с битовыми масками. 🎉
Часто задаваемые вопросы
Урок «Битовые маски как маленькие множества» бесплатный?
Да — полный текст урока «Битовые маски как маленькие множества» бесплатно доступен здесь в веб-версии. Чтобы практиковать его интерактивно (встроенный редактор кода и ИИ-репетитор 24/7) и разблокировать остальной курс Competitive Programming Academy, подпишись на CoddyKit PRO. Курс Competitive Programming Academy содержит 4 уроков всего.
Чему я научусь в уроке «Битовые маски как маленькие множества»?
Представляйте подмножества целыми числами Ты практикуешь Competitive Programming Academy с помощью реального кода, который запускаешь прямо в браузере, и ИИ-репетитор 24/7 отвечает на твои вопросы во время урока.
Нужен ли мне опыт, чтобы начать Competitive Programming Academy?
Предыдущий опыт не требуется. Competitive Programming Academy на CoddyKit структурирован для всех уровней — от новичков до продвинутых, поэтому ты можешь начать отсюда или с самого начала и учиться в своем темпе. Это урок 4 из 4.
Сколько времени занимает урок «Битовые маски как маленькие множества»?
Большинство уроков CoddyKit занимают около 5–10 минут. Каждый из них компактный и интерактивный, поэтому ты постоянно делаешь прогресс и продолжаешь с того же места в веб-версии и приложении.
Можно ли писать и запускать код в этом уроке Competitive Programming Academy?
Да. Каждый урок Competitive Programming Academy включает встроенный редактор кода, поэтому ты пишешь и запускаешь реальный код прямо в браузере и получаешь моментальную обратную связь от AI — локальная установка не требуется.
Все уроки этого курса
- AND, OR, XOR и сдвиги
- Установить, сбросить и переключить бит
- Подсчёт битов и младший установленный бит
- Битовые маски как маленькие множества