Codeforces 100971.M: различия между версиями

Материал из Олимпиадное программирование в УлГТУ
Перейти к навигации Перейти к поиску
(Новая страница: «== Ссылка на задачу == * [http://codeforces.com/gym/100971/problem/M Codeforces #100971.M — Разбиение на хорошие строк…»)
 
Нет описания правки
 
Строка 21: Строка 21:
* двумя указателями за O(1*).
* двумя указателями за O(1*).


Принимаются решения с итоговой асимптотикой не хуже O(n \times; log^2(n)).
Принимаются решения с итоговой асимптотикой не хуже O(n × log^2(n)).


[[Category: Сборник задач: Codeforces]]
[[Category: Сборник задач: Codeforces]]

Текущая версия от 20:56, 8 июня 2016

Ссылка на задачу

Комментарии

Пусть d[i] — минимальное количество хороших строк, на которые можно разбить префикс s[0]..s[i].

Если s[0]..s[i] содержит ровно k различных букв, то d[i] = 1.

Иначе найдём такое минимальное l <= i и максимальное r <= i, что s[l]..s[i] и s[r]..s[i] содержат k различных букв. Тогда d[i] = 1 + min(d[l - 1]..d[r - 1]).

Поиск минимума на отрезке можно выполнять деревом отрезков за O(logn).

Подсчёт количества различных букв на отрезке можно осуществлять:

  • 26 бинарными поисками за O(26 × logn);
  • деревом отрезков отсортированных массивов за O(log^2(n));
  • деревом отрезков битовых масок за O(log^2(n)) (лишний логарифм на подсчёт числа единиц в результирующей маске);
  • разреженной таблицей битовых масок за O(logn).

Определение l и r можно осуществлять:

  • бинарным поиском за O(logn);
  • двумя указателями за O(1*).

Принимаются решения с итоговой асимптотикой не хуже O(n × log^2(n)).