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

Материал из Algocode wiki
Перейти к: навигация, поиск
 
(не показано 107 промежуточных версий 3 участников)
Строка 1: Строка 1:
−
<p style="font-size: 14pt">[https://algocode.ru/bp2019/ Страница на алгокоде]</p>
+
=21. DFS-2=
−
=1. Сортировки=
+
* [[Компоненты сильной связности]]
 +
==Алгоритмика==
 +
* [https://ru.algorithmica.org/cs/graph-traversals/scc/ Компоненты сильной связности]
 +
* [https://ru.algorithmica.org/cs/graph-traversals/bridges/ Мосты и точки сочленения]
 +
 
 +
=20. ДП по цифрам=
 +
* [https://t.me/c/1508532677/129 Лекция 2021-2022]
 +
* [[Динамическое программирование по цифрам]]
 +
* [[Примеры задач на ДП по цифрам]]
 +
* [[Восстановление k-го числа с особым свойством]]
 +
==Доп.материал==
 +
* [[MITM в задачах на числа]]
 +
 
 +
=19. Дерево Фенвика=
 +
* [https://t.me/c/1508532677/128 Лекция 2021-2022]
 +
* [https://ru.algorithmica.org/cs/range-queries/fenwick/ Конспект с Алгоритмики]
 +
* [[Дерево Фенвика]]
 +
 
 +
=18. Декартово дерево=
 +
* [https://t.me/c/1508532677/127 Лекция 2021-2022]
 +
* [https://ru.algorithmica.org/cs/tree-structures/treap/ Конспект с Алгоритмики]
 +
* [[Декартово дерево]]
 +
 
 +
=17. Префикс/z-функции и бор=
 +
* [https://t.me/c/1508532677/125 лекция 2021-2022]
 +
* [https://algorithmica.org/ru/string-searching Конспект с алгоритмики про функции]
 +
* [[Z-функция]]
 +
* [[Бор]]
 +
* [[Цифровой бор]]
 +
 
 +
=16. Геометрия-2=
 +
* [https://t.me/c/1508532677/119 Лекция 2021-2022]
 +
* [[Выпуклая оболочка]]
 +
* [[Поиск двух ближайших точек]]
 +
* [https://algocode.ru/files/course_aspb2019/main.pdf Геометрия: вспомнить всё]
 +
 
 +
=15. ДП по подмножествам=
 +
* [https://t.me/c/1508532677/107 Лекция 2021-2022]
 +
* [https://t.me/c/1508532677/106 Пост в канале с материалами лекции]
 +
 
 +
=14. Хеши=
 +
* [https://t.me/c/1508532677/100 лекция 2021-2022]
 +
 
 +
==Полиномиальный хеш==
 +
* [[Полиномиальное хеширование строк]]
 +
* [[Сравнение строк с помощью хешей]]
 +
* [[Хеширование матриц]]
 +
===Коллизии===
 +
* [https://codeforces.com/blog/entry/4898?locale=ru Строки Туэ-Морса ]
 +
* [https://codeforces.com/blog/entry/60442 Обзорная статья о взломах полиномиальных хешей]
 +
* [https://codeforces.com/blog/entry/1729?locale=ru&mobile=true#comment-32989 Как умножить два long long числа по модулю третьего long long числа]
 +
* [https://en.wikipedia.org/wiki/Largest_differencing_method#Two-way_partitioning Алгоритм Кармаркара-Карпа для поиска разбиения множества на две части с минимальной разностью]
 +
 
 +
==Хеш-таблицы==
 +
* [https://codeforces.com/blog/entry/60737 Встроенные таблицы из gnu pbds]
 +
* [[Хеш-таблицы (открытый ключ)]]
 +
* [[Хеш-таблицы (цепочки)]]
  
−
====Анализ времени и памяти====
+
== Ещё про хеши ==
−
* [[O-нотация light version]]
+
* [[Хеширование множеств (с точностью до перестановки)]]
−
* [[Работа со временем и памятью]]
+
* [[Хеширование корневых деревьев]]
 +
* [https://www.imsc.res.in/~vikram/DiscreteMaths/2011/tree.pdf Изоморфизм произвольных деревьев с помощью хеширования ]
  
−
====Квадратичные сортировки====
+
=13. Дерево отрезков=
 +
* [[Дерево отрезков]]
 +
* [[А что еще можно хранить в до?]]
 +
* [[Спуск по дереву отрезков]]
 +
* [[Отложенные операции]]
 +
* [[Динамическое(Неявное) Дерево Отрезков]]
  
−
* [[Сортировка пузырьком]]
+
===Видео по теме===
−
* [[Сортировка выбором]]
+
* [https://t.me/c/1508532677/90 лекция 2021-2022]
−
* [[Сортировка вставками]]
 
  
−
====Сортировки за $n\log{n}$====
+
=12. LCA=
 +
* [https://t.me/c/1508532677/69 лекция 2021-2022]
 +
===Вспомогательная структура===
 +
*[[Sparse Table]]
 +
===LCA===
 +
*[[LCA]]
 +
*[[Эйлеров обход]]
 +
===Методы===
 +
*[[Двоичные подъемы]]
 +
*[[Решение с помощью Эйлерова обхода]]
  
−
* [[Сортировка слиянием]]
+
=11. СНМ и остовные деревья=
−
* [[Быстрая сортировка]]
+
* [[СНМ]]
 +
===Остовные деревья===
 +
* [[Лемма о безопасном ребре]]
 +
* [[Алгоритм Краскала]]
 +
* [[Алгоритм Прима]]
  
−
====Другие сортировки====
+
===Видео по теме===
  
−
* [[Сортировка подсчетом]]
+
* [https://t.me/c/1508532677/60 лекция 2021-2022]
 +
* [https://www.youtube.com/watch?v=VmNPG__osBE MST от Павла Маврина]
  
−
====Связанные задачи====
 
  
−
* [[Количество инверсий]]
+
=10. Корневая декомпозиция=
−
* [[K-я порядковая статистика]]
+
* [https://t.me/c/1508532677/57 лекция 2021-2022]
 +
* [[Корневая декомпозиция]]
 +
* [[Корневая декомпозиция на массиве]]
 +
* [[Корневая на строках]]
 +
* [[Корневая в задачах на графы]]
 +
* [[Корневая по запросам]]
 +
* [[Алгоритм Мо]]
 +
* [[Подбор констант]]
 +
* [[set за O(1) на вставку и корень на взятие минимума]]
  
−
=2. Поиски за $O(\log(n))$=
+
=9. Геометрия-1=
 +
* [https://t.me/c/1508532677/56 лекция 2021-2022]
 +
* [[Векторы]]
 +
* [[Прямые]]
 +
* [[Отрезки]]
 +
* [[Окружности]]
  
−
====Бинарный поиск====
+
=8. Математика=
 +
* [https://www.youtube.com/watch?v=9nYnS8mPFa4 лекция 2021-2022]
 +
* [[Базовая математика]]
 +
* [[Теория чисел]]
 +
* [[Комбинаторика]]
  
−
* [[Бинарный поиск]]
+
=7. Кратчайшие пути=
−
* [[Бинарный поиск с вещественными числами]]
+
* [https://t.me/c/1508532677/48 лекция 2021-2022]
−
* [[Бинарный поиск по ответу]]
+
* [[BFS]]
−
* [[Бинарный поиск по производной]]
+
* [[0-1 BFS]]
−
* [[Бинарный поиск для нахождения подходящей пары]]
+
* [[1-k BFS]]
 +
* [[Алгоритм Форда-Беллмана]]
 +
* [[Алгоритм Дейкстры]]
 +
* [[Алгоритм Флойда]]
  
−
====Тернарный поиск====
+
===Видео по теме===
−
* [[Тернарный поиск]]
 
  
−
=3. Графы=
+
* [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 Форд-Беллман и Флойд]
  
−
* [[Основные понятия теории графов]]
 
−
* [[Хранение графа]]
 
−
* [[Обходы графа и их применения]]
 
  
−
=4. Динамическое программирование=
+
=6. Динамическое программирование=
  
 
* [[Основы ДП]]
 
* [[Основы ДП]]
Строка 57: Строка 150:
 
* [[НВП]]
 
* [[НВП]]
 
* [[НОП]]
 
* [[НОП]]
 +
* [[ДП по подотрезкам]]
 +
 +
==Видео по теме==
 +
 +
* [https://t.me/c/1508532677/43 лекция 2021-2022]
 +
* [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 Рюкзак]
 +
 +
=5. Линейные алгоритмы =
 +
 +
== Видео ==
 +
[https://t.me/c/1508532677/39 лекция 2021-2022]
  
−
=5. С++ и базовые структуры данных=
+
=4. С++ и базовые структуры данных=
  
 
====Базовые структуры данных====
 
====Базовые структуры данных====
Строка 81: Строка 189:
 
* [[UB]]
 
* [[UB]]
  
−
=6. Корневая декомпозиция=
 
  
−
* [[Корневая декомпозиция]]
+
=3. Графы и стресс-тестирование =
−
* [[Корневая декомпозиция на массиве]]
+
 
−
* [[Корневая на строках]]
+
* [[Основные понятия теории графов]]
−
* [[Корневая в задачах на графы]]
+
* [[Хранение графа]]
−
* [[Корневая по запросам]]
+
* [[Обходы графа и их применения]]
−
* [[Алгоритм Мо]]
+
* [https://t.me/c/1578563708/1727 Пример стресс-теста]
−
* [[Подбор констант]]
+
 
 +
===Видео по теме===
 +
* [https://youtu.be/5FrtL-GSzLg Лекция от 2021 года]
 +
* [https://www.youtube.com/watch?v=80icIrhJ6G0 Важное о графах]
 +
* [https://www.youtube.com/watch?v=80icIrhJ6G0#t=12m09s DFS]
 +
 
 +
=2. Поиски за $O(\log(n))$=
 +
 
 +
====Бинарный поиск====
 +
 
 +
* [[Бинарный поиск]]
 +
* [[Бинарный поиск с вещественными числами]]
 +
* [[Бинарный поиск по ответу]]
 +
* [[Бинарный поиск по производной]]
 +
* [[Бинарный поиск для нахождения подходящей пары]]
 +
 
 +
====Тернарный поиск====
 +
* [[Тернарный поиск]]
 +
* [[Вложенные тернарные поиски]]
 +
 
 +
===Видео по теме===
 +
* [https://youtu.be/eCctYpFF3xI Лекция от 2021 года]
 +
* [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. Сортировки=
 +
 
 +
====Анализ времени и памяти====
 +
* [[O-нотация light version]]
 +
* [[Работа со временем и памятью]]
 +
 
 +
====Квадратичные сортировки====
 +
 
 +
* [[Сортировка пузырьком]]
 +
* [[Сортировка выбором]]
 +
* [[Сортировка вставками]]
 +
 
 +
====Сортировки за $n\log{n}$====
 +
 
 +
* [[Сортировка слиянием]]
 +
* [[Быстрая сортировка]]
  
−
=7. Математика=
+
====Другие сортировки====
  
−
* [[Базовая математика]]
+
* [[Сортировка подсчетом]]
−
* [[Теория чисел]]
 
−
* [[Комбинаторика]]
 
−
* [[Теория вероятностей]]
 
−
* [[Матрицы]]
 
  
−
=8. Кратчайшие пути=
+
====Связанные задачи====
−
* [[BFS]]
 
−
* [[0-1 BFS]]
 
−
* [[1-k BFS]]
 
−
* [[Алгоритм Форда-Беллмана]]
 
−
* [[Алгоритм Дейкстры]]
 
  
−
=9. СНМ и остовные деревья=
+
* [[Количество инверсий]]
−
* [[СНМ]]
+
* [[K-я порядковая статистика]]
−
====Остовные деревья====
 
−
* [[Лемма о безопасном ребре]]
 
−
* [[Алгоритм Краскала]]
 
−
* [[Алгоритм Прима]]
 
  
−
=10. LCA=
+
=== Видео по теме ===
−
===Вспомогательная структура===
+
* [https://www.youtube.com/watch?v=BwzESzVxAHQ&ab_channel=AleksandrGrishutin Лекция 2021 года]
−
*[[Sparse Table]]
 
−
===Методы===
 
−
*[[Двоичные подъемы]]
 
−
*[[Эйлеров обход]]
 

Текущая версия на 15:54, 19 марта 2022

Содержание

21. DFS-2

Алгоритмика

20. ДП по цифрам

Доп.материал

19. Дерево Фенвика

18. Декартово дерево

17. Префикс/z-функции и бор

16. Геометрия-2

15. ДП по подмножествам

14. Хеши

Полиномиальный хеш

Коллизии

Хеш-таблицы

Ещё про хеши

13. Дерево отрезков

Видео по теме

12. LCA

Вспомогательная структура

LCA

Методы

11. СНМ и остовные деревья

Остовные деревья

Видео по теме


10. Корневая декомпозиция

9. Геометрия-1

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

7. Кратчайшие пути

Видео по теме


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

Видео по теме

5. Линейные алгоритмы

Видео

лекция 2021-2022

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

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

С++


3. Графы и стресс-тестирование

Видео по теме

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

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

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

Видео по теме

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

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

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

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

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

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

Видео по теме

Источник — http://wiki.algocode.ru/index.php?title=Параллель_B%27&oldid=1742