Lelyte
@lelyte
7 posts

Корневые оптимизации

Рассмотрим такую задачу Мы хотим делать две операции: 1) a[l; r] += x 2) a[l; r] < x

Z-функция, Префикс-Функция, Бор, Манакер

Z-функция - это длина максимального префикса подстроки S, который начинается в x, который одновременно является префиксом нашей строки S s[x ... x + k] == s[0 ... k]

ДП по подмножествам, ДП по профилю

dp[last][mask] = min длина Гамильтонова пути из S в Last, если посетить вершины mask dp[last][mask] -> dp[next][mask | (1 << next)] next не принадлежит mask last->next есть в графе 𝒪(2^n * n^2)

Дерево Фенвика + Sparse Table ~ Сириус 07.06

Дерево Фенвика - структура данных, дерево на одномерном массиве, которая обладает такими свойствами, как:

Теория Чисел ~ Сириус 05.06

Основная теорема арифметики гласит, что каждое число раскладывается на простые множители, причем единственным образом

ScanLine ~ Сириус 04.06

Задача заключается в том, что на плоскости имеется N прямоугольников, стороны которых параллельны осям координат. Требуется вычислить площадь объединения данных прямоугольников

Тинькофф B' - Дерево Фенвика

Дерево Фенвика - структура данных, дерево на одномерном массиве, которая обладает такими свойствами, как: