Командная тренировка №1 (12.08.2013, Southern Subregional 2006): различия между версиями

Материал из Олимпиадное программирование в УлГТУ
Перейти к навигации Перейти к поиску
Нет описания правки
Строка 29: Строка 29:
* [http://acm.sgu.ru/problem.php?contest=0&problem=323 I. Aviamachinations]
* [http://acm.sgu.ru/problem.php?contest=0&problem=323 I. Aviamachinations]
: ''Едет MST через MST. Неплохо решить, если кто захочет осилить Краскала чтобы потренироваться в написании''
: ''Едет MST через MST. Неплохо решить, если кто захочет осилить Краскала чтобы потренироваться в написании''
:: ''Более подробно:''
:::# Ищем MST
:::# Перебираем цвет
:::# Для каждого цвета находим какой-то остовный лес (добавляем ребра в dsu, чтобы не было циклов), а потом достраиваем его до дерева, используя найденное MST
* [http://acm.sgu.ru/problem.php?contest=0&problem=324 J. The Text Formatting] (<span style="color: green;">'''решена на тренировке'''</span>)
* [http://acm.sgu.ru/problem.php?contest=0&problem=324 J. The Text Formatting] (<span style="color: green;">'''решена на тренировке'''</span>)
: ''[http://ideone.com/akC09J Мой код 2008 года выпуска]. Кажется, меньше, чем у вас например.''
: ''[http://ideone.com/akC09J Мой код 2008 года выпуска]. Кажется, меньше, чем у вас например.''

Версия от 19:41, 12 августа 2013

Участники тренировки

  • Андрей Корнеев
  • Ольга Фирсова
  • Владимир Фолунин
  • Александр Ерофеев (организатор)

Соревнование

9th Southern Subregional Programming Contest (Южный четвертьфинал, 2006 год, Саратов). Для прохода в полуфинал требовалось решить 4 задачи.

Зеркало соревнования (задачи 315 — 325)

Задачи и комментарии

Написать что требуют
Динамика
  • D. Grants (решена на тренировке)
Сжатие координат, дерево отрезков с ботвой, построение графа по генерируемой информации
Довольно хитрая реализация. Нечто похожее по хитрости (хотя, наверно, попроще) было нужно для уверенного прохода в 2008
Как сдадите допишете
dfs, нахождение циклов
Едет MST через MST. Неплохо решить, если кто захочет осилить Краскала чтобы потренироваться в написании
Более подробно:
  1. Ищем MST
  2. Перебираем цвет
  3. Для каждого цвета находим какой-то остовный лес (добавляем ребра в dsu, чтобы не было циклов), а потом достраиваем его до дерева, используя найденное MST
Мой код 2008 года выпуска. Кажется, меньше, чем у вас например.
Жадность, дерево отрезков с ботвой
Источник — https://acm.khpnets.info/w39/index.php?title=Командная_тренировка_№1_(12.08.2013,_Southern_Subregional_2006)&oldid=619