Существует некоторая базовая структура, которая может быть использована для решения этой проблемы за O (n) времени.
Указанные правила являются (большей частью) правилами, определяющими математическую группу, в частности группу D_2, также известную иногда как K (для группы Клейна из четырех групп) или V (немец для Viergruppe, группа из четырех человек). D_2 - это группа из четырех элементов A, B, C и 1 (элемент идентичности). Одна из реализаций D_2 - это набор симметрий прямоугольного прямоугольника с тремя разными сторонами. A, B и C - это повороты на 180 градусов вокруг каждой из осей, а 1 - единичное вращение (без вращения). Таблица групп для D_2:
|1 A B C
-+-------
1|1 A B C
A|A 1 C B
B|B C 1 A
C|C B A 1
Как видите, правила соответствуют правилам, приведенным в задаче, за исключением того, что правила, включающие 1, отсутствуют в задаче.
Поскольку D_2 является группой, она удовлетворяет ряду правил: замыкание (произведение любых двух элементов группы является другим элементом), ассоциативность (что означает (x*y)*z = x*(y*z) для любых элементов x, y, z, т. е. порядок уменьшения строк не имеет значения), существование тождества (существует элемент 1 такой, что 1*x=x*1=x для любого x) и существование обратного (для любого элемента x существует элемент x^{-1} такой, что x*x^{-1}=1 and x^{-1}*x=1; в нашем случае каждый элемент является собственным обратным ).
Также стоит отметить, что D_2 является коммутативным , то есть x*y=y*x для любого x,y.
Учитывая любую строку элементов в D_2, мы можем жадным образом сократить до одного элемента в группе . Например, ABCCCCCCC=CCCCCCCC=CCCCCC=CCCC=CC=1. Обратите внимание, что мы не пишем элемент 1, если только он не является единственным в строке. Ассоциативность говорит нам, что порядок операций не имеет значения, например, мы могли бы работать справа налево или начать посередине и получить тот же результат. Давайте попробуем справа: ABCCCCCCC=ABCCCCC=ABCCC=ABC=AA=1.
Ситуация проблемы другая, поскольку операции с 1 недопустимы, поэтому мы не можем просто исключить пары AA, BB или CC. Однако ситуация не , что отличается. Рассмотрим строку ABB. Мы не можем написать ABB=A в этом случае. Однако мы можем устранить BB в два этапа, используя A: ABB=CB=A. Поскольку порядок операций не имеет значения по ассоциативности, мы гарантируем, что получим тот же результат. Поэтому мы не можем идти прямо от ABB до A, но мы можем получить тот же результат другим путем.
Такие альтернативные маршруты доступны, когда в строке есть хотя бы два разных элемента. В частности, в каждом из ABB, ACC, BAA, BCC, CAA, CBB, AAB, AAC, BBA, BBC, CCA, CCB, мы можем действовать так, как будто у нас есть уменьшение xx=1, а затем отбрасывать 1.
Отсюда следует, что любую строку, которая не является однородной (не все одна и та же буква) и имеет двухбуквенную подстроку (AA, BB или CC), можно уменьшить, удалив двойную букву. Строки, содержащие только две одинаковые буквы, не могут быть дополнительно сокращены (поскольку в задаче не допускается 1), поэтому можно с уверенностью предположить, что любая неоднородная строка может быть уменьшена до A, B , C, AA, BB, CC.
Однако мы все еще должны быть осторожны, потому что CCAACC можно превратить в CCCC, удалив среднюю пару AA, но это не лучшее, что мы можем сделать: CCAACC=AACC=CC or AA сводит нас к строка длиной 2.
Другая ситуация, с которой мы должны быть осторожны, это AABBBB Здесь мы можем исключить AA, чтобы закончить с BBBB, но лучше сначала убрать середину B, затем что угодно: AABBBB=AABB=AA or BB (оба из которых эквивалентны 1 в группе, но могут в дальнейшем проблема не сводится).
Есть еще одна интересная ситуация: AAAABBBB. Слепое устранение пар приводит нас к AAAA или BBBB, но мы могли бы добиться большего: AAAABBBB=AAACBBB=AABBBB=AABB=AA or BB.
Вышеприведенное указывает на то, что устранение двойных чисел вслепую не обязательно является способом продолжения, но, тем не менее, оно освещало.
Вместо этого кажется, что наиболее важным свойством строки является неоднородность.Если строка однородна, остановитесь, мы ничего не можем сделать.В противном случае идентифицируйте операцию, которая сохраняет свойство неоднородности, если это возможно.Я утверждаю, что всегда можно идентифицировать операцию, которая сохраняет неоднородность, если строка неоднородна и имеет длину четыре или более.
Доказательство: если 4-подстрока содержит две разные буквы, третья буква может быть введена на границе между двумя разными буквами, например, AABA переходит к ACA.Так как одна или две исходные буквы должны быть неизменными где-то внутри строки, из этого следует, что результат все еще является неоднородным.
Предположим, что вместо этого у нас есть 4-подстрока, которая имеет три различных элемента, скажем AABC, с двумя внешними элементами.Затем, если средние два элемента различны, выполните операцию над ними;результат неоднороден, потому что два самых внешних элемента все еще различны.С другой стороны, если два внутренних элемента одинаковы, например, ABBC, то они должны отличаться от обоих внешних элементов (в противном случае у нас было бы только два элемента в наборе из четырех, а не три).В этом случае выполните первую или третью операцию;что оставляет либо два последних элемента различными (например, ABBC=CBC), либо первые два элемента различными (например, ABBC=ABA), так что сохраняется неоднородность.
Наконец, рассмотрим случай, когда первый ипоследние элементы одинаковы.Тогда у нас такая ситуация, как ABCA.Два средних элемента должны отличаться от внешних элементов, в противном случае у нас было бы только два элемента, а не три.Мы можем взять первую доступную операцию, ABCA=CCA, и неоднородность снова сохранится.
Конец доказательства.
У нас есть жадный алгоритм для уменьшения любогонеоднородная строка длиной 4 или более: выберите первую операцию, которая сохраняет неоднородность;такая операция должна существовать по приведенному выше аргументу.
Теперь мы сократили до случая, когда мы имеем неоднородную строку из 3 элементов.Если два одинаковы, у нас либо есть двойные значения, такие как AAB и т. Д., Которые, как мы знаем, могут быть сведены к одному элементу, или у нас есть два элемента без двойных, как ABA=AC=B, которые также могут быть уменьшены до одного элементаили у нас есть три разных элемента, таких как ABC.Существует шесть перестановок, каждая из которых =1 в группе по ассоциативности и коммутативности;все они могут быть сведены к двум элементам с помощью любой операции;однако их нельзя уменьшить ниже однородной пары (AA, BB или CC), поскольку 1 не разрешено в задаче, поэтому мы знаем, что это лучшее, что мы можем сделать в этом случае.
Таким образом, если строка однородна, мы ничего не можем сделать;если строка неоднородна и =A в группе, она может быть уменьшена до A в задаче с помощью жадного алгоритма, который поддерживает неоднородность на каждом шаге;то же самое, если строка =B или =C в группе;наконец, если строка неоднородна и =1 в группе, ее можно уменьшить с помощью жадного алгоритма, который поддерживает неоднородность как можно дольше, до одного из AA, BB или CC.Это лучшее, что мы можем сделать с помощью групповых свойств операции.
Программа, решающая проблему:
Теперь, поскольку мы знаем возможные результаты, наша программа можетзапустите время O(n) следующим образом: если все буквы в данной строке одинаковы, сокращение невозможно, поэтому просто выведите длину строки.Если строка неоднородна и равна идентичности в группе, выведите число 2;в противном случае выведите число 1.
Чтобы быстро решить, равен ли элемент идентичности в группе, мы используем коммутативность и ассоциативность следующим образом: просто посчитаем число A, B и C в переменных a, b, c. Замените a = a mod 2, b = b mod 2, c = c mod 2, потому что мы можем исключить пары AA, BB и CC в группе. Если ни один из результирующих a, b, c не равен 0, у нас в группе ABC=1, поэтому программа должна вывести 2, потому что сокращение до идентификатора 1 невозможно. Если все три из результирующих a, b, c равны 0, мы снова имеем тождество (A, B и C все аннулируются), поэтому мы должны вывести 2 В противном случае строка не является тождественной, и мы должны вывести 1.