Здравствуйте ! Я новичёк, хотелось бы узнать каким методом можно решить данную задачу http://acm.timus.ru/problem.aspx?space=1&num=1542 . Пробовал так — строим префиксное дерево из входных слов. Находим все слова, удовлетворяющие заданному префиксу, сортируем по частоте и выводим. Такое решение вылетало с TLE. Ещё пробовал пару способов, но всё равно получал TLE. Возможно через хеширование или дерево отрезков можно решить. Подскажите, пожалуйста, каким способом можно решить данную задачу
Пожалуйста, прочтите новое правило об ограничении использования AI-инструментов.
→ Обратите внимание
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 4009 |
| 2 | jiangly | 3839 |
| 3 | Radewoosh | 3646 |
| 4 | jqdai0815 | 3620 |
| 4 | Benq | 3620 |
| 6 | orzdevinwang | 3612 |
| 7 | Geothermal | 3569 |
| 7 | cnnfls_csy | 3569 |
| 9 | ecnerwala | 3494 |
| 10 | Um_nik | 3396 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | Um_nik | 164 |
| 2 | maomao90 | 160 |
| 3 | -is-this-fft- | 159 |
| 4 | atcoder_official | 158 |
| 4 | cry | 158 |
| 4 | awoo | 158 |
| 7 | adamant | 155 |
| 8 | nor | 154 |
| 9 | TheScrasse | 153 |
| 10 | maroonrk | 152 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 01.10.2024 18:34:05 (i1).
Десктопная версия, переключиться на мобильную.
При поддержке
Сложновата задача для новичка. Я бы советовал сначала познакомиться с ассимптотическим анализом времени исполнения программы и деревом отрезков.
Хотя в принципе можно и префиксным деревом решить. Главное помнить, что нам надо только первые 10 ответов найти и, собственно, не лезть в остальные.
Вы уже построили дерево. В каждой вершине предподсчитайте (начиная с листьев) 10 самых часто используемых концов. Чтобы быстро пересчитывать в детях можно использовать кучу(типа как мердж в мерджсорте, только из нескольких а не 2х частей) или мб достаточно просто посортить и взять топ10 ибо всего будет не больше 26 * 10 слов.
Я бы решал так : я бы построил бор по начальным словам, и в каждой вершине еще бы хранил 10 значений таких : максимальные встречаемости слов, а если их меньше 10, то дополнял бы -1, и теперь нам подается слово : мы идем по бору, идем по начальным буквым вглубь дерева, теперь дошли до нужного места : теперь идем по детям , и с помощью 26 указателей (так как алфавит 26) ищем нужные слова (их не больше 10), и так рекурсивно для детей продолжаем и выписываем все.
У меня еще 2 варианта решения:
Посортировать строки, затем деревом отрезков 10 раз заменить максимум на соответствующем подотрезке на 0, и вывести строки, которые были заменены, а потом восстановить их.
Делать примерно так же, но на боре, поддерживая для перехода максимальную достижимую по нему частоту.
Всем большое спасибо за советы ! Попробую доделать свой вариант с префиксным деревом (бор). И в качестве практики как посоветовал adamant, вариант с деревом отрезков