Национальный цифровой ресурс Руконт - межотраслевая электронная библиотека (ЭБС) на базе технологии Контекстум (всего произведений: 638282)
Контекстум
Электро-2024

Спортивное программирование (4000,00 руб.)

0   0
Первый авторХалим
АвторыХалим Ф.
ИздательствоМ.: ДМК Пресс
Страниц606
ID795347
АннотацияКнига содержит задачи по программированию, аналогичные тем, которые используются на соревнованиях мирового уровня (в частности, ACM ICPC и IOI). Помимо задач разного типа приводятся общие рекомендации для подготовки к соревнованиям, касающиеся классификации заданий, анализа алгоритмов и пр. Кроме стандартных тем (структуры данных и библиотеки, графы, математика, вычислительная геометрия) авторы затрагивают и малораспространенные — им посвящена отдельная глава. В конце каждой главы приводятся краткие решения заданий, не помеченных звездочкой, или даются подсказки к ним. Задания сложного уровня (помеченные звездочкой) требуют самостоятельной проработки. Издание адресовано читателям, которые готовятся к соревнованиям по программированию или просто любят решать задачи по информатике. Для изучения материала требуются элементарные знания из области методологии программирования и знакомство хотя бы с одним из двух языков программирования -C/C++ или Java.
ISBN978-5-97060-758-9
УДК004.02, 004.424
ББК22.18
Халим, С. Спортивное программирование / Ф. Халим; С. Халим .— Москва : ДМК Пресс, 2020 .— 606 с. — ISBN 978-5-97060-758-9 .— URL: https://rucont.ru/efd/795347 (дата обращения: 09.06.2024)

Предпросмотр (выдержки из произведения)

