Изменения
Нет описания правки
# В пустое сплей-дерево были добавлены элементы в таком порядке: 30, 40, 60, 50, 80, 70. Какой элемент нужно добавить, чтобы дерево имело минимальную глубину? А какой, чтобы максимальную?
# Пусть мы хотим хранить информацию только в листьях дерева, как нам использовать сплей-дерево для этого?
# Предложите реализацию операции splay(v), если у вас нет ссылки на саму вершину $v$и ссылок на родителя во всех вершинах, а известен только ее ключ, с $O(1)$ дополнительной памяти.# Задана строка из латинских букв и знаков вопроса. Каждый знак вопроса можно заменить на букву. Посчитать число слов длины $n$ из букв латинского алфавита, в которых после согласной всегда идет гласная буква, которые можно получить таким способом.# Задано дерево, у каждой вершины есть вес. Нужно выбрать $k$ вершин суммарно максимального веса, чтобы никакие две соседние вершины не были выбраны.# Задана скобочная последовательность из нескольких видов скобок. Посчитайте минимальное число скобок, которое нужно вставить в эту последовательность, чтобы она стала правильной.# Задана последовательность чисел длины $n$, каждое число не больше $n$. Посчитайте число различных непустых подпоследовательностей последовательности за $O(n)$. Например, последовательность (1, 1, 2) содержит 5 подпоследовательностей: (1), (2), (1, 2), (1, 1), (1, 1, 2).# Посчитайте число различных двоичных деревьев из $n$ вершин.# Посчитайте число различных двоичных деревьев из $n$ вершин без порядка на детях.# Посчитайте число различных красно-черных деревьев из $n$ вершин.# Предложите алгоритм восстановления наибольшей возрастающей подпоследовательности по функции ДП, вычисление которой была предложено на лекции за $O(n \log{n})$ с $O(n)$ дополнительной памяти.# Задана последовательность. Про каждое $i$ определите одно из трех: элемент $a_i$ не может входить ни в одну НВП, элемент $a_i$ входит хотя бы в одну НВП, элемент $a_i$ входит во все НВП за $O(n \log{n})$.# Заданы две последовательности $a$ и $b$. Подпоследовательность $c$ называется общей для $a$ и $b$, если $c$ является подпоследовательностью $a$ и подпоследовательностью $b$. Найдите наибольшую общую подпоследовательность $a$ и $b$ за время $O(|a| \cdot |b|)$ и памятью $o(|a| \cdot |b|)$.# Задача о рюкзаке. Заданы $n$ предметов, для каждого известен вес $w_i$ и цены $p_i$. Вам нужно выбрать подмножество предметов суммарным весом не более $W$ с максимальной суммарной ценой. Найдите это подмножество за время $O(W \cdot n)$ и память $O(W)$.
</wikitex>
