Подготовка
Полезная литература
На этой странице собраны материалы, которые помогут тебе в подготовке к отборочным и финальному раундам
Для эффективной подготовки рекомендуем ознакомиться с задачами и разборами прошлых лет, а также принятие участие в ознакомительном раунде.
«Олимпиадное программирование» (Антти Лааксонен)
«Competitive Programming 3.» (Halim S., Halim F.)
«Справочник спортивного программиста. Часть 1» (В.А. Демиденко, М.Д. Кормышов)
«Программирование — это так просто. Программирование — это так сложно. Современный учебник программирования». (Е.В. Андреева)
«Competitive Programming 3.» (Halim S., Halim F.)
«Справочник спортивного программиста. Часть 1» (В.А. Демиденко, М.Д. Кормышов)
«Программирование — это так просто. Программирование — это так сложно. Современный учебник программирования». (Е.В. Андреева)
Онлайн-курсы
Старт в олимпиадном программировании с VK Education
Старт в олимпиадном программировании с VK Education
Программирование для школьников от VK Education
Программирование для школьников от VK Education
Алгоритмы: теория и практика
Алгоритмы: теория и практика
Быстрый старт в спортивное программирование
Быстрый старт в спортивное программирование
Основы С/C++ для спортивного программирования
Основы С/C++ для спортивного программирования
Быстрый старт в искусственный интеллект
Быстрый старт в искусственный интеллект
Для успешного участия в олимпиаде, полезно повторить следующие темы
Тема 1. Теория чисел.
Модульная арифметика. Рекурсивные алгоритмы. Факторизация целых чисел. Разложение числа на множители. НОД, НОК. Алгоритм Евклида. Решето Эратосфена. Сравнение чисел по модулю. Вычисление факториала по модулю.
Тема 2. Рекурсия.
Генерация перестановок. Расширенный алгоритм Евклида. Тест простоты Ферма (Малая теорема Ферма). Быстрое возведение в степень по модулю.
Тема 3. Сортировки и поиск.
Сортировка слиянием, быстрая сортировка. Подсчёт количества инверсий. Вещественный бинарный поиск. Целочисленный бинарный поиск. Бинарный поиск по ответу. Тернарный поиск.
Тема 4. Динамическое программирование.
Динамическое программирование один параметр. Динамическое программирование два параметра параметр. Наибольшая неубывающая подпоследовательность. Наибольшая общая подпоследовательность. Задача о рюкзаке. Динамическое программирование на подмножествах и подотрезках. Динамическое программирование на поддеревьях.
Тема 5. Структуры данных и их применение.
Стек. Очередь. Дек. Правильные скобочные последовательности. Префиксная нотация.
Тема 6. Строки.
Хэш функция. Z-функция. Префикс-функция. Бор. Суффиксные массивы. Алгоритм Ахо- Корасика.
Тема 7. Запросы на подотрезках массива. Бинарная куча. Дерево поиска. Задача RMQ и RSQ.
Массив частичных сумм. Sqrt-декомпозиция. Разреженная таблица (sparse table). Дерево отрезков. Дерево отрезков с массовыми обновлениями. Двоичное дерево поиска. АВЛ - дерево. Красно-черное дерево. Декартово дерево по явному и не явному ключу. Дерево Фенвика.
Тема 8. Теория графов.
Основные понятия: граф, дерево. Представление сетей в компьютере. Поиск в глубину. Поиск в ширину. Диаметр дерева. Радиус дерева. Центр дерева. Система непересекающихся множеств. Задача нахождения минимального остовного дерева. Алгоритм Краскала. Задача нахождения дерева кратчайших расстояний. Алгоритм Дейкстры. Алгоритм Беллмана-Форда. Алгоритм Флойда.