Расскажите, пожалуйста, как решается вот такая задача: У нас есть множество битовых масок(n бит). Необходимо выбрать минимально по размеру подмножество, такое, что если мы применим битовую операцию "или" ко всем элементам подмножества, то мы получим битовую маску заполненную единицами(т.е. в десятеричной системе исчисления число 2^n — 1).(n < 10). Количество масок в множестве 10^5.
→ Обратите внимание
→ Трансляции
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 3690 |
| 2 | jiangly | 3647 |
| 3 | Benq | 3581 |
| 4 | orzdevinwang | 3570 |
| 5 | Geothermal | 3569 |
| 5 | cnnfls_csy | 3569 |
| 7 | Radewoosh | 3509 |
| 8 | ecnerwala | 3486 |
| 9 | jqdai0815 | 3474 |
| 10 | gyh20 | 3447 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | maomao90 | 174 |
| 2 | awoo | 164 |
| 3 | adamant | 163 |
| 4 | TheScrasse | 159 |
| 5 | nor | 157 |
| 6 | maroonrk | 155 |
| 7 | -is-this-fft- | 152 |
| 8 | Petr | 146 |
| 8 | orz | 146 |
| 10 | BledDest | 145 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 19.05.2024 16:07:04 (k2).
Десктопная версия, переключиться на мобильную.
При поддержке
Динамическое программирование: Fij пусть будет минимальное количество масок среди первых i которые надо взять чтобы получить j проORив их.
Динамика d[i][mask], где i — текущая позиция, mask — маска, которую мы хотим получить, а значение — собственно минимальное количество чисел, которое нужно для того, чтобы достичь такой маски. Переход — на каждом шаге либо берем текущее число (и переходим в d[i + 1][mask|a[i]]), либо не берем (и переходим в d[i + 1][mask]). Ответ лежит в d[k][(1«n) - 1], где k — количество масок. Сложность — O(k * 2n). Может быть, есть какое-то более простое конструктивное решение, но сейчас лень думать.
O(кол-во_масок*2^n)
Спасибо, исправил. Это должны быть две разные n.
P. S. Подскажите, как делать "<<" внутри теха. Он вырождается в кавычку. А обычные читы вроде
<\ \!<(если не ошибаюсь, '!' обратный пробел делает) у меня тут не работают.Это не совсем то... Челлендж — написать два символа < подряд.
Откуда-то находит лишний пробел, nevermind
Похоже, что сам символ
<внутри формулы безусловно переводится в<(с пробелом до и после).Challenge forfeited.
Фича в том, что
<<если писать — тоже пробел есть < <О, это наблюдение навело на мысль: надо < записать как
<. И действительно, работает:1<<10
гратц))
Это также покрытие множества.
не легче перебрать все маски и за н проверка и подсчет количества едениц?
Что значит "перебрать все маски"? Их может быть гораздо больше, чем N. N — это только количество бит.
Можно по подробнее?
Если у нас есть N битов, то в худшем случае масок 2^N. Тогда перебрать их все можно за 2^(2^N). При N = = 10, это 2^(2^10) = 2^1024. Что будет работать миллионы лет :)
UPD: "Количество масок в множестве 10^5" раньше этого не было? при таком раскладе 2^(10^5) если перебирать. P.S та динамика, которая описана это частный случай задачи о "рюкзаке" видимо будет полезно прочитать Тыц
Можно за O(кол-во масок + 3^n), вчера же на ОпенКапе такая задача была.
Создадим массив, размера 2^n, заполним его INF'ами. Затем, для каждой маски начальной запишем в этот массив под этой маской единичку. Заметим, что маска покрывает все свои подмаски, поэтому информацию пропушим от каждой маски, для которой известен ответ, всем её подмаскам.
Затем простое ДП, берём маску, перебираем все разбиения маски на две подмаски и пробуем улучшить ответ.
Это именно та задача. Т.к. опыта работы с бит масками у меня нет, то на разборе я не очень понял решение:)
а дорешка есть?
На сайте opencup.ru, но только если у вас есть логин и пароль для входа в систему.
советую решить вот эту задачу, точно разберешься с ними
Моё рекурсивное решение со сложностью O(fib(n)) = O(1.618^n) работает 0.3 сек, итересно как люди сдают её за 0.030? Есть более крутое решение?
да, O(2^n), с отсечениями as expected
Что? Ничего не понял, можете более понятно свою мысль изъяснить, и если можно поделитесь идеей решения.
я имел ввиду, что проходит перебор, который теоретически за O(2^n * n) или (2^n * n^2), но благодаря отсечениям он летает :) например в рекурсии маска f — это что собираемся взорвать, g — что взорвётся. берём первую непокрытую вершину из g и поочерёдно для каждой, кто её может взорвать, добавляем в f и делаем новый вызов. ну ещё, наверное, нужно отсечение по размеру ответа
а мне вот интересно знать, как за O(fib(n)) решать
Рекурсивно перебираем города в которые кинем бобмы, очередной город мы либо не берем, либо берем его, но только если он увеличивает число разрушенных городов как минимум на два. В конце перебора в каждый недобитый город кидаем еще по бомбе. Работает это за fib[n].
Вот мое решение. O(2^n) с простыми отсечениями. Отрабатывает за 0.031
Подскажите пожалуйста как получить из двоичного числа двоичное число, отличающееся от исходного в одной 1. Т.е. если у нас есть число 10101 то мне надо получить число(за O(1)), например, 00101. Или 10001 или 10100.
Обязательно убрать? или добавить тоже можно? из условия не ясно.
Если не важно, то можно xor 1
n&(n-1) Убирает наименьший бит 1.
Если уже известен номер единичного бита, то можно применить операцию xor (
^в C++/Java). Например:a ^ (1 << i)инвертирует в a i-й бит.К сожалению, получить номер единичного бита за O(1) без предподсчёта нельзя (или я не умею). Но можно получить число без последнего единичного бита (то есть то, что вам нужно) при помощи формулы
a & (a - 1). Чтобы понять, как это работает, посмотрим на числа: пустьa=B100..00, тогдаa-1=B011..11иa&(a-1)=B000..00.