Изменения
Нет описания правки
# Предложите реализацию операции splay(v), если у вас нет ссылки на саму вершину $v$ и ссылок на родителя во всех вершинах, а известен только ее ключ, с $O(1)$ дополнительной памяти.
# Задана строка из латинских букв и знаков вопроса. Каждый знак вопроса можно заменить на букву. Посчитать число слов длины $n$ из букв латинского алфавита, в которых после согласной всегда идет гласная буква, которые можно получить таким способом.
# Задано дерево, у каждой вершины есть вес. Нужно выбрать $k$ вершин суммарно максимального веса, чтобы никакие две соседние соединенные ребром вершины не были выбраны.
# Задана скобочная последовательность из нескольких видов скобок. Посчитайте минимальное число скобок, которое нужно вставить в эту последовательность, чтобы она стала правильной.
# Задана последовательность чисел длины $n$, каждое число не больше $n$. Посчитайте число различных непустых подпоследовательностей последовательности за $O(n)$. Например, последовательность (1, 1, 2) содержит 5 подпоследовательностей: (1), (2), (1, 2), (1, 1), (1, 1, 2).
