Блог пользователя Aziza

acm.sgu.ru 322, 325
Автор Aziza, 14 лет назад, По-русски

Здраствуйте, подскажите пожалуйста как можно решить задачи 322. The Great Union и задачу 325. Palindrome.
Заранее спасибо).

  • Проголосовать: нравится
  • +11
  • Проголосовать: не нравится

»
14 лет назад, скрыть # |
← Rev. 7  
Проголосовать: нравится +3 Проголосовать: не нравится

На 325 у меня есть довольно мутная идея...

Идея такая: разобьем буквы на "левые" и "правые" ("центральную" игнорируем). На каждом шаге мы должны выбрать, какие буквы мы поставим на края палиндрома. Очевидно, из одинаковых букв мы будем выбирать самую левую для "левой" буквы и самую правую для "правой". Выбирать будем жадно, оптимизируя следующую функцию: количество свапов для "левой" буквы минус количество "левых" букв справа от нее плюс количество свапов для "правой" буквы минус количество "правых" букв слева от нее.

P.S. Решение я еще не написал, но у меня в голове есть набросок доказательства.

**UPD.** Вопрос к знающим: как реализовать вышеописанную байду без применения дерамиды / дерева отрезков / вообще каких-либо деревьев? Уже реализовал.

→ Ответить
»
14 лет назад, скрыть # |
 
Проголосовать: нравится +4 Проголосовать: не нравится

322 казалось бы просто реализация. Находим дорогу, которой нет в первой стране, но есть во второй. Добавляем ее в первую страну. В результате получается цикл. В нем точно есть дорога, которой нет во второй стране. Удаляем ее. Так до тех пор, пока деревья не совпадут.

→ Ответить
»
14 лет назад, скрыть # |
 
Проголосовать: нравится +8 Проголосовать: не нравится

В палиндроме жадность + фенвик же. http://pastie.org/4395924 мой старый код

→ Ответить
»
10 лет назад, скрыть # |
← Rev. 2  
Проголосовать: нравится +2 Проголосовать: не нравится

sf

→ Ответить