My<cod/>.net
Решение задачи Обмен символов (упрощённая версия) с Codeforces
С пояснением Просмотров: 1024
После долгих страданий и многих неуспешных попыток Уджан решил снова попробовать прибраться в своём доме. Вначале он решил привести в порядок свои строки.
У Уджана есть две различные строки s и t длины n, которые содержат только строчные буквы английского алфавита. Он хочет сделать их одинаковыми. Так как Уджан ленивый, он выполнит следующую операцию ровно один раз: он выбирает два индекса i и j (1≤i,j≤n, значения i и j могут как совпадать, так и различаться), и меняет местами буквы si и tj. Получится ли у него задуманное?
Обратите внимание, что он должен применить эту операцию ровно один раз. Он не может ее не cделать.
Автор: Администратор
Автор: Администратор
Пояснение к задаче
Сперва допустим, что мы делаем строки одинаковыми, выбирая некоторые i, j. Тогда для всех p≠i,j должно выполнятся s[p]=t[p], потому что эти буквы не изменились.
Допустим, что i=j. Так как данные строки различные, то обязательно должно быть s[i]≠t[i]. Но тогда строки различные и после обмена букв; поэтому, нам всегда нужно выбирать различные i и j.
Теперь, если i≠j и строки одинаковые после обмена символов, должно выполнятся s[i]=s[j], t[i]=t[j] и s[i],s[j]≠t[i],t[j]. Поэтому, алгоритм следующий: если количество позиций, в которых s и t различаются, не равно 2, то ответ «Нет». Иначе находим две позиции i, j, в которых s и t различаются, и проверим, что описанные выше условия выполняются. Тогда ответ «Да». Время работы решения: O(n).