Спортивное_программирование.pdf
Стр.5
Стр.6
Стр.7
Стр.8
Стр.9
Стр.10
Стр.11
Спортивное_программирование.pdf
УДК 004.02, 004.424 ББК 22.18 Х17 Х17 Спортивное программирование / пер. с англ. Н. Б. Желновой, А. В. Снастина. – М.: ДМК Пресс, 2020. – 604 с.: ил. Халим С., Халим Ф. ISBN 978-5-97060-758-9 Книга содержит задачи по программированию, аналогичные тем, которые используются на соревнованиях мирового уровня (в частности, ACM ICPC и IOI). Помимо задач разного типа приводятся общие рекомендации для подготовки к соревнованиям, касающиеся классификации заданий, анализа алгоритмов и пр. Кроме стандартных тем (структуры данных и библиотеки, графы, математика, вычислительная геометрия) авторы затрагивают и малораспространенные – им посвящена отдельная глава. В конце каждой главы приводятся краткие решения заданий, не помеченных звездочкой, или даются подсказки к ним. Задания сложного уровня (помеченные звездочкой) требуют самостоятельной проработки. Издание адресовано читателям, которые готовятся к соревнованиям по программированию или просто любят решать задачи по информатике. Для изучения материала требуются элементарные знания из области методологии программирования и знакомство хотя бы с одним из двух языков программирования – C/C++ или Java. УДК 004.02, 004.424 ББК 22.18 Russian­language edition copyright © 2020 by DMK Press. All rights reserved. Все права защищены. Любая часть этой книги не может быть воспроизведена в какой бы то ни было форме и какими бы то ни было средствами без письменного разрешения владельцев авторских прав. ISBN 978­5­97060­758­9 (рус.) © Steven Halim, Felix Halim, 2013 © Оформление, издание, перевод, ДМК Пресс, 2020
Стр.5
Содержание Вступление ................................................................................................................... 11 Предисловие ............................................................................................................... 13 От издательства ......................................................................................................... 27 Об авторах этой книги .......................................................................................... 28 Список сокращений ................................................................................................ 30 Глава 1. Введение ..................................................................................................... 32 1.1. Олимпиадное программирование ....................................................................... 32 1.2. Как стать конкурентоспособным ......................................................................... 35 1.2.1. Совет 1: печатайте быстрее! .......................................................................... 36 1.2.2. Совет 2: быстро классифицируйте задачи ................................................. 37 1.2.3. Совет 3: проводите анализ алгоритмов ...................................................... 40 1.2.4. Совет 4: совершенствуйте свои знания языков программирования .................................................................................................... 46 1.2.5. Совет 5: овладейте искусством тестирования кода ................................. 48 1.2.6. Совет 6: практикуйтесь и еще раз практикуйтесь! .................................. 52 1.2.7. Совет 7: организуйте командную работу (для ICPC) ............................... 53 1.3. Начинаем работу: простые задачи ...................................................................... 54 1.3.1. Общий анализ олимпиадной задачи по программированию .............. 54 1.3.2. Типичные процедуры ввода/вывода ........................................................... 55 1.3.3. Начинаем решать задачи ............................................................................... 57 1.4. Задачи Ad Hoc ........................................................................................................... 60 1.5. Решения упражнений, не помеченных звездочкой ........................................ 68 1.6. Примечания к главе 1 .............................................................................................. 73 Глава 2. Структуры данных и библиотеки ................................................. 76 2.1. Общий обзор и мотивация ................................................................................... 76 2.2. Линейные структуры данных – встроенные библиотеки .............................. 79 2.3. Нелинейные структуры данных – встроенные библиотеки .......................... 90 2.4. Структуры данных с реализациями библиотек, написанными авторами этой книги ...................................................................................................... 99 2.4.1. Граф ..................................................................................................................... 99 2.4.2. Система непересекающихся множеств ......................................................103 2.4.3. Дерево отрезков ...............................................................................................107 2.4.4. Дерево Фенвика ...............................................................................................112 2.5. Решения упражнений, не помеченных звездочкой .......................................118 2.6. Примечания к главе 2 .............................................................................................121
Стр.6
6  Содержание Глава 3. Некоторые способы решения задач .........................................124 3.1. Общий обзор и мотивация ...................................................................................124 3.2. Полный перебор ......................................................................................................125 3.2.1. Итеративный полный перебор ....................................................................127 3.2.2. Рекурсивный полный перебор (возвратная рекурсия) ..........................130 3.2.3. Советы ................................................................................................................134 3.3. «Разделяй и властвуй» ...........................................................................................146 3.3.1. Интересное использование двоичного поиска ........................................146 3.4. «Жадные» алгоритмы ............................................................................................152 3.4.1. Примеры ............................................................................................................153 3.5. Динамическое программирование ....................................................................160 3.5.1. Примеры DP ......................................................................................................161 3.5.2. Классические примеры ..................................................................................171 3.5.3. Неклассические примеры .............................................................................184 3.6. Решения упражнений, не помеченных звездочкой .......................................192 3.7. Примечания к главе 3 .............................................................................................195 Глава 4. Графы ...........................................................................................................197 4.1. Общий обзор и мотивация ...................................................................................197 4.2. Обход графа ..............................................................................................................198 4.2.1. Поиск в глубину (Depth First Search, DFS) ..................................................198 4.2.2. Поиск в ширину (Breadth First Search, BFS) ...............................................200 4.2.3. Поиск компонент связности (неориентированный граф) ....................202 4.2.4. Закрашивание – Маркировка/раскрашивание компонент связности .....................................................................................................................203 4.2.5. Топологическая сортировка (направленный ациклический граф) ....204 4.2.6. Проверка двудольности графа .....................................................................206 4.2.7. Проверка свойств ребер графа через остовное дерево DFS ..................207 4.2.8. Нахождение точек сочленения и мостов (неориентированный граф) ..............................................................................................................................209 4.2.9. Нахождение компонент сильной связности (ориентированный граф) ..............................................................................................................................212 4.3. Минимальное остовное дерево ...........................................................................218 4.3.1. Обзор ..................................................................................................................218 4.3.2. Алгоритм Краскала .........................................................................................219 4.3.3. Алгоритм Прима ..............................................................................................221 4.3.4. Другие варианты применения .....................................................................222 4.4. Нахождение кратчайших путей из заданной вершины во все остальные (Single – Source Shortest Paths, SSSP) .....................................................229 4.4.1. Обзор ..................................................................................................................229 4.4.2. SSSP на невзвешенном графе .......................................................................230 4.4.3. SSSP на взвешенном графе ...........................................................................232 4.4.4. SSSP на графе, имеющем цикл с отрицательным весом .......................237 4.5. Кратчайшие пути между всеми вершинами ....................................................242 4.5.1. Обзор ..................................................................................................................242 4.5.2. Объяснение алгоритма DP Флойда–Уоршелла .........................................243 4.5.3. Другие применения ........................................................................................246
Стр.7
Содержание  7 4.6. Поток ..........................................................................................................................253 4.6.1. Обзор ..................................................................................................................253 4.6.2. Метод Форда–Фалкерсона ............................................................................254 4.6.3. Алгоритм Эдмондса–Карпа ..........................................................................256 4.6.4. Моделирование графа потока – часть I ......................................................257 4.6.5. Другие разновидности задач, использующих поток ..............................259 4.6.6. Моделирование графа потока – часть II ....................................................261 4.7. Специальные графы ...............................................................................................264 4.7.1. Направленный ациклический граф ............................................................265 4.7.2. Дерево .................................................................................................................274 4.7.3. Эйлеров граф ....................................................................................................276 4.7.4. Двудольный граф .................................................................................................277 4.8. Решения упражнений, не помеченных звездочкой .......................................287 4.9. Примечания к главе 4 .............................................................................................291 Глаа 5. Математика .................................................................................................293 5.1. Общий обзор и мотивация ...................................................................................293 5.2. Задачи Ad Hoc и математика ................................................................................294 5.3. Класс Java BigInteger ...............................................................................................303 5.3.1. Основные функции .........................................................................................303 5.3.2. Дополнительные функции ...........................................................................305 5.4. Комбинаторика ........................................................................................................311 5.4.1. Числа Фибоначчи ............................................................................................311 5.4.2. Биномиальные коэффициенты ...................................................................312 5.4.3. Числа Каталана ................................................................................................313 5.5. Теория чисел .............................................................................................................319 5.5.1. Простые числа ..................................................................................................319 5.5.2. Наибольший общий делитель и наименьшее общее кратное ..............322 5.5.3. Факториал .........................................................................................................322 5.5.4. Нахождение простых множителей с помощью оптимизированных операций пробных разложений на множители ...........323 5.5.5. Работа с простыми множителями ...............................................................324 5.5.6. Функции, использующие простые множители ........................................325 5.5.7. Модифицированное «решето» .....................................................................327 5.5.8. Арифметические операции по модулю .....................................................327 5.5.9. Расширенный алгоритм Евклида: решение линейного диофантова уравнения ......................................................328 5.6. Теория вероятностей ..............................................................................................334 5.7. Поиск цикла ..............................................................................................................336 5.7.1. Решение(я), использующее(ие) эффективные структуры данных ......337 5.7.2. Алгоритм поиска цикла, реализованный Флойдом ................................337 5.8. Теория игр .................................................................................................................340 5.8.1. Дерево решений ..............................................................................................341 5.8.2. Знание математики и ускорение решения ...............................................342 5.8.3. Игра Ним ...........................................................................................................343 5.9. Решения упражнений, не помеченных звездочкой .......................................344 5.10. Примечания к главе 5 ..........................................................................................346
Стр.8
8  Содержание Глава 6. Обработка строк ....................................................................................349 6.1. Обзор и мотивация .................................................................................................349 6.2. Основные приемы и принципы обработки строк ..........................................350 6.3. Специализированные задачи обработки строк ..............................................353 6.4. Поиск совпадений в строках ................................................................................360 6.4.1. Решения с использованием библиотечных функций ............................361 6.4.2. Алгоритм Кнута–Морриса–Пратта .............................................................361 6.4.3. Поиск совпадений в строках на двумерной сетке ...................................364 6.5. Обработка строк с применением динамического программирования .....366 6.5.1. Регулирование строк (редакционное расстояние) ..................................366 6.5.2. Поиск наибольшей общей подпоследовательности ...............................369 6.5.3. Неклассические задачи обработки строк с применением динамического программирования......................................................................370 6.6. Суффиксный бор, суффиксное дерево, суффиксный массив .......................372 6.6.1. Суффиксный бор и его приложения ...........................................................372 6.6.2. Суффиксное дерево .........................................................................................374 6.6.3. Практические приложения суффиксного дерева ....................................375 6.6.4. Суффиксный массив .......................................................................................379 6.6.5. Практические приложения суффиксного массива .................................386 6.7. Решения упражнений, не помеченных звездочкой ........................................392 6.8. Примечания к главе ................................................................................................396 Глава 7. (Вычислительная) Геометрия ........................................................398 7.1. Обзор и мотивация .................................................................................................398 7.2. Основные геометрические объекты и библиотечные функции для них ...400 7.2.1. Нульмерные объекты: точки .........................................................................400 7.2.2. Одномерные объекты: прямые ....................................................................403 7.2.3. Двумерные объекты: окружности ...............................................................408 7.2.4. Двумерные объекты: треугольники ............................................................411 7.2.5. Двумерные объекты: четырехугольники ...................................................414 7.2.6. Замечания о трехмерных объектах .............................................................415 7.3. Алгоритмы для многоугольников с использованием библиотечных функций ............................................................................................................................418 7.3.1. Представление многоугольника ..................................................................419 7.3.2. Периметр многоугольника ............................................................................419 7.3.3. Площадь многоугольника ..............................................................................420 7.3.4. Проверка многоугольника на выпуклость ................................................420 7.3.5. Проверка расположения точки внутри многоугольника .......................421 7.3.6. Разделение многоугольника с помощью прямой линии .......................422 7.3.7. Построение выпуклой оболочки множества точек ..................................424 7.4. Решения упражнений, не помеченных звездочкой ........................................430 7.5. Замечания к главе ...................................................................................................434 Глава 8. Более сложные темы .........................................................................436 8.1. Обзор и мотивация .................................................................................................436 8.2. Более эффективные методы поиска ...................................................................436
Стр.9
Содержание  9 8.2.1. Метод поиска с возвратами с применением битовой маски ...............437 8.2.2. Поиск с возвратами с интенсивным отсечением ....................................442 8.2.3. Поиск в пространстве состояний с применением поиска в ширину или алгоритма Дейкстры ......................................................................444 8.2.4. Встреча в середине (двунаправленный поиск) ........................................446 8.2.5. Поиск, основанный на имеющейся информации: A* и IDA* ................448 8.3. Более эффективные методы динамического программирования .............455 8.3.1. Динамическое программирование с использованием битовой маски .............................................................................................................................455 8.3.2. Некоторые общие параметры (динамического программирования) ..................................................................................................456 8.3.3. Обработка отрицательных значений параметров с использованием метода смещения ....................................................................458 8.3.4. Превышение лимита памяти? Рассмотрим использование сбалансированного бинарного дерева поиска как таблицы запоминания состояний ..........................................................................................460 8.3.5. Превышение лимита памяти/времени? Используйте более эффективное представление состояния ..............................................................460 8.3.6. Превышение лимита памяти/времени? Отбросим один параметр, будем восстанавливать его по другим параметрам ..........................................462 8.4. Декомпозиция задачи ............................................................................................467 8.4.1. Два компонента: бинарный поиск ответа и прочие ..............................468 8.4.2. Два компонента: использование статической задачи RSQ/RMQ ........470 8.4.3. Два компонента: предварительная обработка графа и динамическое программирование ....................................................................471 8.4.4. Два компонента: использование графов ..................................................473 8.4.5. Два компонента: использование математики .........................................474 8.4.6. Два компонента: полный поиск и геометрия ..........................................474 8.4.7. Два компонента: использование эффективной структуры данных ...474 8.4.8. Три компонента ...............................................................................................475 8.5. Решения упражнений, не помеченных звездочкой .......................................484 8.6. Замечания к главе ...................................................................................................485 Глава 9. Малораспространенные темы ......................................................487 Общий обзор и мотивация ...........................................................................................487 9.1. Задача 2­SAT .............................................................................................................488 9.2. Задача о картинной галерее .................................................................................491 9.3. Битоническая задача коммивояжера .................................................................492 9.4. Разбиение скобок на пары ....................................................................................495 9.5. Задача китайского почтальона ............................................................................496 9.6. Задача о паре ближайших точек ..........................................................................497 9.7. Алгоритм Диница ....................................................................................................499 9.8. Формулы или теоремы...........................................................................................500 9.9. Алгоритм последовательного исключения переменных, или метод Гаусса .................................................................................................................................502 9.10. Паросочетание в графах ......................................................................................505 9.11. Кратчайшее расстояние на сфере (ортодромия) ...........................................509
Стр.10
10  Содержание 9.12. Алгоритм Хопкрофта–Карпа..............................................................................511 9.13. Вершинно и реберно не пересекающиеся пути ............................................512 9.14. Количество инверсий ...........................................................................................513 9.15. Задача Иосифа Флавия ........................................................................................515 9.16. Ход коня ..................................................................................................................516 9.17. Алгоритм Косараджу ............................................................................................518 9.18. Наименьший общий предок ..............................................................................519 9.19. Создание магических квадратов (нечетной размерности) ........................522 9.20. Задача о порядке умножения матриц ..............................................................523 9.21. Возведение матрицы в степень .........................................................................525 9.22. Задача о независимом множестве максимального веса .............................530 9.23. Максимальный поток минимальной стоимости ..........................................532 9.24. Минимальное покрытие путями в ориентированном ациклическом графе ......................................................................................................533 9.25. Блинная сортировка .............................................................................................535 9.26. Ро­алгоритм Полларда для разложения на множители целых чисел ......538 9.27. Постфиксный калькулятор и преобразование выражений ........................540 9.28. Римские цифры .....................................................................................................543 9.29. k­я порядковая статистика .................................................................................545 9.30. Алгоритм ускоренного поиска кратчайшего пути .......................................549 9.31. Метод скользящего окна .....................................................................................550 9.32. Алгоритм сортировки с линейным временем работы.................................553 9.33. Структура данных «разреженная таблица» ....................................................555 9.34. Задача о ханойских башнях................................................................................558 9.35. Замечания к главе .................................................................................................559 Приложение А. uHunt ............................................................................................562 Приложение В. Благодарности .......................................................................567 Список используемой литературы ...............................................................569 Предметный указатель ........................................................................................574
Стр.11

Облако ключевых слов *


* - вычисляется автоматически
Периодика по подписке
Антиплагиат система Руконтекст