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

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


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

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

У Уджана есть две различные строки 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";
	}
}

         


<div style=

A PHP Error was encountered

Severity: Notice

Message: Undefined index: first_name

Filename: templates/tasksdecision_view.php

Line Number: 133

Backtrace:

File: /var/www/u0984434/data/www/hsecodes.com/application/views/templates/tasksdecision_view.php
Line: 133
Function: _error_handler

File: /var/www/u0984434/data/www/hsecodes.com/application/controllers/Tasksdecision.php
Line: 120
Function: view

File: /var/www/u0984434/data/www/hsecodes.com/index.php
Line: 315
Function: require_once

Администратор 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).

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

Комментарии

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