Решение задачи Уравнивание строк с Codeforces
Без пояснения   Просмотров: 77
Вам заданы две строки s и t одинаковой длины, состоящие из строчных букв латинского алфавита. Вы можете выполнять любое (возможно нулевое) количество операций над этими строками.
В течении каждой операции вы выбираете два соседних символа в любой строке и присваиваете значение первого символа значению второго или наоборот.
Например, если s равна «acbc» вы можете получить следующие строки за одну операцию:
«aabc» (если выполните присвоение s2=s1);
«ccbc» (если выполните присвоение s1=s2);
«accc» (если выполните присвоение s3=s2 или s3=s4);
«abbc» (если выполните присвоение s2=s3);
«acbb» (если выполните присвоение s4=s3);
Обратите внимание, что такие же операции вы можете применять и к строке t.
Вам нужна выполнить несколько (возможно ноль) таких операций, чтобы строка s стала равна t. Определите, возможно ли это.
Обратите внимание, что вам нужно ответить на q независимых запросов.
В течении каждой операции вы выбираете два соседних символа в любой строке и присваиваете значение первого символа значению второго или наоборот.
Например, если s равна «acbc» вы можете получить следующие строки за одну операцию:
«aabc» (если выполните присвоение s2=s1);
«ccbc» (если выполните присвоение s1=s2);
«accc» (если выполните присвоение s3=s2 или s3=s4);
«abbc» (если выполните присвоение s2=s3);
«acbb» (если выполните присвоение s4=s3);
Обратите внимание, что такие же операции вы можете применять и к строке t.
Вам нужна выполнить несколько (возможно ноль) таких операций, чтобы строка s стала равна t. Определите, возможно ли это.
Обратите внимание, что вам нужно ответить на q независимых запросов.