О курсе
Курс для тех, кто участвовал в олимпиадах и владеет языком С++. Вы узнаете о библиотеке STL, контейнерах vector, string, set, map и других возможностях С++, которые используются в задачах. Будут изучены все необходимые для успешного выступления на олимпиадах алгоритмы, такие как алгоритмы на графах, арифметические алгоритмы, строковые алгоритмы, геометрические алгоритмы. Будут разобраны задачи динамического программирования и изучены структуры данных.
1 Язык C++
Типы данных
Битовые операции
Ввод-вывод данных. Работа с файлами
Структуры, классы
Строки
Контейнеры STL
Встроенные сортировки
2 Арифметические алгоритмы
Проверка на простоту
Факторизация
Алгоритм Евклида
Решето Эратосфена
Быстрое возведение в степень
3 Алгоритмы поиска
Бинарный поиск
Тернарный поиск
Метод двух указателей
Метод сканирующей прямой
4 Динамическое программирование
Динамическое программирование
Восстановление ответа
Задачи НОП, НВП, НОВП
Динамическое программирование по подстрокам, поддеревьям, подмножествам, профилю
Метод Convex Hull Trick
5 Структуры данных
Префиксные суммы
Sqrt-декомпозиция
Sparse table
Дерево отрезков
Массовые операции в дереве отрезков
Декартово дерево
Декартово дерево по неявному ключу
Дерево merge-sort
Метод сканирующей прямой и дерева отрезков
Дерево Фенвика
Система непересекающихся множеств
6 Алгоритмы на графах
Хранение графов
DFS, топологическая сортировка, конденсация, поиск мостов и точек сочленения
BFS
Алгоритм Дейкстры
Алгоритм Форда-Беллмана
Алгоритм Флойда
Поиск минимального остовного дерева
Задача LCA
Поиск паросочетаний
7 Вычислительная геометрия
Структура точки
Скалярное и векторное произведение
Площадь многоугольника, задача про точку внутри многоугольника
Прямые, окружности
8 Строковые алгоритмы
Хэширование
9 Комбинаторные алгоритмы
Генерация всех комбинаторных объектов
Получение объекта по номеру и номера по объекту
Получение следующего объекта
Последнее редактирование модератором:
- Статус
- В этой теме нельзя размещать новые ответы.