Hướng dẫn giải của [200 đề thầy Đức] Bài 137: Biến đổi 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
Tại mỗi vị trí i, ta đổi c[i] với a[i] hoặc với b[i]. Cần sau cùng a bằng b.
Sub 1: Vét cạn 2^n lựa chọn — ~O(2^n · n)~
Đệ quy thử cả hai lựa chọn cho từng vị trí, đến cuối thì kiểm tra a == b. Chỉ chạy được khi n nhỏ. Đạt 1/21 test, còn lại quá giờ.
#include <bits/stdc++.h>
using namespace std;
// Vét cạn: thử cả hai lựa chọn cho mỗi vị trí i (đổi c[i] với a[i] hoặc với b[i]),
// rồi kiểm tra a == b. Mất 2^n lần thử nên chỉ chạy được với n nhỏ.
bool thu(int i, int n, string a, string b, string c) {
if (i == n) return a == b;
// Lựa chọn 1: đổi c[i] với a[i]
{
string a2 = a, c2 = c;
swap(a2[i], c2[i]);
if (thu(i + 1, n, a2, b, c2)) return true;
}
// Lựa chọn 2: đổi c[i] với b[i]
{
string b2 = b, c2 = c;
swap(b2[i], c2[i]);
if (thu(i + 1, n, a, b2, c2)) return true;
}
return false;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int T;
cin >> T;
while (T--) {
string a, b, c;
cin >> a >> b >> c;
int n = a.size();
cout << (thu(0, n, a, b, c) ? "YES" : "NO") << "\n";
}
return 0;
}
Sub 2: Kiểm tra từng vị trí — ~O(n)~
Nếu đổi c[i] với a[i] thì cần c[i] == b[i]. Nếu đổi c[i] với b[i] thì cần a[i] == c[i]. Vì vậy mỗi vị trí chỉ cần c[i] bằng a[i] hoặc bằng b[i]. Đạt 21/21 test.
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int T;
cin >> T;
while (T--) {
string a, b, c;
cin >> a >> b >> c;
int n = a.size();
// Tại vị trí i, sau khi đổi:
// - đổi c[i] với a[i]: a'[i] = c[i] phải bằng b[i] => c[i] == b[i]
// - đổi c[i] với b[i]: b'[i] = c[i] phải bằng a[i] => c[i] == a[i]
// Mỗi vị trí chỉ cần một trong hai điều kiện đúng.
bool ok = true;
for (int i = 0; i < n; i++)
if (c[i] != a[i] && c[i] != b[i]) {
ok = false;
break;
}
cout << (ok ? "YES" : "NO") << "\n";
}
return 0;
}
Bình luận