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

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


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


Если s[0]..s[i] содержит ровно k различных букв, то d[i] = 1.
Если в графе есть хотя бы одна вершина, степень которой больше 2, то в такой вершине роботы могут при необходимости разойтись, поменяв свой порядок, поэтому ответ YES.


Иначе найдём такое минимальное l <= i и максимальное r <= i, что s[l]..s[i] и s[r]..s[i] содержат k различных букв. Тогда d[i] = 1 + min(d[l - 1]..d[r - 1]).
Иначе если граф не содержит вершин со степенью больше 2, то он представляет собой цикл или путь. Если граф &mdash; цикл, то ответ YES, иначе ответ NO.
 
Поиск минимума на отрезке можно выполнять деревом отрезков за O(logn).
 
Подсчёт количества различных букв на отрезке можно осуществлять:
* 26 бинарными поисками за O(26 &times; 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:50, 8 июня 2016

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

Комментарии

По условию задачи граф связен.

Если в графе есть хотя бы одна вершина, степень которой больше 2, то в такой вершине роботы могут при необходимости разойтись, поменяв свой порядок, поэтому ответ YES.

Иначе если граф не содержит вершин со степенью больше 2, то он представляет собой цикл или путь. Если граф — цикл, то ответ YES, иначе ответ NO.

Источник — https://acm.khpnets.info/w39/index.php?title=Codeforces_100971.J&oldid=2037