Привет.
Как решать задачи A, C и H с этой тренировки? Буду очень признателен.
Привет.
Как решать задачи A, C и H с этой тренировки? Буду очень признателен.
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 3757 |
| 2 | jiangly | 3647 |
| 3 | Benq | 3581 |
| 4 | orzdevinwang | 3570 |
| 5 | Geothermal | 3569 |
| 5 | cnnfls_csy | 3569 |
| 7 | Radewoosh | 3509 |
| 8 | ecnerwala | 3486 |
| 9 | jqdai0815 | 3474 |
| 10 | gyh20 | 3447 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | maomao90 | 171 |
| 2 | awoo | 165 |
| 3 | adamant | 163 |
| 4 | TheScrasse | 159 |
| 5 | maroonrk | 155 |
| 6 | nor | 154 |
| 7 | -is-this-fft- | 152 |
| 8 | Petr | 147 |
| 9 | orz | 145 |
| 9 | pajenegod | 145 |
В задаче С будем использовать дерево отрезков. Так как всего 366 операций обновления, значит просто будем перестраивать все дерево отрезков с каждой операцией обновления.
В задаче H нужно было посчитать динамику dp[i][j] — максимальная длина строки палиндрома на подстроке s[i..j], которую можно получить путем вычеркивания минимального количества символов. Затем просто пройтись по всем парам (l, r) и найти максимальный ответ, т.к. количество символов которые стоит удалить чтобы получить палиндром на подстроке s[i..j] = j — i + 1 — dp[i][j].
Так как всего 366 операций обновления, значит просто будем перестраивать все дерево отрезков с каждой операцией обновления.
Когда-нибудь я научусь внимательно читать условия задач, но только не сегодня :) Ведь почти два часа убил...
A — как любят говорить в таких случаях, "несложными преобразованиями..." :) Пускай ответ без последней цифры х имеет длину L, тогда (10*x+6)*3=6*10^L+x; отсюда x*29=6*(10^L-3); далее 10^L=3 mod 29. Осталось только найти k-ое по порядку подходящее L. Заметим, что период 10^L mod 29 равен 28 — дальше только подставить все значения во все полученные выражения по порядку и посчитать ответ:)
C — дерево отрезков. При запросе обновления — перестроим наивным образом всю ту часть дерева, которая изменилась. Мы можем себе это позволить, потому что есть ограничение на число обновлений среди запросов:) При запросе произведения — вытаскиваем произведение из дерева отрезков.
Вроде бы возможно альтернативное решение, поскольку у нас простой модуль — считать частичные произведения на суффиксах, и ответ на отрезке представлять в виде частного двух произведений. Но здесь надо будет аккуратно обработать возможные ноли (не учитывать их в произведениях и считать отдельно).
Н — считаем стандартную динамику "сколько нужно изменений, чтобы сделать подстроку от l до r палиндромом". Считаем ее по подстрокам от коротких к длинным — для подстроки мы можем либо выбросить один из крайних символов, и перейти к строке, которая короче на 1, либо бесплатно выбросить пару крайних символов, если они одинаковые — и перейти к строке, короче на 2. Далее среди всех состояний динамики, у которых значение не больше K — выбираем лучшее.
Задача C:
Почему первое решение получает ТЛ7, а второе заходит?
Если я правильно понял, в чем различие — при вызове build мы обрабатываем все дерево (О(N) вершин); при вызове update мы обрабатываем О(logN) вершин. Если update вызывать для каждого элемента массива, а r-l соизмеримо с N, то получаем суммарно О(NlogN). Это ощутимо хуже О(N) в случае одного вызова build — отсюда и TL.
Почему-то думал, что build работает за NlogN.
Спасибо за разъяснение)
В задаче С можно написать SQRT-декомпозицию.
Мой код.
прочитал условия. Не грешновато ли давать школьникам задачи из сериала категории 18+? :)