Hướng dẫn giải của [Beginner Free Contest 09] LEXSTR
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
Các chữ ~?~ phải được điền sao cho đủ tần số ~f_c~ của mỗi chữ cái. Để xâu nhỏ nhất theo từ điển, duyệt từ trái sang phải và tại mỗi ~?~ chọn chữ cái nhỏ nhất còn có thể dùng. Nếu tần số các chữ đã đặt vượt quá ~f_c~ thì không có đáp án.
Sub 1: Kiểm tra lại toàn bộ xâu — ~O(n^2 \cdot 26)~, dùng khi ~n \le 100~
Với mỗi ~?~, thử các chữ ~a \dots z~ và kiểm tra lại đếm chữ cái của cả xâu. Cuối cùng kiểm tra đủ đúng tần số. Nếu chỉ nộp sub này: đúng 20/20 test.
Sub 2: Đếm tần số con thiếu — ~O(26 \cdot n)~
Giữ mảng đếm ~cnt~ và mỗi ~?~ lấy chữ cái nhỏ nhất có ~cnt[c] < f_c~. Cách này tương đương sub 1 nhưng không cần kiểm tra lại xâu. Nếu chỉ nộp sub này: đúng 20/20 test.
Chương trình hoàn chỉnh
~main~ đọc xâu và tần số, nếu ~n \le 100~ gọi sub1, ngược lại gọi sub2.
#include <bits/stdc++.h>
using namespace std;
int n;
string s;
int f[26];
// Kiem tra xau t (con '?') co chu cai nao vuot qua so lan f[c] khong
bool fits(const string &t) {
int cnt[26] = {0};
for (char ch : t)
if (ch != '?') cnt[ch - 'a']++;
for (int c = 0; c < 26; c++)
if (cnt[c] > f[c]) return false;
return true;
}
// Sub 1: vet can (n <= 100): voi moi '?' thu lan luot a..z, chon chu cai nho nhat
// ma xau van hop le (kiem tra lai ca xau).
void sub1() {
string t = s;
for (int i = 0; i < n; i++) {
if (t[i] != '?') continue;
bool placed = false;
for (char c = 'a'; c <= 'z' && !placed; c++) {
t[i] = c;
if (fits(t)) placed = true;
}
if (!placed) { cout << -1 << "\n"; return; }
}
int cnt[26] = {0};
for (char ch : t) cnt[ch - 'a']++;
for (int c = 0; c < 26; c++)
if (cnt[c] != f[c]) { cout << -1 << "\n"; return; }
cout << t << "\n";
}
// Sub 2: O(26 n). Dem so lan con thieu cua tung chu cai; moi '?' lay chu cai nho nhat con thieu.
void sub2() {
int cnt[26] = {0};
for (char ch : s)
if (ch != '?') cnt[ch - 'a']++;
for (int c = 0; c < 26; c++)
if (cnt[c] > f[c]) { cout << -1 << "\n"; return; }
string t = s;
for (int i = 0; i < n; i++) {
if (t[i] != '?') continue;
int c = 0;
while (c < 26 && cnt[c] >= f[c]) c++;
if (c == 26) { cout << -1 << "\n"; return; }
t[i] = 'a' + c;
cnt[c]++;
}
cout << t << "\n";
}
int main() {
cin >> n >> s;
for (int c = 0; c < 26; c++) cin >> f[c];
if (n <= 100) sub1();
else sub2();
return 0;
}
Bình luận