Codeforces 100971.J: различия между версиями
Перейти к навигации
Перейти к поиску
Ctrlalt (обсуждение | вклад) (Новая страница: «== Ссылка на задачу == * [http://codeforces.com/gym/100971/problem/J Codeforces #100971.J — Роботы на складе] == Коммент…») |
Ctrlalt (обсуждение | вклад) Нет описания правки |
||
| Строка 1: | Строка 1: | ||
== Ссылка на задачу == | == Ссылка на задачу == | ||
* [http://codeforces.com/gym/100971/problem/ | * [http://codeforces.com/gym/100971/problem/M Codeforces #100971.M — Разбиение на хорошие строки] | ||
== Комментарии == | == Комментарии == | ||
Пусть 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 \times; log^2(n)). | |||
[[Category: Сборник задач: Codeforces]] | [[Category: Сборник задач: Codeforces]] | ||
[[Category: Задачи: | [[Category: Задачи: Динамическое программирование — один параметр]] | ||
[[Category: Задачи: Дерево отрезков]] | |||
[[Category: Задачи: Sparse Table]] | |||
[[Category: Задачи: Бинарный поиск]] | |||
[[Category: Задачи: Два указателя]] | |||
Версия от 20:48, 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 \times; log^2(n)).