Блог пользователя Peter-007

Автор Peter-007, история, 8 месяцев назад, перевод, По-русски

Я придумал это около двух месяцев назад (хотя это скорее всего хорошо известная структура), когда пытался решить задачу, которую я и придумал. Я не видел ни одного блога на эту тему, поэтому решил написать свой.

Основная идея здесь это применение meet-in-the-middle.

В наивном алгоритме, для вставки, или удаления, мы просто создадим вектор размера $$$2^k$$$, где $$$dp_{mask}$$$ означает количество элементов с данным значением, и просто сделаем $$$dp_{mask}++$$$ (либо $$$dp_{mask}--$$$), поэтому это зайтем $$$O(1)$$$ времени, и чтобы сделать запрос просто пробежимся по всем подмаскам of за $$$O(2^k)$$$. Довольно очевидно, что мы можем это сбалансировать.

Разделим биты пополам, для вставки, или удаления, мы пробежимся по всем надмаскам первой половины бит (назовем $$$maskup$$$) и добавим сюда вторую половину (назовем $$$masksec$$$), то есть сделаем $$$dp_{maskup+masksec}++$$$ (либо, если хотим удалить, отнимем единицу).

Чтобы сделать запрос, сделаем наоборот: первая половина зафиксирована, и мы пробежимся по всем подмаскам второй половины.

Единственная проблема это то, что у нас осталось $$$O(2^k)$$$ памяти, мы можем сделать map или unordered_map, но это довольно медленно, или по-умному использовать векторы.

Код (используя вектора с O(2^(k/2)) памяти)
Задача (некоторые другие решения, которые не используют данную идею, могут существовать)
  • Проголосовать: нравится
  • +42
  • Проголосовать: не нравится

»
4 недели назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

How would you react if I posted a rather large among us crewmate png here?