Параллель А': различия между версиями
Материал из Algocode wiki
KiKoS (обсуждение | вклад) м (→2. Геометрия 1) |
KiKoS (обсуждение | вклад) м (...) |
||
Строка 18: | Строка 18: | ||
* [[Окружности]] | * [[Окружности]] | ||
* [[Выпуклая оболочка]] | * [[Выпуклая оболочка]] | ||
− | * [[Проверка точки на принадлежность многоугольнику за | + | * [[Проверка точки на принадлежность многоугольнику за O(n)|Проверка точки на принадлежность многоугольнику за $O(n)$]] |
+ | * [[Локализация точки в выпуклом многоугольнике]] | ||
+ | * [[Касательные к многоугольнику]] | ||
+ | * [[Формула Пика]] | ||
+ | * [[Пересечение полуплоскостей]] | ||
==3. Структуры данных 1== | ==3. Структуры данных 1== |
Версия 18:38, 15 октября 2020
Содержание
1. Корневая оптимизация
- Корневая декомпозиция на массиве
- Корневая на строках
- Корневая в задачах на графы
- split-rebuild
- split-merge
- Корневая по запросам
- Алгоритм Мо
- Рюкзак за $O(S \sqrt{S})$
2. Геометрия 1
- Векторы
- Прямые
- Отрезки
- Окружности
- Выпуклая оболочка
- Проверка точки на принадлежность многоугольнику за $O(n)$
- Локализация точки в выпуклом многоугольнике
- Касательные к многоугольнику
- Формула Пика
- Пересечение полуплоскостей
3. Структуры данных 1
- Дерево отрезков
- Декартово дерево
- Дерево Фенвика
- Merge sort tree
- Отложенные операции
- Динамические структуры данных
- Двумерные структуры данных
4. Оптимизации динамики
- Монотонность точки перегиба
- Divide&Conquer оптимизация
- Оптимизация Кнута
- Convex hull trick
- Дерево Li Chao
- Лямбда-оптимизация
- $\text{MOD}^2$-оптимизация
5. Математика 1
- Алгоритм Евклида
- Расширенный алгоритм Евклида
- Диофантово уравнение
- Обратный по модулю
- Решето Эратосфена
- Линейное решето Эратосфена
- Обратные ко всем остаткам за O(p)
6. Структуры данных 2
- RMQ offline с СНМ
- RMQ в окне
- Sparse Table
- Disjoint Sparse Table
- LCA
- $RMQ \pm 1$
- Эйлеров обход дерева
- Сжатые деревья
- Heavy-light decomposition
7. Структуры данных 3
8. Строки 1
9. Графы 1
- DFS
- BFS
- 0-1 BFS
- 0-K BFS
- Поиск мостов и точек сочленения
- Конденсация графа
- Топологическая сортировка
- 2-SAT
10. Битовые оптимизации
- Bitset
- Перебор всех подмасок данной маски
- Динамическое программирование по профилю
- Динамическое программирование по подмножествам
- Meet in the middle