|
|
| Строка 1: |
Строка 1: |
| − | <p style="font-size: 14pt">[https://algocode.ru/bp2020/ Страница на алгокоде]
| |
| − |
| |
| − | =23. Суффиксный массив =
| |
| − | * [https://algorithmica.org/ru/suffix-array конспект с Алгоритмики про суфмас и LCP]
| |
| − |
| |
| − | ===Видео по теме===
| |
| − | *[https://www.youtube.com/watch?v=5ykXTgTwE30&feature=youtu.be Лекция 2020-2021]
| |
| − | *[https://www.youtube.com/watch?v=gzmmrUMnSEA Лекция от Павла Маврина]
| |
| − |
| |
| − |
| |
| − | =22. Разделяй-и-властвуй, meet in the middle=
| |
| − | * [[MITM]]
| |
| − | * [[Разделяй-и-властвуй]]
| |
| − |
| |
| − | ===Видео по теме===
| |
| − | * [https://www.youtube.com/watch?v=k9JvhcoeYkE&feature=youtu.be Лекция 2020-2021]
| |
| − | * [https://www.youtube.com/watch?v=Irx0wa-JBmY&feature=youtu.be 2019-2020: MITM]
| |
| − | * [https://www.youtube.com/watch?v=iOrAjBHQOUA&feature=youtu.be 2019-2020: Алгоритм Карацубы]
| |
| − | * [https://www.youtube.com/watch?v=q74CyZl45G0&feature=youtu.be 2019-2020: DC-оптимизация]
| |
| − | * [https://www.youtube.com/watch?v=aTJHNr9fbjs Центроидная декомпозиция от Павла Маврина]
| |
| − |
| |
| − | =21.ДП по цифрам=
| |
| − | * [[ДП по цифрам]]
| |
| − | ===Видео по теме===
| |
| − | * [https://www.youtube.com/watch?v=oMdgpyE62ig&feature=youtu.be Лекция 2019-2020]
| |
| − | * [https://www.youtube.com/watch?v=sDYE4pZeZD0 Лекция 2020-2021]
| |
| − |
| |
| − | =20. Дерево Фенвика=
| |
| − | * [[Дерево Фенвика]]
| |
| − | ===Видео по теме===
| |
| − | * [https://www.youtube.com/watch?v=tmYxmvXo6hQ&feature=youtu.be Запись лекции 2020-2021]
| |
| − | * [https://www.youtube.com/watch?v=oMdgpyE62ig&feature=youtu.be Запись лекции 2019-2020]
| |
| − |
| |
| − | =19. Декартово дерево=
| |
| − | * [[Декартово дерево]]
| |
| − | ===Видео по теме===
| |
| − | * [https://www.youtube.com/watch?v=nXxQYQQEPwQ Лекция 2019-2020]
| |
| − | * [https://www.youtube.com/watch?v=uTNtxepNk3o&feature=youtu.be Лекция 2020-2021]
| |
| − |
| |
| − |
| |
| − | =18. Паросочетания=
| |
| − | * [[Паросочетание]]
| |
| − | * [[Проверка на двудольность]]
| |
| − | * [[Лемма Бержа]]
| |
| − | * [[Алгоритм Куна]]
| |
| − | * [[Важные задачи]]
| |
| − | * [http://codeforces.com/blog/entry/63164?locale=ru Сведение MinVertexCover к 2-SAT]
| |
| − |
| |
| − | ===Видео по теме===
| |
| − | * [https://www.youtube.com/watch?v=-AzO1CKEqcQ Паросочетания в двудольных графах]
| |
| − | * [https://www.youtube.com/watch?v=GRluYFzdfSM Ролик про паросочетания в играх]
| |
| − |
| |
| − | =17.Строки=
| |
| − | * [[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 Ахо-Корасик]
| |
| − | * [https://www.youtube.com/watch?v=Y-yusdOwxXc&feature=youtu.be Лекция 2020-2021]
| |
| − |
| |
| − | =16. Продвинутая геометрия=
| |
| − | * [[Выпуклая оболочка]]
| |
| − | * [[Поиск двух ближайших точек]]
| |
| − | * [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 Алгоритм Чэна]
| |
| − |
| |
| − | =15. Игры=
| |
| − | * [[Игра на графе]]
| |
| − | * [[Ним]]
| |
| − | * [[Функция Шпрага-Гранди]]
| |
| − | * [http://olymp.sch239.net/materials/games.pdf Книга от Андрея Станкевича]
| |
| − |
| |
| − | ===Видео по теме===
| |
| − | * [https://www.youtube.com/watch?v=y3CIDrTwHAY&feature=youtu.be Лекция 2020-2021]
| |
| − | * [https://www.youtube.com/watch?v=o4eZBJspDzU Лекция от Павла Маврина]
| |
| − |
| |
| − | =14. Комбинаторные объекты=
| |
| − | * [[Перестановки и действия с ними]]
| |
| − | * [[Правильные скобочные последовательности]]
| |
| − | * [[Другие Комбинаторные объекты]]
| |
| − | ===Видео по теме===
| |
| − | * [https://www.youtube.com/watch?v=gn1VZnGBHrY&feature=youtu.be Лекция 2020-2021]
| |
| − |
| |
| − | =13. Дерево отрезков=
| |
| − | * [[Дерево отрезков]]
| |
| − | * [[А что еще можно хранить в до?]]
| |
| − | * [[Отложенные операции]]
| |
| − | * [[Динамическое(Неявное) Дерево Отрезков]]
| |
| − | * [[Сканлайн + Дерево отрезков]]
| |
| − |
| |
| − | ===Видео по теме===
| |
| − | * [https://www.youtube.com/watch?v=kcX732Fo4W8&feature=youtu.be Лекция 2020-2021]
| |
| − | * [https://www.youtube.com/watch?v=PHL6gHLfBs8 Дерево отрезков]
| |
| − | * [https://www.youtube.com/watch?v=NJB05K1M7oE Групповые операции]
| |
| − |
| |
| − | =12=
| |
| − | ==Хеши==
| |
| − | * [[Полиномиальное хеширование строк]]
| |
| − | * [[Сравнение строк с помощью хешей]]
| |
| − | * [[Хеширование множеств (с точностью до перестановки)]]
| |
| − | * [[Хеширование матриц]]
| |
| − | * [[Хеш-таблицы (открытый ключ)]]
| |
| − | * [[Хеш-таблицы (цепочки)]]
| |
| − | * [[Хеширование корневых деревьев]]
| |
| − |
| |
| − | ===Лекции про хеши===
| |
| − | * [https://www.youtube.com/watch?v=cGfKt5q1qu8 Лекция от Павла Маврина]
| |
| − | ==Конденсация, мосты==
| |
| − | * [[Топологическая сортировка]]
| |
| − | * [[Компоненты сильной связности]]
| |
| − | * [https://algorithmica.org/ru/dfs Продвинутый DFS, конспект на Алгоритмике]
| |
| − |
| |
| − | ===Лекция про DFS===
| |
| − | * [https://www.youtube.com/watch?v=80icIrhJ6G0#t=12m09s DFS]
| |
| − | * [https://www.youtube.com/watch?v=UOr3GgJbzek&feature=youtu.be Лекция 2020-2021]
| |
| − |
| |
| − | =11. Геометрия, примитивы=
| |
| − | * [[Векторы]]
| |
| − | * [[Прямые]]
| |
| − | * [[Отрезки]]
| |
| − | * [[Окружности]]
| |
| − | * [[Многоугольники]]
| |
| − |
| |
| − | =10. Корневая декомпозиция=
| |
| − |
| |
| − | * [[Корневая декомпозиция]]
| |
| − | * [[Корневая декомпозиция на массиве]]
| |
| − | * [[Корневая на строках]]
| |
| − | * [[Корневая в задачах на графы]]
| |
| − | * [[Корневая по запросам]]
| |
| − | * [[Алгоритм Мо]]
| |
| − | * [[Подбор констант]]
| |
| − |
| |
| − | =9. LCA=
| |
| − | ===Вспомогательная структура===
| |
| − | *[[Sparse Table]]
| |
| − | ===LCA===
| |
| − | *[[LCA]]
| |
| − | *[[Эйлеров обход]]
| |
| − | ===Методы===
| |
| − | *[[Двоичные подъемы]]
| |
| − | *[[Решение с помощью Эйлерова обхода]]
| |
| − |
| |
| − | =8. СНМ и остовные деревья=
| |
| − | * [[СНМ]]
| |
| − | ===Остовные деревья===
| |
| − | * [[Лемма о безопасном ребре]]
| |
| − | * [[Алгоритм Краскала]]
| |
| − | * [[Алгоритм Прима]]
| |
| − |
| |
| − | ===Видео по теме===
| |
| − |
| |
| − | * [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 Алгоритм Прима]
| |
| − |
| |
| − | =7. Кратчайшие пути=
| |
| − | * [[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 Форд-Беллман и Флойд]
| |
| − |
| |
| − | =6. Математика=
| |
| − |
| |
| − | * [[Базовая математика]]
| |
| − | * [[Теория чисел]]
| |
| − | * [[Комбинаторика]]
| |
| − | * [[Теория вероятностей]]
| |
| − |
| |
| − | =5. С++ и базовые структуры данных=
| |
| − |
| |
| − | ====Базовые структуры данных====
| |
| − | * [[Vector]]
| |
| − | * [[Стек]]
| |
| − | * [[Очередь]]
| |
| − | * [[Дек]]
| |
| − | * [[Куча(Очередь с приоритетами)]]
| |
| − | * [[Списки]]
| |
| − |
| |
| − | ====С++====
| |
| − |
| |
| − | * [[Итератор]]
| |
| − | * [[Multiset]]
| |
| − | * [[Set]]
| |
| − | * [[Map]]
| |
| − | * [[Ускорение ввода-вывода]]
| |
| − | * [[Полезные встроенные функции]]
| |
| − | * [[pbds]]
| |
| − | * [[Бинпоиски]]
| |
| − | * [[Подводные камни]]
| |
| − | * [[UB]]
| |
| − |
| |
| − | =4. Динамическое программирование=
| |
| − |
| |
| − | * [[Основы ДП]]
| |
| − | * [[План ДП]]
| |
| − | * [[Одномерное ДП]]
| |
| − | * [[Двумерное ДП]]
| |
| − | * [[Восстановление ответа: через массив динамики и через массив предков.]]
| |
| − | * [[Ленивая динамика.]]
| |
| − | * [[Рюкзак]]
| |
| − | * [[Динамика по префиксу и значению последнего элемента]]
| |
| − | * [[НВП]]
| |
| − | * [[НОП]]
| |
| − |
| |
| − | ==Видео по теме==
| |
| − |
| |
| − | * [https://www.youtube.com/watch?v=LziQLB7QmAs&list=PL4_hYwCyhAvYikJXQHwKCOe1i7So13ZNc&index=6&t=0s Лекция про ДП от Саши Гришутина]
| |
| − | * [https://www.youtube.com/watch?v=q_n2vzVNXE4 Динамическое программирование от Павла Маврина]
| |
| − | * [https://www.youtube.com/watch?v=skEkTaAy8Ek НОП]
| |
| − | * [https://www.youtube.com/watch?v=skEkTaAy8Ek#t=12m09s НВП]
| |
| − | * [https://www.youtube.com/watch?v=6XHWHnvBiu4 Рюкзак]
| |
| − |
| |
| − | =3. Графы=
| |
| − |
| |
| − | * [[Основные понятия теории графов]]
| |
| − | * [[Хранение графа]]
| |
| − | * [[Обходы графа и их применения]]
| |
| − |
| |
| − | ===Видео по теме===
| |
| − |
| |
| − | * [https://www.youtube.com/watch?v=80icIrhJ6G0 Важное о графах]
| |
| − | * [https://www.youtube.com/watch?v=80icIrhJ6G0#t=12m09s DFS]
| |
| − |
| |
| − | =2. Поиски за $O(\log(n))$=
| |
| − |
| |
| − | ====Бинарный поиск====
| |
| − |
| |
| − | * [[Бинарный поиск]]
| |
| − | * [[Бинарный поиск с вещественными числами]]
| |
| − | * [[Бинарный поиск по ответу]]
| |
| − | * [[Бинарный поиск по производной]]
| |
| − | * [[Бинарный поиск для нахождения подходящей пары]]
| |
| − |
| |
| − | ====Тернарный поиск====
| |
| − | * [[Тернарный поиск]]
| |
| − |
| |
| − | ===Видео по теме===
| |
| − |
| |
| − | * [https://www.youtube.com/watch?v=Kn2DtmsN8f8 Бинарный поиск]
| |
| − | * [https://www.youtube.com/watch?v=80icIrhJ6G0#t=19m00s Вещественный бинарный поиск]
| |
| − | * [https://www.youtube.com/watch?v=80icIrhJ6G0#t=41m20s Тернарный поиск]
| |
| − |
| |
| | =1. Сортировки= | | =1. Сортировки= |
| | | | |