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