Hướng dẫn giải của [2425 KS1] Bài 3: Biến đổi xâu
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
Phép biến đổi chỉ chép ký tự từ vị trí bên trái sang vị trí bên phải, nên ký tự đầu không đổi, và vị trí i chỉ có thể nhận ký tự ban đầu của mình hoặc một ký tự đã có ở bên trái. Điều kiện cần và đủ: T[1] = S[1], và với mỗi i \ge 2, T[i] = S[i] hoặc T[i] xuất hiện trong S[1..i-1]. Xử lý từ phải sang trái để các vị trí bên trái còn nguyên.
Sub 1: Vét cạn - ~O(n^2)~, dùng khi ~n \le 100~
Với mỗi vị trí, duyệt lại các vị trí bên trái để tìm ký tự cần chép. Đúng 20/20 test.
Sub 2: Đánh dấu chữ cái - ~O(n)~
Giữ mảng 26 phần tử đánh dấu các chữ cái đã xuất hiện ở bên trái. Đúng 20/20 test.
Chương trình hoàn chỉnh
main đọc t rồi từng cặp S, T. Mỗi bộ test chọn sub theo độ dài: nếu ~n \le 100~ gọi sub1, còn lại gọi sub2.
#include <bits/stdc++.h>
using namespace std;
// Quy tac: vi tri 1 khong bao gio doi. Voi i >= 2, T[i] phai bang S[i] (khong doi) hoac bang mot ky tu
// co mat trong S[1..i-1] (goc). Xu ly tu phai sang trai nen cac vi tri truoc van con nguyen ban.
string S, T;
// Sub 1: vet can - voi moi vi tri i, duyet lai cac vi tri j < i de tim S[j] = T[i]. O(n^2). Dung khi n <= 100.
void sub1() {
bool ok = (S[0] == T[0]);
for (size_t i = 1; i < S.size() && ok; i++) {
if (T[i] == S[i]) continue;
bool found = false;
for (size_t j = 0; j < i; j++)
if (S[j] == T[i]) { found = true; break; }
if (!found) ok = false;
}
cout << (ok ? "yes" : "no") << "\n";
}
// Sub 2: duyet tu trai sang phai, giu danh sach 26 chu cai da xuat hien trong S[1..i-1]. O(n).
void sub2() {
bool ok = (S[0] == T[0]);
bool seen[26] = {false};
seen[S[0] - 'a'] = true;
for (size_t i = 1; i < S.size() && ok; i++) {
if (T[i] != S[i] && !seen[T[i] - 'a']) ok = false;
seen[S[i] - 'a'] = true;
}
cout << (ok ? "yes" : "no") << "\n";
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t;
cin >> t;
while (t--) {
cin >> S >> T;
if (S.size() <= 100) sub1();
else sub2();
}
return 0;
}
Bình luận