Решение сложных и олимпиадных задач по программированию.    Долинский М.С.

                                 Содержание

      Введение   .............................................................................. 8

От издательства   .................................................................................... 11

 Глава 1. Максимальный поток............................................. 12

1.1.        Примеры задач на максимальный поток   ..................................... 12

1.2.        Формальная постановка задачи......................................................... 14

1.3.        Задача «Новогодняя вечеринка»....................................................... 16

1.4.        Задача «Кубики»............................................................................... 18

1.5.        Задача «Игра»   ............................................................................... 21

1.6.        Пример максимального потока на графе....................................... 25

1.7.        Алгоритм Форда-Фалкерсона   ......................................................... 28

1.8.        Решения задач................................................................................. 33

1.9.        Замечания по реализации   ............................................................... 44

Глава 2. Минимальное остовное дерево............................. 45

2.1.  Формальная постановка задачи......................................................... 45

2.2.  Алгоритм Прима................................................................................ 47

2.3.  Алгоритм Крускала............................................................................ 51

2.4.  Быстрая сортировка.......................................................................... 54

2.5.  Задача «Secret Pipes»....................................................................... 55

2.6.  Задача «Метро»   ............................................................................. 59

2.7.  Задача «Network»  ............................................................................ 61

2.8.  Решения задач................................................................................. 63

Глава 3. Решение задач на деревьях и с помощью деревьев........ 76

3.1.  Практические примеры деревьев....................................................... 78

3.1.1.    Деревья отношений   .............................................................. 78

3.1.2.    Деревья попиксельного представления

плоских цветных образов........................................................ 78

3.1.3.    Деревья представления сложных композиций трехмерных объектов

3.1.4.    Деревья кодирования символов.............................................. 79

3.1.5.    Деревья сортировки................................................................ 81

3.1.6.    Деревья сумм......................................................................... 82

3.1.7.    Перечисление деревьев.......................................................... 82

3.1.8.    Представление деревьев в памяти компьютера............... 83

3.1.9.    Порядок обхода деревьев   .................................................... 84

3.1.10.  Организация материала и технология

работы с ним   ..................................................................... 84

3.2.  Задачи на основные свойства деревьев............................................ 84

3.2.1.    Задача «Is it a tree?»  ............................................................. 85

3.2.2.    Задача «Strategic game»......................................................... 89

3.2.3.    Задача «Оппозиция»............................................................... 92

3.2.4.    Задача «Erdos Numbers»......................................................... 94

3.2.5.    Задача «Closest Common Ancestor»   ..................................... 96

3.3.  Задачи на представление образов..................................................... 98

3.3.1.    Задача «Unscrambling Images»   ............................................. 99

3.3.2.    Задача «BSP Trees»   .......................................................... 106

3.4.  Задачи на двоичные деревья сортировки........................................ 110

3.4.1.    Задача «Дерево»   ............................................................... 110

3.4.2.    Задача «Parliament»   ........................................................... 113

3.4.3.    Задача «Falling Leaves»......................................................... 117

3.5.  Кодирование последовательностей символов

методом Хаффмана   ....................................................................... 120

3.5.1.    Задача «Кодирование»  ....................................................... 120

3.5.2.    Задача «Entroov».................................................................. 124

3.6. Перечисление деревьев.................................................................. 126

3.6.1.   Задача «Nextree»   ............................................................... 126

3.6.2.   Задача «Trees Made to Order»................................................ 132

3.7. Битово-индексированные деревья................................................... 137

3.7.1.   Задача «Мобильные телефоны»  ......................................... 137

3.7.2.   Структура данных BIT............................................................ 141

3.8. Задачи для самостоятельного решения........................................... 145

3.8.1.   Задача «Knockout Tournament».............................................. 145

3.8.2.   Задача «Split Windows»......................................................... 147

3.8.3.   Задача «Huffman Trees»   ...................................................... 149

3.8.4.   Задача «Pre-Post-erous!»   .................................................... 151

3.9. Решения задач............................................................................... 153

Глава 4. Скрытые графы   ................................................ 185

4.1.  Инцидентность областей   ............................................................... 186

4.1.1.    Задача «Тетраэдр»  .............................................................. 186

4.1.2.    Задача «Стены»   ................................................................. 192

4.1.3.    Задача «Блокада»................................................................. 198

4.1.4.    Задача «Мудрый правитель»................................................. 203

4.1.5.    Задача «Ременная передача»  ............................................. 207

4.2.  Отношения других видов   .............................................................. 211

4.2.1.    Задача «Currency Exchange»................................................. 211

4.2.2.    Задача «Exchange Rates»   .................................................. 215

4.2.3.    Задача «Sorting It All Out»   .................................................. 220

4.2.4.    Задача «Проверка веб-страниц»............................................ 225

4.2.5.    Задача «Play On Words»   .................................................... 230

4.3.  Задачи на множествах отрезков...................................................... 234

4.3.1.    Задача «Падение»................................................................ 235

4.3.2.    Задача «The Doors»............................................................... 241

4.3.3.    Задача «Борозды»   ............................................................. 246

4.3.4.    Задача «N-Credible Mazes».................................................... 250

4.4.  Задачи для самостоятельного решения........................................... 254

4.4.1.   Задача «Door Man»................................................................ 254

4.4.2.   Задача «This Sentence is false»  ........................................... 255