Параллель А': различия между версиями
Материал из Algocode wiki
Глеб (обсуждение | вклад) |
Tikhon (обсуждение | вклад) м |
||
| (не показано 17 промежуточных версий 2 участников) | |||
| Строка 1: | Строка 1: | ||
| − | <p style="font-size: 20pt"> [ | + | <p style="font-size: 20pt">[https://algocode.ru/ap2023/ Страница на алгокоде]</p> |
---- | ---- | ||
==1. Корневая оптимизация== | ==1. Корневая оптимизация== | ||
| Строка 9: | Строка 9: | ||
* [[Корневая по запросам]] | * [[Корневая по запросам]] | ||
* [[Алгоритм Мо]] | * [[Алгоритм Мо]] | ||
| + | * [[Рюкзак за Ssqrt|Рюкзак за $O(S \sqrt{S})$]] | ||
==2. Геометрия 1== | ==2. Геометрия 1== | ||
| − | |||
| + | * [[Векторы]] | ||
| + | * [[Прямые]] | ||
| + | * [[Отрезки]] | ||
| + | * [[Окружности]] | ||
| + | * [[Выпуклая оболочка]] | ||
| + | * [[Проверка точки на принадлежность многоугольнику за O(n)|Проверка точки на принадлежность многоугольнику за $O(n)$]] | ||
| + | * [[Локализация точки в выпуклом многоугольнике]] | ||
| + | * [[Касательные к многоугольнику]] | ||
| + | * [[Формула Пика]] | ||
| + | * [[Пересечение полуплоскостей]] | ||
==3. Структуры данных 1== | ==3. Структуры данных 1== | ||
| Строка 23: | Строка 33: | ||
* [[Динамические структуры данных]] | * [[Динамические структуры данных]] | ||
* [[Двумерные структуры данных]] | * [[Двумерные структуры данных]] | ||
| + | * [https://codeforces.com/blog/entry/57319 Segment tree beats на codeforces] | ||
| Строка 50: | Строка 61: | ||
* [[LCA]] | * [[LCA]] | ||
* [[Алгоритм Фарака-Колтона и Бендера|$RMQ \pm 1$]] | * [[Алгоритм Фарака-Колтона и Бендера|$RMQ \pm 1$]] | ||
| − | |||
* [[Сжатые деревья]] | * [[Сжатые деревья]] | ||
* [[Heavy-light decomposition]] | * [[Heavy-light decomposition]] | ||
| + | |||
| + | ==7. Строки 1== | ||
| + | * [[Z-функция]] | ||
| + | * [[Префикс-функция]] | ||
| + | * [[Алгоритм Манакера]] | ||
| + | * [[Тандемные повторы]] | ||
| + | * [[Бор]] | ||
| + | * [[Ахо-Корасик]] | ||
| + | |||
| + | ==8. Структуры данных 3== | ||
| + | * [[Centroid декомпозиция]] | ||
| + | * [[Переливания]] | ||
| + | |||
| + | ==9. Графы 1== | ||
| + | * [[DFS]] | ||
| + | * [[BFS]] | ||
| + | * [[0-1 BFS]] | ||
| + | * [[0-K BFS]] | ||
| + | * [[Поиск мостов и точек сочленения]] | ||
| + | * [[Конденсация графа]] | ||
| + | * [[Топологическая сортировка]] | ||
| + | * [[2-SAT]] | ||
| + | |||
| + | ==10. Битовые оптимизации== | ||
| + | |||
| + | * [[Bitset]] | ||
| + | * [[Перебор всех подмасок данной маски]] | ||
| + | * [[Динамическое программирование по профилю]] | ||
| + | * [[Динамическое программирование по подмножествам]] | ||
| + | * [[Meet in the middle]] | ||
| + | |||
| + | ==11. Строки 2== | ||
| + | * [[Хэши]] | ||
| + | * [[Суффиксный массив]] | ||
Текущая версия на 19:58, 30 сентября 2023
Содержание
1. Корневая оптимизация
- Корневая декомпозиция на массиве
- Корневая на строках
- Корневая в задачах на графы
- split-rebuild
- split-merge
- Корневая по запросам
- Алгоритм Мо
- Рюкзак за $O(S \sqrt{S})$
2. Геометрия 1
- Векторы
- Прямые
- Отрезки
- Окружности
- Выпуклая оболочка
- Проверка точки на принадлежность многоугольнику за $O(n)$
- Локализация точки в выпуклом многоугольнике
- Касательные к многоугольнику
- Формула Пика
- Пересечение полуплоскостей
3. Структуры данных 1
- Дерево отрезков
- Декартово дерево
- Дерево Фенвика
- Merge sort tree
- Отложенные операции
- Динамические структуры данных
- Двумерные структуры данных
- Segment tree beats на codeforces
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. Строки 1
8. Структуры данных 3
9. Графы 1
- DFS
- BFS
- 0-1 BFS
- 0-K BFS
- Поиск мостов и точек сочленения
- Конденсация графа
- Топологическая сортировка
- 2-SAT
10. Битовые оптимизации
- Bitset
- Перебор всех подмасок данной маски
- Динамическое программирование по профилю
- Динамическое программирование по подмножествам
- Meet in the middle