Лучше поздно чем никогда
Сегодня, 30 ноября, состоялся очередной СРМ
→ Обратите внимание
→ Трансляции
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 3985 |
| 2 | jiangly | 3814 |
| 3 | jqdai0815 | 3682 |
| 4 | Benq | 3529 |
| 5 | orzdevinwang | 3526 |
| 6 | ksun48 | 3517 |
| 7 | Radewoosh | 3410 |
| 8 | hos.lyric | 3399 |
| 9 | ecnerwala | 3392 |
| 9 | Um_nik | 3392 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | cry | 169 |
| 2 | maomao90 | 162 |
| 2 | Um_nik | 162 |
| 4 | atcoder_official | 161 |
| 5 | djm03178 | 158 |
| 6 | -is-this-fft- | 157 |
| 7 | adamant | 155 |
| 8 | awoo | 154 |
| 8 | Dominater069 | 154 |
| 10 | luogu_official | 150 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 23.12.2024 02:23:53 (i1).
Десктопная версия, переключиться на мобильную.
При поддержке
Скорее всего венгерский алгоритм (ну или парасочетание с помощью минкоста).
Каждой фигуре из начального состояния соответствует какая-то фигура из конечного. таким образом для каждой пары фигур можно определить сколько понадобится ходов для перехода.
А что делать, когда все кони уже стоят на своих местах, но их надо подвинуть, чтобы пропустить пешку?
Пример 1:
...
.N.
.P.
---
.P..
.N.
...
Пример 2:
..P.P..
.P...P.
...N...
.P.P.P.
..P.N..
.......
-------
..P.P..
.P.P.P.
...N...
.P...P.
..P.N..
.......
Я вот тоже думаю как решать. Оценка сверху количества позиций не такая и хорошая:
Но может решение и есть простой бфс, это же див2 всё-таки.
Параметры: номер обрабатываемой вершинки, текущая сумма длин внутри объединенных вершин, текущее количество объединенных вершин.
Отсортируем деревья по возрастанию r.
Представим что перестановка это такой граф-цикл из N+1 вершины. Чтобы получить по графу перестановку надо разрезать цикл по N+1-ой вершинке. Вес ребра i-j в графе это rmax(i, j)
Представим себе следующий разрез: вершины с 1 по i в одной части, i + 1 по N в другой. Пусть через этот разрез проходит s пар рёбер. Будем считать число вариантов соединений в левой части разреза.
Три параметра: i - текущая вершинка которую мы переносим через разрез, s - сколько пар рёбер есть в разрезе (проходит из одной части в другую), w - текущая длина перестановки, если учесть все рёбра между вершинами 1..(i - 1).
Значение - количество графов оказывающихся в "левой" части разреза.
Внутри надо перебрать сколько рёбер ведёт из вершины i налево, а сколько направо. Варианты:
2-0 : таких вариантов s * (s - 1) * 2, при этом s надо уменьшать на 1. Вес увеличивается на 2ri
1-1 : таких вариантов ровно s, при этом s не меняется. Вес увеличивается на ri
0-2 : вариант один, s увеличивается на 1.