Настройки поиска (Страница 3 из 15)

Ошибка в иллюстрации... Состояние для строки "a" не является терминальным.

Спасибо, исправлю.

спасибо.

Правильно ли я понимаю, что это сведение нетривиально, и первым его привёл Эдмондс?
(в 1964 г.; я пытался разобраться по этой статье, но не смог понять, как решать данную задачу)
Также нашлась статья Hartvigsen, но не менее понятная.

(про одуванчик гораздо лучше было. наверное, тот шедевр уже не превзойти...)

Нет, при n=6, k=3 подзадача будет вызываться от n=4, поэтому будет возвращать в отрезке [0;3]. После нормализации в строках 5-8 res=0 и res=1 останутся без изменений, а res=2 и res=3 увеличатся на 1.

Насчет случая 2а - да, пожалуй, технически он необходим, хотя я всё же верю, что эти два случая можно объединить в одну формулу.

Да, с массивами теоретически можно делать (т.е. везде вместо указателей использовать индексы в массиве). Но вот без ссылок - заметно более громоздко получится.

Компактная реализация сильно использует хитрости массивов/указателей, поэтому без их понимания разобраться в реализации будет непросто.

• item - это структура данных, представляющая собой одну вершину дерева.

• pitem - это указатель на структуру item. Такие указатели мы используем, чтобы хранить связи между вершинами: т.е. левый и правый сын каждой вершины - это указатели, указывающие на некоторые другие вершины (или NULL, если не указывает никуда). Да и корень дерева root - тоже указатель, он указывает на вершину-корень. В общем, всё дерево написано на указателях

• Что вообще такое ссылка в C++. Упрощенное понимание такое: если у функции какой-то параметр является ссылкой, то внутри функции мы можем присваивать этому параметру какое-нибудь значение, и это значение запишется в передаваемую переменную.

• pitem & - это ссылка на указатель. Это самый сложный для понимания момент. Давайте посмотрим на одно из мест, где это используется: функция split(). Этой функции передаётся дерево t, ключ key, по которому надо разрезать дерево t, а результат этой функции кладётся в параметры l и r. Соответственно, для чего параметры l и r сделаны ссылками на pitem? Например, чтобы мы могли вызвать эту функцию с аргументом l равным t.r, аргументом r равным чему-нибудь ещё, и результат разрезания записался бы в t.r.

Всё равно, конечно, получилось сумбурно и запутанно, но надеюсь, что вы что-нибудь поймете из моего объяснения.

Нет, насколько я помню, вполне там можно обойтись без пометок.

Кажется, что незачем передавать в dfs значение, пришедшее "сверху": ведь в таком решении то, что происходит выше текущей вершины, - не особенно-то и важно. Это решение заражает вершины в жадном порядке, каждый раз заражая только действительно необходимую вершину. Поэтому передавать ничего не надо, а просто надо посмотреть: если мы после запуска dfs из всех потомков видим, что один какой-то потомок вернул отрицательное число, превосходящее по модулю все положительные числа из других потомков - то все эти положительные потомки можно мысленно "удалить".

UPD:

Надо не -1, а -k, потому что это важно, на каком именно расстоянии произошло ближайшее снизу заражение.

Вроде жадно можно. Просто пускаем обход по дереву, как бы идём от листьев вверх, и как только оказывается, что мы в текущей вершине обязаны заражать, то заражаем. Т.е. делаем dfs, который возвращает расстояние до самого далёкого незаражённого потомка, и если в текущей вершине это значение получилось равно k - заражаем её, иначе - нет.

А как её решать принципом включений-исключений?

Вот вертикальной декомпозицией за N^3 log N понятно как решать: мы сводим трёхмерную задачу к O(N) двумерным задачам (перебрав Z среди имеющихся в инпуте), а каждую двумерную задачу с прямоугольниками сводим к O(N) одномерным (перебрав Y среди имеющихся в инпуте), а каждую одномерную задачу - решив за O(N log N) (сортировкой).

Почему нельзя сделать такую простую динамику: d[v][c] - ответ для поддерева с корнем в v, если саму вершину мы покрасили в c (c=0..2).

Считается она так: пусть мы хотим посчитать ответ d[v][c]. Тогда каждый сын вершины v должен иметь цвет, отличный от c. Поскольку разные сыновья не влияют друг на друга, то можно просто для каждого сына to посмотреть значения динамик d[to][(c+1)%3] и d[to][(c+2)%3] и выбрать из них максимальное. Просуммировав это по всем сыновьям, и прибавив единицу, если c=0, мы получим искомое d[v][c].

В код не вчитывался, но мне кажется, что неправильно работать может то, когда вы вызываете insert() от ключа, уже имеющегося в дереве (не проверяя, что такого ключа не было). Скажем, если node->prior получился большим, чем у всех вершин дерева, то эта новая вершина встанет в корень, а остальное дерево просто просплитится на два - и в результате могут появиться две вершины с одинаковым key.