Решение задачи Обмен символов (упрощённая версия) с Codeforces

С пояснением   Просмотров: 21


Эта задача отличается от усложнённой версии. В этой версии задачи Уджана сделает ровно один обмен. Вы можете взламывать эту задачу только тогда, когда решите обе задачи.

После долгих страданий и многих неуспешных попыток Уджан решил снова попробовать прибраться в своём доме. Вначале он решил привести в порядок свои строки.

У Уджана есть две различные строки s и t длины n, которые содержат только строчные буквы английского алфавита. Он хочет сделать их одинаковыми. Так как Уджан ленивый, он выполнит следующую операцию ровно один раз: он выбирает два индекса i и j (1≤i,j≤n, значения i и j могут как совпадать, так и различаться), и меняет местами буквы si и tj. Получится ли у него задуманное?

Обратите внимание, что он должен применить эту операцию ровно один раз. Он не может ее не cделать.

Код

#include <bits/stdc++.h>
using namespace std;
string s,t;
int q;
int n;
main () {
	cin >>q;
	while (q--)
	{
		cin >>n >>s >>t;
		int j = -1;
		for (int i = 0 ;i < n; i++)
			if (s[i] != t[i]) 
			{
				if (j < 0) j = i;
				else
				{
					swap(s[i],t[j]);
					break;
				}
			}
		if (s == t) cout <<"Yes\n";
		else
		cout <<"No\n";
	}
}

         

Администратор Photo Автор: Администратор


Сперва допустим, что мы делаем строки одинаковыми, выбирая некоторые 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).


Комментарии

Чтобы написать комментарии вам нужно войти в систему или зарегистрироваться