|
|
| Строка 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. С++ и базовые структуры данных= |