[Условия задач] [Список тренировок]
6A. Закраска прямой
[cover]
Полезная задача. Является фундаментальным “кирпичиком”. Другая вариация этой задачи встречается в задаче Музей. Нужно научиться корректно, а главное быстро обрабатывать случай когда часть отрезка принадлежит нескольким интервалам, а также грамотно откидывать пустоты.
6B. Суммы
[sums]
Переборная задача, требующая знания и понимая “Рюкзака”.
6C. Игра “Даты”
[dategame]
Первая задача на теорию игр. Крайне полезно при первом прорешивании догадаться самому до правильного решения, воспользовавшись фактом, что решается она методом Динамического программирования. Мне такого сделать не удалось. Текущая позиция для первого игрока является выигрышной, если есть хотя бы одна позиция, куда он может пойти, которая является проигрышной для второго игрока.
6D. Площадь прямоугольников
[rectarea]
Эта задача еще один фундаментальный “кирпичик”. Ее решение изложено в книге Окулова. Рассмотрим рисунок.
Как видно дано 4 прямоугольника. Каждый из них дает по 2 проекции на оси X и Y. Избавляемся от дубликатов проекций. После чего получаем сетку, образованную этими проекциями. Эта сетка разбила первоначально пустой прямоугольник на N маленьких прямоугольников. В нашем случае N = 28. Чтобы найти суммарную площадь нужно перебрать каждый прямоугольник сетки и проверить, не является ли он вложенным хотя бы в один из первоначальных прямоугольников.
6E. Lines
[lines]
Отличная задача на одновременное применение поиска в ширину(BFS) для получения наилучшего ответа и поиска в глубину(DFS) для восстановление ответа.
6F. Покраска лабиринта
[paintlab] Рекурсивный DFS
Эту задачу можно делать как поиском в глубину, так и в ширину. Т.к. ограничения невелики и DFS пишется быстрее, то выбираем именно этот путь.
[paintlab] Нерекурсивный DFS
Была предпринята попытка показать, как можно реализовать DFS без явного использования рекурсии. Для этого был использован стек, в котором хранились предыдущие состояния. На больших размерностях такой подход будет работать быстрее. Но в боевых условиях, чтобы избежать использования рекурсии лучше писать BFS, если это возможно.
[Все решения]
6A. Закраска прямой
[cover]
Полезная задача. Является фундаментальным “кирпичиком”. Другая вариация этой задачи встречается в задаче Музей. Нужно научиться корректно, а главное быстро обрабатывать случай когда часть отрезка принадлежит нескольким интервалам, а также грамотно откидывать пустоты.
6B. Суммы
[sums]
Переборная задача, требующая знания и понимая “Рюкзака”.
6C. Игра “Даты”
[dategame]
Первая задача на теорию игр. Крайне полезно при первом прорешивании догадаться самому до правильного решения, воспользовавшись фактом, что решается она методом Динамического программирования. Мне такого сделать не удалось. Текущая позиция для первого игрока является выигрышной, если есть хотя бы одна позиция, куда он может пойти, которая является проигрышной для второго игрока.
6D. Площадь прямоугольников
[rectarea]
Эта задача еще один фундаментальный “кирпичик”. Ее решение изложено в книге Окулова. Рассмотрим рисунок.
Как видно дано 4 прямоугольника. Каждый из них дает по 2 проекции на оси X и Y. Избавляемся от дубликатов проекций. После чего получаем сетку, образованную этими проекциями. Эта сетка разбила первоначально пустой прямоугольник на N маленьких прямоугольников. В нашем случае N = 28. Чтобы найти суммарную площадь нужно перебрать каждый прямоугольник сетки и проверить, не является ли он вложенным хотя бы в один из первоначальных прямоугольников. 6E. Lines
[lines]
Отличная задача на одновременное применение поиска в ширину(BFS) для получения наилучшего ответа и поиска в глубину(DFS) для восстановление ответа.
6F. Покраска лабиринта
[paintlab] Рекурсивный DFS
Эту задачу можно делать как поиском в глубину, так и в ширину. Т.к. ограничения невелики и DFS пишется быстрее, то выбираем именно этот путь.
[paintlab] Нерекурсивный DFS
Была предпринята попытка показать, как можно реализовать DFS без явного использования рекурсии. Для этого был использован стек, в котором хранились предыдущие состояния. На больших размерностях такой подход будет работать быстрее. Но в боевых условиях, чтобы избежать использования рекурсии лучше писать BFS, если это возможно.
[Все решения]
Комментариев нет:
Отправить комментарий