№ | Пользователь | Рейтинг |
---|---|---|
1 | tourist | 3947 |
2 | jiangly | 3734 |
3 | Radewoosh | 3646 |
4 | jqdai0815 | 3620 |
4 | Benq | 3620 |
6 | orzdevinwang | 3612 |
7 | ecnerwala | 3581 |
8 | Geothermal | 3569 |
8 | cnnfls_csy | 3569 |
10 | ksun48 | 3479 |
Страны | Города | Организации | Всё → |
№ | Пользователь | Вклад |
---|---|---|
1 | awoo | 162 |
2 | maomao90 | 160 |
3 | nor | 157 |
4 | adamant | 156 |
5 | cry | 155 |
5 | atcoder_official | 155 |
5 | -is-this-fft- | 155 |
8 | maroonrk | 153 |
9 | SecondThread | 147 |
10 | Petr | 146 |
Название |
---|
хммм. Можно даже так. Будем идти обходом в ширину по маскам, где ребро - это прибавление одного бита, запускаемся от нулевой маски. Очевидно, что если парсоч для данной маски уже не полный - значит, если мы будем добавлять биты, мы полный парсоч не получим. То есть, запускаемся только от тех масок, где получен уже полный парсоч, и в них ищем увеличивающую цепь. Асимптотику как посчитать в таком варианте решения я не знаю, но это в разы быстрее чем для каждой маски строить парсоч - во-первых, мы отсекаем явно невалидные маски, во-вторых, мы ответ достраиваем, а не строим с самого начала.
Если G - это "Выбор фотоаппарата", то по ней есть авторский разбор решения И.Н.Порублёва - если очень интересует, могу выложить, думаю Илья Николаевич возражать не будет. :)
UPD(на реплику ниже): понял, не туда. Где-то я видел её разбор, но на английском. Как попадется под руки, то коль уже здесь не в тему отписался, то обязательно выложу разбор по теме. :)
По скольку нам надо вывести не само дерево, а только число вершин в нём, то можно всё сделать попроще.
Рассмотрим некоторый лист нашего дерева. К этому листу от ближайшей к нему развилки (развилка это вершина степени >= 3) ведёт цепочка. Найдём длинну этой цепочки. Alias уже почти написал как. Зафиксируем произвольно начало его кишки, переберём все остальные вершины в качестве конца. И из всех 'x' - расстояний до кишки выберем минимальное. Это и будет расстояние до ближайшей развилки. Добавим его к ответу. После чего нашу вершину, вместе с цепочкой ведущей к ней, удалим из дерева. Тоесть просто больше никогда не будем её рассматривать в качестве конца кишки. И так сделаем для каждой вершины.
Получаем 2 вложенных фора (перебираем вершину и для каждой вершины перебираем конец кишки) и одна формула рассчёта расстояния до кишки внутри. Пишется 5 минут.