№ | Пользователь | Рейтинг |
---|---|---|
1 | jiangly | 3846 |
2 | tourist | 3799 |
3 | orzdevinwang | 3706 |
4 | jqdai0815 | 3682 |
5 | ksun48 | 3590 |
6 | Ormlis | 3533 |
7 | Benq | 3468 |
8 | Radewoosh | 3463 |
9 | ecnerwala | 3451 |
9 | Um_nik | 3451 |
Страны | Города | Организации | Всё → |
№ | Пользователь | Вклад |
---|---|---|
1 | cry | 166 |
2 | -is-this-fft- | 161 |
3 | Qingyu | 160 |
3 | Dominater069 | 160 |
5 | atcoder_official | 158 |
6 | adamant | 155 |
7 | Um_nik | 152 |
8 | djm03178 | 151 |
8 | luogu_official | 151 |
10 | awoo | 148 |
Название |
---|
UwU
Жаль блог о контесте набрал минусовой вклад
В правду жаль
F2 странные ограничения. Приведу свое решение, которое вроде зашло, но ИМХО легче:
Найдем длину максимального палиндрома, предварительно насчитав dp[l][r] — длина макс.палиндрома на промежутке $$$[l;r]$$$. Теперь найдем ответ для минимума за $$$O(n^2*c)$$$ (для максимума похожий алгоритм). Будем поддерживать $$$[ans_l;ans_r]$$$ и еще сколько нам осталось найти букв палиндрома ($$$len$$$), зная что ответ хранится в нем. Если $$$len = 0$$$ можно выйти из алгоритма. Будем перебирать буквы по возрастанию, так как нам нужно найти минимальный лексикографически палиндром. Если кол-во вхождений буквы меньше 2-х, то перебираем дальше. Иначе найдем самое левое и самое правое вхождение этой буквы, обозначим за $$$l_c$$$ и $$$r_c$$$. Если $$$dp[l_c][r_c]<len$$$, то также скипаем. Иначе обновляем $$$l:=l_c+1$$$, $$$r:=r_c-1$$$, $$$len:=len-2;$$$.
И еще немного обработки случаев для палиндромов нечетной длины.
посылка.
код еще оптимайзить и оптимайзить.
UPD: если предподсчитать за $$$O(c*n)$$$ $$$next_c[i]$$$ и $$$last_c[i]$$$, которые показывают ближайшую следующую/предыдущую соответсвенно позицию буквы $$$c$$$, асимптотика непосредственного вычисления ответа снижается до $$$O(n*c)$$$, и у нас остается только динамика за квадрат, которая на самом деле не 10^4 * 10^4 = 10^8, а 10^4 * (10^4 -1)/2 ~= 5*10^7 операций, т.к. это заходит за 500мс, много вопросов к тестам. А так идея контеста интересна
Я туплю немного
А такая нечитаемость условий задумывалась?
Да
не дерево фенрика, а дерево фенвика)
Я привык говорить дерево фенрика. Спасибо за исправления