Спортивное программирование : новый нижний предел соревнований по программированию

Содержание книги "Спортивное программирование : новый нижний предел соревнований по программированию"

Вступление
Предисловие
От издательства
Об авторах этой книги
Список сокращений
Глава 1. Введение
1.1. Олимпиадное программирование
1.2. Как стать конкурентоспособным
1.3. Начинаем работу: простые задачи
1.4. Задачи Ad Hoc
1.5. Решения упражнений, не помеченных звездочкой
1.6. Примечания к главе 1
Глава 2. Структуры данных и библиотеки
2.1. Общий обзор и мотивация
2.2. Линейные структуры данных – встроенные библиотеки
2.3. Нелинейные структуры данных – встроенные библиотеки
2.4. Структуры данных с реализациями библиотек, написанными авторами этой книги
2.5. Решения упражнений, не помеченных звездочкой
2.6. Примечания к главе 2
Глава 3. Некоторые способы решения задач
3.1. Общий обзор и мотивация
3.2. Полный перебор
3.3. «Разделяй и властвуй»
3.4. «Жадные» алгоритмы
3.5. Динамическое программирование
3.6. Решения упражнений, не помеченных звездочкой
3.7. Примечания к главе 3
Глава 4. Графы
4.1. Общий обзор и мотивация
4.2. Обход графа
4.3. Минимальное остовное дерево
4.4. Нахождение кратчайших путей из заданной вершины во все остальные (Single – Source Shortest Paths, SSSP)
4.5. Кратчайшие пути между всеми вершинами
4.6. Поток
4.7. Специальные графы
4.8. Решения упражнений, не помеченных звездочкой
4.9. Примечания к главе 4
Глава 5. Математика
5.1. Общий обзор и мотивация
5.2. Задачи Ad Hoc и математика
5.3. Класс Java BigInteger
5.4. Комбинаторика
5.5. Теория чисел
Глава 6. Обработка строк
6.1. Обзор и мотивация
6.2. Основные приемы и принципы обработки строк
6.3. Специализированные задачи обработки строк
6.4. Поиск совпадений в строках
6.5. Обработка строк с применением динамического программирования
6.6. Суффиксный бор, суффиксное дерево, суффиксный массив
6.7. Решения упражнений, не помеченных звездочкой
6.8. Примечания к главе
Глава 7. (Вычислительная) Геометрия
7.1. Обзор и мотивация
7.2. Основные геометрические объекты и библиотечные функции для них
7.3. Алгоритмы для многоугольников с использованием библиотечных функций
7.4. Решения упражнений, не помеченных звездочкой
7.5. Замечания к главе
Глава 8. Более сложные темы
8.1. Обзор и мотивация
8.2. Более эффективные методы поиска
8.3. Более эффективные методы динамического программирования
8.4. Декомпозиция задачи
8.5. Решения упражнений, не помеченных звездочкой
8.6. Замечания к главе
Глава 9. Малораспространенные темы
Общий обзор и мотивация
9.1. Задача 2-SAT
9.2. Задача о картинной галерее
9.3. Битоническая задача коммивояжера
9.4. Разбиение скобок на пары
9.5. Задача китайского почтальона
9.6. Задача о паре ближайших точек
9.7. Алгоритм Диница
9.8. Формулы или теоремы
9.9. Алгоритм последовательного исключения переменных, или метод Гаусса
9.10. Паросочетание в графах
9.11. Кратчайшее расстояние на сфере (ортодромия)
9.12. Алгоритм Хопкрофта–Карпа
9.13. Вершинно и реберно не пересекающиеся пути
9.14. Количество инверсий
9.15. Задача Иосифа Флавия
9.16. Ход коня
9.17. Алгоритм Косараджу
9.18. Наименьший общий предок
9.19. Создание магических квадратов (нечетной размерности)
9.20. Задача о порядке умножения матриц
9.21. Возведение матрицы в степень
9.22. Задача о независимом множестве максимального веса
9.23. Максимальный поток минимальной стоимости
9.24. Минимальное покрытие путями в ориентированном ациклическом графе
9.25. Блинная сортировка
9.26. Ро-алгоритм Полларда для разложения на множители целых чисел
9.27. Постфиксный калькулятор и преобразование выражений
9.28. Римские цифры
9.29. k-я порядковая статистика
9.30. Алгоритм ускоренного поиска кратчайшего пути
9.31. Метод скользящего окна
9.32. Алгоритм сортировки с линейным временем работы
9.33. Структура данных «разреженная таблица»
9.34. Задача о ханойских башнях
9.35. Замечания к главе
Приложение А. uHunt
Приложение В. Благодарности
Список используемой литературы
Предметный указатель