Hướng dẫn giải của [200 đề thầy Đức] Bài 122: Chuỗi k-string
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
Chuỗi ~k\text{-string}~ là ~k~ lần lặp lại một chuỗi ~t~. Vậy ~n~ phải chia hết cho ~k~, và số lần xuất hiện của mỗi chữ cái trong ~s~ phải chia hết cho ~k~. Khi đó lấy mỗi chữ cái ~cnt / k~ lần để tạo đoạn ~t~, rồi lặp ~t~ đúng ~k~ lần. Nếu điều kiện không thỏa thì in -1.
Sub 1: Đếm bằng cách quét chuỗi cho từng chữ cái — ~O(26 \cdot n)~
Với mỗi chữ cái từ 'a' đến 'z', quét cả chuỗi để đếm số lần xuất hiện, kiểm tra chia hết cho ~k~, rồi ghép đoạn ~t~ và lặp ~k~ lần. Đạt 29/29 test.
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int k;
string s;
cin >> k >> s;
int n = s.size();
// Vét cạn: n phải chia hết k
if (n % k != 0) {
cout << -1 << "\n";
return 0;
}
// Đếm từng chữ cái bằng cách quét lại chuỗi cho mỗi chữ cái
string base;
for (char c = 'a'; c <= 'z'; c++) {
int cnt = 0;
for (int i = 0; i < n; i++) if (s[i] == c) cnt++;
if (cnt % k != 0) {
cout << -1 << "\n";
return 0;
}
// chữ c xuất hiện cnt/k lần trong một đoạn lặp lại
base += string(cnt / k, c);
}
// Lặp đoạn base k lần
string ans;
for (int i = 0; i < k; i++) ans += base;
cout << ans << "\n";
return 0;
}
Sub 2: Đếm một lần bằng mảng tần suất — ~O(n)~
Dùng mảng ~cnt[26]~ để đếm một lần duy nhất, sau đó xây dựng như trên. Đạt 29/29 test. Lưu ý kiểm tra ~n \bmod k~ trước để tránh in nhầm.
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int k;
string s;
cin >> k >> s;
int n = s.size();
// Chuỗi k-string gồm k lần lặp lại một chuỗi t, nên độ dài n chia hết cho k
// và số lần xuất hiện mỗi chữ cái phải chia hết cho k.
if (n % k != 0) {
cout << -1 << "\n";
return 0;
}
int cnt[26] = {0};
for (char c : s) cnt[c - 'a']++;
string t;
for (int c = 0; c < 26; c++) {
if (cnt[c] % k != 0) {
cout << -1 << "\n";
return 0;
}
// Mỗi đoạn t chứa cnt[c]/k chữ c
t += string(cnt[c] / k, (char)('a' + c));
}
// Lặp đoạn t k lần thì mỗi chữ cái đúng cnt[c] lần
string ans;
ans.reserve(n);
for (int i = 0; i < k; i++) ans += t;
cout << ans << "\n";
return 0;
}
Bình luận