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

Материал из Algocode wiki
Перейти к: навигация, поиск
 
(не показаны 42 промежуточные версии 3 участников)
Строка 1: Строка 1:
<p style="font-size: 14pt">[https://algocode.ru/bp2019/ Страница на алгокоде]</p>
+
=12. Хеши=
=6. Математика=
+
==Полиномиальный хеш==
 +
* [[Полиномиальное хеширование строк]]
 +
* [[Сравнение строк с помощью хешей]]
 +
* [[Хеширование матриц]]
 +
===Коллизии===
 +
* [https://codeforces.com/blog/entry/4898?locale=ru Строки Туэ-Морса ]
 +
* [https://codeforces.com/blog/entry/60442 Обзорная статья о взломах полиномиальных хешей]
 +
* [https://en.wikipedia.org/wiki/Largest_differencing_method#Two-way_partitioning Алгоритм Кармаркара-Карпа для поиска разбиения множества на две части с минимальной разностью]
  
 +
==Хеш-таблицы==
 +
* [https://codeforces.com/blog/entry/60737 Встроенные таблицы из gnu pbds]
 +
* [[Хеш-таблицы (открытый ключ)]]
 +
* [[Хеш-таблицы (цепочки)]]
 +
 +
== Ещё про хеши ==
 +
* [[Хеширование множеств (с точностью до перестановки)]]
 +
* [[Хеширование корневых деревьев]]
 +
* [https://www.imsc.res.in/~vikram/DiscreteMaths/2011/tree.pdf Изоморфизм произвольных деревьев с помощью хеширования ]
 +
 +
=11. СНМ и остовные деревья=
 +
* [[СНМ]]
 +
===Остовные деревья===
 +
* [[Лемма о безопасном ребре]]
 +
* [[Алгоритм Краскала]]
 +
* [[Алгоритм Прима]]
 +
 +
===Видео по теме===
 +
 +
* [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 Алгоритм Прима]
 +
 +
 +
=10. Корневая декомпозиция=
 +
 +
* [[Корневая декомпозиция]]
 +
* [[Корневая декомпозиция на массиве]]
 +
* [[Корневая на строках]]
 +
* [[Корневая в задачах на графы]]
 +
* [[Корневая по запросам]]
 +
* [[Алгоритм Мо]]
 +
* [[Подбор констант]]
 +
* [[set за O(1) на вставку и корень на взятие минимума]]
 +
 +
=9. Геометрия-1=
 +
* [[Векторы]]
 +
* [[Прямые]]
 +
* [[Отрезки]]
 +
* [[Окружности]]
 +
 +
===Видео по теме===
 +
* [https://t.me/c/1508532677/56 запись лекции 2021 года]
 +
 +
=8. Математика=
 
* [[Базовая математика]]
 
* [[Базовая математика]]
 
* [[Теория чисел]]
 
* [[Теория чисел]]
 
* [[Комбинаторика]]
 
* [[Комбинаторика]]
* [[Теория вероятностей]]
 
  
=5. С++ и базовые структуры данных=
+
=7. Кратчайшие пути=
 +
* [[BFS]]
 +
* [[0-1 BFS]]
 +
* [[1-k BFS]]
 +
* [[Алгоритм Форда-Беллмана]]
 +
* [[Алгоритм Дейкстры]]
 +
* [[Алгоритм Флойда]]
  
====Базовые структуры данных====
+
===Видео по теме===
* [[Vector]]
 
* [[Стек]]
 
* [[Очередь]]
 
* [[Дек]]
 
* [[Куча(Очередь с приоритетами)]]
 
* [[Списки]]
 
  
====С++====
+
* [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 Форд-Беллман и Флойд]
  
* [[Итератор]]
 
* [[Multiset]]
 
* [[Set]]
 
* [[Map]]
 
* [[Ускорение ввода-вывода]]
 
* [[Полезные встроенные функции]]
 
* [[pbds]]
 
* [[Бинпоиски]]
 
* [[Подводные камни]]
 
* [[UB]]
 
  
=4. Динамическое программирование=
+
=6. Динамическое программирование=
  
 
* [[Основы ДП]]
 
* [[Основы ДП]]
Строка 42: Строка 88:
 
* [[НВП]]
 
* [[НВП]]
 
* [[НОП]]
 
* [[НОП]]
 +
* [[ДП по подотрезкам]]
  
 
==Видео по теме==
 
==Видео по теме==
  
 +
* [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=LziQLB7QmAs&list=PL4_hYwCyhAvYikJXQHwKCOe1i7So13ZNc&index=6&t=0s Лекция про ДП от Саши Гришутина]
 
* [https://www.youtube.com/watch?v=q_n2vzVNXE4 Динамическое программирование от Павла Маврина]
 
* [https://www.youtube.com/watch?v=q_n2vzVNXE4 Динамическое программирование от Павла Маврина]
Строка 51: Строка 99:
 
* [https://www.youtube.com/watch?v=6XHWHnvBiu4 Рюкзак]
 
* [https://www.youtube.com/watch?v=6XHWHnvBiu4 Рюкзак]
  
=3. Графы=
+
=5. Линейные алгоритмы =
 +
 
 +
== Видео ==
 +
[https://t.me/c/1508532677/39 лекция 2021-2022]
 +
 
 +
=4. С++ и базовые структуры данных=
 +
 
 +
====Базовые структуры данных====
 +
* [[Vector]]
 +
* [[Стек]]
 +
* [[Очередь]]
 +
* [[Дек]]
 +
* [[Куча(Очередь с приоритетами)]]
 +
* [[Списки]]
 +
 
 +
====С++====
 +
 
 +
* [[Итератор]]
 +
* [[Multiset]]
 +
* [[Set]]
 +
* [[Map]]
 +
* [[Ускорение ввода-вывода]]
 +
* [[Полезные встроенные функции]]
 +
* [[pbds]]
 +
* [[Бинпоиски]]
 +
* [[Подводные камни]]
 +
* [[UB]]
 +
 
 +
 
 +
=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 Важное о графах]
 
* [https://www.youtube.com/watch?v=80icIrhJ6G0#t=12m09s DFS]
 
* [https://www.youtube.com/watch?v=80icIrhJ6G0#t=12m09s DFS]
Строка 74: Строка 152:
 
====Тернарный поиск====
 
====Тернарный поиск====
 
* [[Тернарный поиск]]
 
* [[Тернарный поиск]]
 +
* [[Вложенные тернарные поиски]]
  
 
===Видео по теме===
 
===Видео по теме===
 
+
* [https://youtu.be/eCctYpFF3xI Лекция от 2021 года]
 
* [https://www.youtube.com/watch?v=Kn2DtmsN8f8 Бинарный поиск]
 
* [https://www.youtube.com/watch?v=Kn2DtmsN8f8 Бинарный поиск]
 
* [https://www.youtube.com/watch?v=80icIrhJ6G0#t=19m00s Вещественный бинарный поиск]
 
* [https://www.youtube.com/watch?v=80icIrhJ6G0#t=19m00s Вещественный бинарный поиск]
Строка 106: Строка 185:
 
* [[Количество инверсий]]
 
* [[Количество инверсий]]
 
* [[K-я порядковая статистика]]
 
* [[K-я порядковая статистика]]
 +
 +
=== Видео по теме ===
 +
* [https://www.youtube.com/watch?v=BwzESzVxAHQ&ab_channel=AleksandrGrishutin Лекция 2021 года]

Текущая версия на 16:24, 23 января 2022

12. Хеши

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

Коллизии

Хеш-таблицы

Ещё про хеши

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

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

Видео по теме


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

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

Видео по теме

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

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

Видео по теме


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

Видео по теме

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

Видео

лекция 2021-2022

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

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

С++


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

Видео по теме

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

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

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

Видео по теме

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

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

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

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

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

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

Видео по теме