Hướng dẫn giải của [200 đề thầy Đức] Bài 140: Thao tác chuỗi
Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Hướng dẫn giải
Hoán đổi đúng một cặp s[i] và t[j] phải làm hai chuỗi bằng nhau. Các vị trí khác nhau giữa s và t phải được xử lý bởi đúng cặp hoán đổi này.
Sub 1: Vét cạn mọi cặp (i, j) — ~O(n^3)~
Thử mọi cặp (i, j), hoán đổi s[i] với t[j] trên bản sao, rồi kiểm tra s == t. Đạt 11/21 test, còn lại quá giờ.
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int q;
cin >> q;
while (q--) {
int n;
string s, t;
cin >> n >> s >> t;
// Vét cạn: thử mọi cặp (i, j), hoán đổi s[i] với t[j], rồi kiểm tra s == t
bool ok = false;
for (int i = 0; i < n && !ok; i++)
for (int j = 0; j < n && !ok; j++) {
string s2 = s, t2 = t;
swap(s2[i], t2[j]);
if (s2 == t2) ok = true;
}
cout << (ok ? "Yes" : "No") << "\n";
}
return 0;
}
Sub 2: Kiểm tra các vị trí khác nhau — ~O(n)~
Nếu s và t khác nhau đúng hai vị trí p, r, thì hoán đổi phải dùng đúng p và r. Điều kiện đủ là s[p] = s[r] và t[p] = t[r]. Nếu số vị trí khác nhau khác 2 thì đáp án là No. Đạt 21/21 test.
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int q;
cin >> q;
while (q--) {
int n;
string s, t;
cin >> n >> s >> t;
// Tìm các vị trí khác nhau giữa s và t
vector<int> viTri;
for (int i = 0; i < n; i++)
if (s[i] != t[i]) {
viTri.push_back(i);
if (viTri.size() > 2) break;
}
// Phải đúng 2 vị trí khác nhau p, r, và cặp (s[p], t[p]) = (s[r], t[r]) theo nghĩa
// s[p] == s[r] và t[p] == t[r]. Khi đó hoán đổi s[p] với t[r] là đủ.
bool ok = false;
if (viTri.size() == 2) {
int p = viTri[0], r = viTri[1];
if (s[p] == s[r] && t[p] == t[r]) ok = true;
}
cout << (ok ? "Yes" : "No") << "\n";
}
return 0;
}
Bình luận