Изменения
Нет описания правки
# Дан набор образцов $\{p_i\}$. Определить, существует ли бесконечная в две стороны строка $t$, не содержащая $p_i$ как подстроки.
# Докажите, что если строки s и t таковы, что st=ts, то найдется такая строка p, что $s=p^i$ и $t=p^j$ для некоторых i и j.
# Дано взвешенное дерево. Научиться отвечать на запросы "максимальное ребро на пути из $u$ в $v$" Для решения задачи модифицировать метод двоичного подъема ($O(n\log n)$ - предобработка, $O(\log n)$ - ответ на запрос).
# Дано взвешенное дерево. Научиться отвечать на запросы "максимальное ребро на пути из $u$ в $v$" $O(n)$ - предобработка, $O(1)$ - ответ на запрос).
# Дано взвешенное дерево. Научиться отвечать на запросы "вес пути из $u$ в $v$". После предобработки за $O(n)$ ответ на запрос за $O(1)$.
# Дано дерево. Разбить вершины его на множество путей (каждая вершина принадлежит ровно одному пути), чтобы путь от любой вершины до любой переходил с одного пути на другой не более $O(\log n)$ раз.
# Дано дерево. Рассмотрим покрытие его вершин путями по следующему алгоритму: из каждой нелистовой вершины включаем в множество ребро в наиболее глубокое поддерево. Решает ли этот алгоритм предыдущую задачу? Если нет, то какую точную оценку можно дать на число смены текущего пути?
# Дано взвешенное дерево. Уметь отвечать на запросы "минимальное ребро на пути из $u$ в $v$" и "изменить весь ребра $uv$" за полином от логарифма.
# Дано взвешенное дерево. Уметь отвечать на запросы "сумма ребер на пути из $u$ в $v$" и "изменить весь ребра $uv$" за $O(\log n)$.
# Дан массив $a$. Посчитать массив $RMQ[i][j] = min(a[i] ... a[j])$ за $O(n^2)$.
# Модифицировать алгоритм Фараха-Колтона-Бендера, чтобы массив precalc занимал только $O(d)$ памяти для каждой маски.
# Дано дерево. Научиться обрабатывать запросы "наименьший общий предок" и "добавить новый лист с родителем u", предподготовка $O(n \log n)$, запрос $O(\log n)$.
# Дано дерево. Научиться обрабатывать запросы "наименьший общий предок" и "перевесить вершину u от ее текущего родителя к вершине v", предподготовка $O(n \log n)$, запрос $O(\log n)$.
</wikitex>
