Hướng dẫn giải của [Beginner Free Contest 04] COMPRESS
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
Cho xâu S (độ dài ≤ 1000), tìm xâu nén: chọn T ngắn nhất sao cho S là T lặp lại K lần, rồi in K ghép với T.
Sub 1: Vét cạn độ dài T — ~O(n^3)~
Thử lần lượt các độ dài L = 1, 2, ..., n. Nếu L không chia hết n thì bỏ qua. Ngược lại, lấy T là L ký tự đầu, ghép T lặp lại K = n / L lần rồi so với S. Gặp L đầu tiên khớp thì đó là T ngắn nhất. Đạt 10/10 test (n nhỏ nên thời gian vẫn ổn).
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
string s;
cin >> s;
int n = s.size();
// Sub 1: thu tung do dai T = 1..n, dung lai T rat lan roi so sanh voi S (vet can)
for (int len = 1; len <= n; len++) {
if (n % len) continue;
int k = n / len;
string t = s.substr(0, len), built;
for (int i = 0; i < k; i++) built += t;
if (built == s) {
cout << k << t << endl;
return 0;
}
}
return 0;
}
Sub 2: Kiểm tra từng vị trí — ~O(n^2)~
Cũng thử L tăng dần, nhưng không dựng lại chuỗi. Với mỗi L chia hết n, chỉ cần kiểm tra mọi vị trí i có S[i] = S[i mod L]. Độ phức tạp O(n^2) và không tốn bộ nhớ thêm. Đây là lời giải đầy đủ, đạt 10/10 test.
Lưu ý: đề chỉ đảm bảo T ngắn nhất, nên phải thử L theo thứ tự tăng dần và dừng ngay khi gặp L đầu tiên thỏa mãn.
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
string s;
cin >> s;
int n = s.size();
// Thu do dai T = 1..n (T ngan nhat truoc). Chi xet len chia het n.
// Kiem tra S co phai T lap K lan bang cach so tung ki tu voi ki tu tuong ung cua T.
for (int len = 1; len <= n; len++) {
if (n % len) continue;
bool ok = true;
for (int i = len; i < n && ok; i++)
if (s[i] != s[i % len]) ok = false;
if (ok) {
int k = n / len;
cout << k << s.substr(0, len) << endl;
return 0;
}
}
return 0;
}
Bình luận