Решение задач олимпиадного программирования: Учебно-методическое пособие

РЕШЕНИЕ ЗАДАЧ ОЛИМПИАДНОГО ПРОГРАММИРОВАНИЯ Cодержание ВВЕДЕНИЕ 1. БАЗОВЫЕ АЛГОРИТМЫ 1.1. Алгоритм бинарного возведения в степень 1.2. Алгоритм «Решето Эратосфена» 1.3. Различные оптимизации решета Эратосфена 1.4. Числа Фибоначчи 1.5. Факториал по модулю p за O(p log(n)) 1.6. Линейные диофантовы уравнения с двумя переменными 2. АЛГОРИТМЫ НА СТРОКАХ 2.1. Префикс-функция 2.2. Алгоритмы хэширования в задачах на строки 2.3. Задачи на строках 3. ГЕОМЕТРИЯ 3.1. Линейные операции 3.2. Пересечение линии 3.3. Пересечение плоскостей 4. АЛГОРИТМЫ НА ГРАФАХ 4.1. Поиск в ширину (BFS) 4.2. Примеры решения задач с использованием алгоритма DFS 4.3. 0-1 Поиск в ширину (0-1 BFS) 4.4. Примеры решения задач с использованием алгоритма BFS 4.5. Поиск в глубину (DFS) 4.6. Классификация рёбер графа 4.7. Примеры решения задач с использованием алгоритма DFS 4.8. Алгоритм Дейкстры 4.9. Примеры решения задач с использованием алгоритма Дейкстры 4.10. Алгоритм поиска компонент связности в графе 4.11. Алгоритм топологической сортировки вершин графа 5. ВСПОМОГАТЕЛЬНЫЕ СТРУКТУРЫ ДАННЫХ 5.1. Дерево отрезков 5.2. Задача, использующая в решении дерево отрезков 5.3. Декартово дерево 6. ДИНАМИЧЕСКОЕ ПРОГРАММИРОВАНИЕ 6.1. «Разделяй и властвуй» 6.2. Динамика по профилю. Задача «Паркет» 6.3. Нахождение самой большой нулевой подматрицы 6.4. Игры на произвольных графах 7. ПОТОКИ 7.1. Алгоритм Диница для нахождения максимального потока 7.2. Поиск блокирующего потока 7.3. Единичные сети 7.4. Масштабирование потока 7.5. Реализация алгоритма Диница 7.6. Пример решения задачи 8. ПРОДВИНУТЫЕ АЛГОРИТМЫ 8.1. Быстрое преобразование Фурье 8.2. Дискретное преобразование Фурье 8.3. Применение ДПФ: быстрое умножение многочленов 8.4. Быстрое преобразование Фурье 8.5. Обратное БПФ 8.6. Теоретико-числовое преобразование 8.7. Вычисление многочленов с большими коэффициентами с помощью нескольких NTT 8.8. Примеры решения задач БИБЛИОГРАФИЧЕСКИЙ СПИСОК