Параллель B': различия между версиями

Материал из Algocode wiki
Перейти к: навигация, поиск
Строка 1: Строка 1:
 
<p style="font-size: 14pt">[https://algocode.ru/bp2019/ Страница на алгокоде]</p>
 
<p style="font-size: 14pt">[https://algocode.ru/bp2019/ Страница на алгокоде]</p>
=Второй семестр=
 
 
=23. Суффиксный массив =
 
* [https://algorithmica.org/ru/suffix-array конспект с Алгоритмики про суфмас и LCP]
 
 
===Видео по теме===
 
*[https://www.youtube.com/watch?v=gzmmrUMnSEA Лекция от Павла Маврина]
 
 
=22. Разделяй-и-властвуй, meet in the middle=
 
* [[MITM]]
 
* [[Разделяй-и-властвуй]]
 
 
===Видео по теме===
 
* [https://www.youtube.com/watch?v=Irx0wa-JBmY&feature=youtu.be MITM]
 
* [https://www.youtube.com/watch?v=iOrAjBHQOUA&feature=youtu.be Алгоритм Карацубы]
 
* [https://www.youtube.com/watch?v=q74CyZl45G0&feature=youtu.be DC - оптимизация]
 
* [https://www.youtube.com/watch?v=aTJHNr9fbjs Центроидная декомпозиция от Павла Маврина]
 
 
=21. Обо всем=
 
* [[Дерево Фенвика]]
 
* [[ДП по цифрам]]
 
* [[set-trie]]
 
* [http://osebje.famnit.upr.si/~savnik/papers/cdares13.pdf статья про set-trie]
 
===Видео по теме===
 
* [https://www.youtube.com/watch?v=oMdgpyE62ig&feature=youtu.be Дерево Фенвика]
 
* [https://www.youtube.com/watch?v=oMdgpyE62ig&feature=youtu.be#t=52m25s ДП по цифрам]
 
* [https://www.youtube.com/watch?v=oMdgpyE62ig&feature=youtu.be#t=1h21m15s set-trie]
 
 
=20. Декартово дерево=
 
 
* [[Декартово дерево]]
 
 
===Видео по теме===
 
* [https://www.youtube.com/watch?v=nXxQYQQEPwQ Декартово дерево]
 
 
=19. Строки 2=
 
* [[Z-функция]]
 
* [https://algorithmica.org/ru/string-searching Конспект с Алгоритмики про префикс-функцию и z-функцию]
 
* [[Бор]]
 
* [[Цифровой бор]]
 
* [[Алгоритм Ахо-Корасик]]
 
 
===Видео по теме===
 
* [https://www.youtube.com/watch?v=cGfKt5q1qu8#t=42m10s КМП]
 
* [https://www.youtube.com/watch?v=BP9LXwosFco Z-функция]
 
* [https://www.youtube.com/watch?v=BP9LXwosFco#t=27m50s Бор]
 
* [https://www.youtube.com/watch?v=pctMrLsWPbU Ахо-Корасик]
 
 
=18. Продвинутая геометрия=
 
* [[Выпуклая оболочка]]
 
* [[Поиск двух ближайших точек]]
 
* [https://algocode.ru/files/course_aspb2019/main.pdf Конспект по геометрии, чтобы вспомнить все важное и узнать новое интреесное]
 
 
===Видео по теме===
 
* [https://www.youtube.com/watch?v=JPypmkh77S4 Геометрия]
 
* [https://www.youtube.com/watch?v=JPypmkh77S4#t=11m21s Выпуклая оболочка]
 
* [https://www.youtube.com/watch?v=JPypmkh77S4#t=21m20s Алгоритм Джарвиса]
 
* [https://www.youtube.com/watch?v=JPypmkh77S4#t=33m33s Алгоритм Грэхема]
 
* [https://www.youtube.com/watch?v=JPypmkh77S4#t=52m47s Алгоритм Чэна]
 
 
=17. Комбинаторные объекты=
 
* [[Генерация всех правильных скобочных последовательностей]]
 
* [[Построение следующей в лексикографическом порядке перестановки по данной]]
 
* [[Поиск k-ой в лексикографическом порядке перестановки]]
 
* [[Поиск k-ой в лексикографическом порядке скобочной последовательности]]
 
 
=16. Паросочетания=
 
* [[Паросочетание]]
 
* [[Проверка на двудольность]]
 
* [[Лемма Бержа]]
 
* [[Алгоритм Куна]]
 
* [[Важные задачи]]
 
 
===Видео по теме===
 
* [https://www.youtube.com/watch?v=-AzO1CKEqcQ Паросочетания в двудольных графах]
 
* [https://www.youtube.com/watch?v=GRluYFzdfSM Ролик про паросочетания в играх]
 
 
=15. Игры=
 
* [[Игра на графе]]
 
* [[Ним]]
 
* [[Функция Шпрага-Гранди]]
 
* [http://olymp.sch239.net/materials/games.pdf Книга от Андрея Станкевича]
 
 
===Видео по теме===
 
* [https://www.youtube.com/watch?v=o4eZBJspDzU Лекция от Павла Маврина]
 
 
=14. Дерево Отрезков=
 
* [[Дерево отрезков]]
 
* [[А что еще можно хранить в до?]]
 
* [[Отложенные операции]]
 
* [[Динамическое(Неявное) Дерево Отрезков]]
 
* [[Сканлайн + Дерево отрезков]]
 
 
===Видео по теме===
 
* [https://www.youtube.com/watch?v=PHL6gHLfBs8 Дерево отрезков]
 
* [https://www.youtube.com/watch?v=NJB05K1M7oE Групповые операции]
 
 
=13. Хеши=
 
* [[Полиномиальное хеширование строк]]
 
* [[Сравнение строк с помощью хешей]]
 
* [[Хеширование множеств (с точностью до перестановки)]]
 
* [[Хеширование матриц]]
 
* [[Хеш-таблицы (открытый ключ)]]
 
* [[Хеш-таблицы (цепочки)]]
 
* [[Хеширование корневых деревьев]]
 
 
===Видео по теме===
 
* [https://www.youtube.com/watch?v=cGfKt5q1qu8 Лекция от Павла Маврина]
 
 
=Первый семестр=
 
 
=12. Динамическое программирование=
 
 
===Повторение для подзабывших===
 
* [[Основы ДП]]
 
* [[План ДП]]
 
* [[Одномерное ДП]]
 
* [[Двумерное ДП]]
 
* [[Восстановление ответа: через массив динамики и через массив предков.]]
 
* [[Ленивая динамика.]]
 
* [[Рюкзак]]
 
* [[Динамика по префиксу и значению последнего элемента]]
 
* [[НВП]]
 
* [[НОП]]
 
 
===Новое===
 
* [[Паросочетание]]
 
* [[ДП по поддеревьям]]
 
* [[Маска]]
 
* [[Битовые операции]]
 
* [[ДП по подмножествам]]
 
* [[ДП по профилю]]
 
* [[Перебор всех подмасок данной маски]]
 
 
==Видео по теме==
 
 
* [https://www.youtube.com/watch?v=6XHWHnvBiu4#t=28m09s ДП по подмножествам]
 
* [https://www.youtube.com/watch?v=IISXNH1ROds ДП по профилю]
 
 
=11. Геометрия, примитивы=
 
* [[Векторы]]
 
* [[Прямые]]
 
* [[Отрезки]]
 
* [[Окружности]]
 
 
=10. LCA=
 
===Вспомогательная структура===
 
*[[Sparse Table]]
 
===LCA===
 
*[[LCA]]
 
*[[Эйлеров обход]]
 
===Методы===
 
*[[Двоичные подъемы]]
 
*[[Решение с помощью Эйлерова обхода]]
 
 
==Видео по теме==
 
 
* [https://www.youtube.com/watch?v=C7oVQ9vsVDY LCA от Павла Маврина]
 
* [https://www.youtube.com/watch?v=C7oVQ9vsVDY#t=04m31s Двоичные подъемы]
 
* [https://www.youtube.com/watch?v=C7oVQ9vsVDY#t=29m43s Сведение к RMQ]
 
* [https://www.youtube.com/watch?v=D0NQS_lyrY0 Sparse Table]
 
 
=9. СНМ и остовные деревья=
 
* [[СНМ]]
 
===Остовные деревья===
 
* [[Лемма о безопасном ребре]]
 
* [[Алгоритм Краскала]]
 
* [[Алгоритм Прима]]
 
 
===Видео по теме===
 
 
* [https://www.youtube.com/watch?v=VmNPG__osBE MST от Павла Маврина]
 
* [https://www.youtube.com/watch?v=VmNPG__osBE#t=03m45s Лемма о разрезе]
 
* [https://www.youtube.com/watch?v=r6JVt4NIR1Y DSU(СНМ)]
 
* [https://www.youtube.com/watch?v=VmNPG__osBE#t=12m09s Алгоритм Краскала]
 
* [https://www.youtube.com/watch?v=VmNPG__osBE#t=30m39s Алгоритм Прима]
 
 
=8. Кратчайшие пути=
 
* [[BFS]]
 
* [[0-1 BFS]]
 
* [[1-k BFS]]
 
* [[Алгоритм Форда-Беллмана]]
 
* [[Алгоритм Дейкстры]]
 
 
===Видео по теме===
 
 
* [https://www.youtube.com/watch?v=O5n1ORyECAY&list=PL4_hYwCyhAvYikJXQHwKCOe1i7So13ZNc&index=9 Лекция про кратчайшие пути от Саши Гришутина]
 
* [https://www.youtube.com/watch?v=GJkCzQo-rAc BFS]
 
* [https://www.youtube.com/watch?v=GJkCzQo-rAc#t=18m16s Дейкстра]
 
* [https://www.youtube.com/watch?v=0drmQj1RsEQ Форд-Беллман и Флойд]
 
 
 
=7. Математика=
 
=7. Математика=
  
Строка 199: Строка 8:
 
* [[Матрицы]]
 
* [[Матрицы]]
  
 
=6. Корневая декомпозиция=
 
 
* [[Корневая декомпозиция]]
 
* [[Корневая декомпозиция на массиве]]
 
* [[Корневая на строках]]
 
* [[Корневая в задачах на графы]]
 
* [[Корневая по запросам]]
 
* [[Алгоритм Мо]]
 
* [[Подбор констант]]
 
  
 
=5. С++ и базовые структуры данных=
 
=5. С++ и базовые структуры данных=

Версия 22:12, 9 ноября 2020

Страница на алгокоде

7. Математика


5. С++ и базовые структуры данных

Базовые структуры данных

С++

4. Динамическое программирование

Видео по теме

3. Графы

Видео по теме

2. Поиски за $O(\log(n))$

Бинарный поиск

Тернарный поиск

Видео по теме

1. Сортировки

Анализ времени и памяти

Квадратичные сортировки

Сортировки за $n\log{n}$

Другие сортировки

Связанные задачи