Пожалуйста, прочтите новое правило об ограничении использования AI-инструментов.
→ Обратите внимание
→ Трансляции
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 4009 |
| 2 | jiangly | 3773 |
| 3 | Radewoosh | 3646 |
| 4 | ecnerwala | 3624 |
| 5 | jqdai0815 | 3620 |
| 5 | Benq | 3620 |
| 7 | orzdevinwang | 3612 |
| 8 | Geothermal | 3569 |
| 8 | cnnfls_csy | 3569 |
| 10 | Um_nik | 3396 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | Um_nik | 163 |
| 2 | cry | 161 |
| 3 | maomao90 | 160 |
| 4 | -is-this-fft- | 159 |
| 5 | awoo | 158 |
| 6 | atcoder_official | 157 |
| 7 | adamant | 155 |
| 8 | nor | 154 |
| 9 | maroonrk | 152 |
| 10 | Dominater069 | 148 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 21.09.2024 09:47:46 (l1).
Десктопная версия, переключиться на мобильную.
При поддержке
А по-моему смешно. Большинство конечно заступится за беднягу. Но все-таки поинтереснее, чем просто так попросить о помощи у сообщества. Молодец, неплохо придумал.
По поводу задачи. Да тут можно самый тупой бор построить по всем суффиксам первой строки, потом пройтись по всем суффиксам второй строки и пометить все вершины бора, достижимые переходами по символам этих суффиксов. Все не помеченные вершины удалить. Затем уже тривиальное решение. Встаем в корень. Смотрим в поддерево, в которое переходим по нулю. Если в нем листов меньше, чем наш номер K, то вычитаем из K это число и переходим по единице. Если в нем листов не меньше, то переходим по нулевому ребру. Ну и так далее для всех вершин, в которых оказываемся. Я так понял, что существование ответа гарантируется.
Благодарю за помощь и оптимистическое восприятие моих слов насчёт JKeeJ1e30!
К сожалению, такое решение ловит МЛ (64 мб) на больших тестах( В вершине дерева вроде как ничего лишнего.
Не подскажете, как можно соптимизировать, или может у меня ошибка какая-то? http://ideone.com/TGMaxI
А если заменить
node *pointer[2];наnode* zero, one;?Такое решение можно пропихнуть. Моя реализация бора не на указателях, а на массивах (то есть ссылка — это просто индекс в массиве). Так как количество вершин — это величина порядка N^2, то можно юзать bitset место bool used[], что существенно лучше. (прошло за 65060 KB из 65536 KB)
P.S. А если по-хорошему, то такая задача, только с более жесткими ограничениями, была в Харькове 2013. Задача М. Решается с помощью суффиксного дерева, можете посмотреть разбор.
Спасибо.
Увы, на зимней школе да и после суффиксное дерево я так и не осилил, поэтому ту задачу и не вспомнил =)
А эту задачу пришлось решить за
.
Решение, кстати, получилось довольно небольшим и хорошим по памяти и времени (270мс, 1.2мб). А именно:
Для каждого символа первой строки нашёл позицию во второй строке, начала наибольшей подстроки, совпадающей с подстрокой, начинающейся в этом символе=) Это я сделал через прогон префикс-функций. Далее отсортировал полученный массив позиций, сравнивая их по подстрокам, которые они представляют. Ну и последовательно прошёлся по этому массиву, пока не дошёл до k-той общей подстроки.
Наверное, можно было вместо сортировки использовать функцию nth_element со своим компаратором и тогда решение работало бы за квадрат (в среднем).
Но у меня же в том массиве хранятся не все возможные подстроки, а лишь n штук, такие, что ихние префиксы формируют все подстроки. А уже при проходе после сортировки, я прибавляю все подстроки, которые находяться между і-той и i+1-ой в моём массиве. То-есть до этого прохода я даже не знаю, какой по счёту элемент из массива мне нужен.
Или это можно как-то обтанцевать в компараторе?
Если написать nth_element полностью руками, то можно :)