ТВОЙ BZFAR
Главная » Статьи » Algorithms & Programming » Algorithms
Путь к олимпиадному программированию (планирование)
BZFAR · от первых задач к сложным алгоритмам

Путь к олимпиадному программированию

Последовательность подготовки по книге Антти Лааксонена: двигайтесь по главам, разбирайте примеры и проверяйте каждый новый приём на задачах.

  • изучай
  • программируй
  • решай контесты

Как работать с темой: прочитайте главу, воспроизведите алгоритмы самостоятельно, решите задачи и разберите случаи, на которых решение ошибается. Ссылки на готовые материалы сайта добавлены к соответствующим главам.

Начните с основы

Разберитесь с форматом соревнований, научитесь писать и оценивать решения.

Глава 03

Эффективность

  • Временная сложность
  • Сравнение алгоритмов
  • Примеры оценки решений
Разбор главы на сайте готовится

Освойте основные приёмы

Сортировка, структуры данных и первые задачи на динамику.

Глава 04

Сортировка и поиск

  • Алгоритмы сортировки
  • Задачи с сортировкой
  • Двоичный поиск
Разбор главы на сайте готовится
Глава 05

Структуры данных

  • Векторы
  • Множества и отображения
  • Очереди с приоритетом
Разбор главы на сайте готовится
Глава 06

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

  • Оптимальные решения
  • Подсчёт решений
  • Подпоследовательности, сетки, рюкзак
Разбор главы на сайте готовится

Перейдите к графам

Изучите обходы, маршруты и методы ускорения алгоритмов.

Глава 07

Алгоритмы на графах

  • Представление графа
  • DFS и BFS
  • Кратчайшие пути, DAG, остовные деревья
Тренажёр DFS
Глава 08

Избранные вопросы проектирования алгоритмов

  • Параллельный просмотр разрядов
  • Два указателя и скользящее окно
  • Троичный поиск
Разбор главы на сайте готовится

Углубите работу со структурами

Запросы к массивам и деревьям, затем математические инструменты.

Глава 09

Запросы по диапазону

  • Запросы суммы и минимума
  • Двоичное индексное дерево
  • Дерево отрезков
Разбор главы на сайте готовится
Глава 10

Алгоритмы на деревьях

  • Обход и диаметр дерева
  • Предки, поддеревья, пути
  • Декомпозиция дерева
Разбор главы на сайте готовится
Глава 11

Математика

  • Теория чисел и комбинаторика
  • Матрицы и вероятность
  • Теория игр
Разбор главы на сайте готовится

Изучите специальные темы

Материал для задач, в которых базовых приёмов уже недостаточно.

Глава 12

Дополнительные алгоритмы на графах

  • Сильная связность
  • Эйлеровы и гамильтоновы пути
  • Максимальный поток
Разбор главы на сайте готовится
Глава 13

Геометрия

  • Точки, прямые и площади
  • Заметающая прямая
  • Ближайшая пара и выпуклая оболочка
Разбор главы на сайте готовится
Глава 14

Алгоритмы работы со строками

  • Префиксное дерево
  • Хеширование и Z-алгоритм
  • Суффиксные массивы
Разбор главы на сайте готовится
Глава 15

Дополнительные темы

  • Алгоритм Мо
  • Ленивое распространение
  • Оптимизация динамического программирования
Разбор главы на сайте готовится

Основа маршрута: Антти Лааксонен, «Олимпиадное программирование. Изучение и улучшение алгоритмов на соревнованиях» (ДМК Пресс, 2018). 

Категория: Algorithms | Добавил: bzfar77 (Сегодня)
Просмотров: 5 | Теги: алгоритмы, подготовка, Графы, олимпиадное программирование, структуры данных | Рейтинг: 0.0/0
Всего комментариев: 0
Войдите:
avatar