Hướng dẫn giải của Khôi phục xâu 1
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.
Lời giải này đang bị ẩn cho đến khi bạn chọn mở ra.
Chúng tôi khuyên bạn nên tự thử giải bài trước. Việc mở lời giải có thể làm lộ mất ý tưởng chính trước khi bạn có cơ hội tự giải.
Bạn phải đăng nhập để mở lời giải này.
Đăng nhậpTác giả: , , ,
Editorial for lexstr: Khôi phục xâu 1
Hiểu bài toán
Cho một xâu s độ dài n, trong đó một số ký tự bị mờ được biểu diễn bằng '?'. Yêu cầu thay thế các ký tự '?' bằng các ký tự thường từ 'a' đến 'z' sao cho:
- Tần suất xuất hiện của mỗi ký tự c trong xâu sau khi khôi phục đúng bằng f_c.
- Xâu kết quả có thứ tự từ điển nhỏ nhất.
Giải thích thêm: Để xâu có thứ tự từ điển nhỏ nhất, ta cần ưu tiên đặt các ký tự có thứ tự từ điển nhỏ hơn ('a'<'b'<...) vào các vị trí '?' càng sớm càng tốt. Cụ thể, khi duyệt từ trái sang phải, tại vị trí '?' đầu tiên, ta nên thử các ký tự từ 'a' đến 'z'. Ký tự nào thỏa mãn điều kiện tần suất và cho phép tạo ra một xâu hợp lệ cho phần còn lại thì ta chọn ngay lập tức.
Các cách tiếp cận
Cách Greedy (Tham lam)
#include <iostream>
#include <string>
#include <vector>
using namespace std;
int main() {
int n;
cin >> n;
string s;
cin >> s;
vector<int> f(26, 0);
for (int i = 0; i < 26; ++i) {
cin >> f[i];
}
// 1. Giảm tần suất cho các ký tự có sẵn
for (char c : s) {
if (c != '?') {
f[c - 'a']--;
}
}
// Kiểm tra tần suất âm
for (int count : f) {
if (count < 0) {
cout << -1 << endl;
return 0;
}
}
// 2. Thay thế '?' theo thứ tự ưu tiên (a -> z)
// Logic: Duyệt từ trái sang phải, tại mỗi '?', thử từ 'a' đến 'z'.
// Nếu chọn ký tự đó mà tần suất còn lại đủ để lấp đầy các '?' khác, thì chọn.
// Để kiểm tra "đủ", ta cần biết còn bao nhiêu '?' và tổng tần suất còn lại.
// Tuy nhiên, các solution C nộp contest này chỉ đơn giản là:
// Duyệt qua các vị trí '?', tại đó thử từ 'a' đến 'z', nếu f[j] > 0 thì chọn và giảm f[j].
// Cách này đúng vì đề bài đảm bảo input có nghiệm, và ta chỉ cần xâu lexicographically nhỏ nhất.
// Việc chọn 'a' sớm nhất có thể luôn là tối ưu.
// Tuy nhiên, có một trường hợp edge case:
// Nếu ta chọn 'a' tại vị trí hiện tại, nhưng sau đó không còn 'a' nào nữa,
// trong khi các vị trí '?' sau đó vẫn cần được lấp đầy.
// Nhưng do ta duyệt từ a -> z, và f[j] > 0 mới chọn, nên cách này về cơ bản là đúng.
// Nhưng để chắc chắn 100% "đủ", ta cần kiểm tra:
// Remaining '?' positions = count_rem
// Remaining characters sum = sum(f)
// Nếu sum(f) < count_rem -> sai.
// Nhưng input đảm bảo có nghiệm.
//
// Thuật toán chính xác cho Greedy:
// Duyệt i từ 0 đến n-1:
// Nếu s[i] == '?':
// Duyệt k từ 0 đến 25:
// Nếu f[k] > 0:
// Giả sử chọn ký tự k.
// f[k]--.
// Nếu thỏa mãn điều kiện (tổng tần suất còn lại >= số '?' còn lại):
// Gán s[i] = 'a' + k, break vòng lặp.
// Nếu không, hoàn tác (f[k]++) và thử k tiếp theo.
//
// Code dưới đây là cách tiếp cận đơn giản hóa (thường dùng trong contest với dữ liệu弱).
// Nhưng để đảm bảo đúng cho mọi trường hợp, ta nên dùng cách kiểm tra tổng.
int remaining_q = 0;
for (char c : s) if (c == '?') remaining_q++;
for (int i = 0; i < n; ++i) {
if (s[i] == '?') {
// Thử từ 'a' đến 'z'
for (int j = 0; j < 26; ++j) {
if (f[j] > 0) {
// Giả định chọn j
f[j]--;
remaining_q--;
// Kiểm tra xem phần còn lại có khả thi không
// Tính tổng tần suất còn lại
int sum_f = 0;
for (int k = 0; k < 26; ++k) sum_f += f[k];
// Nếu tổng >= số '?' còn lại, thì đây là lựa chọn tốt nhất (vì đang duyệt từ nhỏ đến lớn)
// (Trường hợp đặc biệt: nếu là '?' cuối cùng, sum_f == 0)
if (sum_f >= remaining_q) {
s[i] = (char)('a' + j);
break; // Đã chọn xong, thoát vòng lặp j
}
// Nếu không thỏa mãn, hoàn tác và thử ký tự tiếp theo
f[j]++;
remaining_q++;
}
}
}
}
cout << s << endl;
return 0;
}
- Time Complexity: O(n * 26 * 26) ~ O(n)
- Space Complexity: O(n)
Đây là thuật toán tham lam chuẩn xác nhất.
- Đọc dữ liệu và đếm tần suất các ký tự có sẵn, giảm tần suất theo yêu cầu.
- Duyệt qua từng ký tự trong xâu:
- Nếu là ký tự thường, giữ nguyên.
- Nếu là '?', ta cần chọn một ký tự. Để xâu có thứ tự từ điển nhỏ nhất, ta ưu tiên chọn các ký tự có thứ tự từ điển nhỏ hơn trước ('a' trước 'b').
- Tuy nhiên, không phải lúc nào cũng có thể chọn 'a' được. Ví dụ, nếu chọn 'a' tại vị trí này mà sau đó không còn đủ tần suất để lấp đầy các vị trí '?' còn lại, ta phải chọn ký tự lớn hơn.
- Do đó, tại mỗi vị trí '?', ta duyệt qua các ký tự từ 'a' đến 'z'. Với mỗi ký tự, ta thử 'giảm' tần suất của nó đi 1. Sau đó kiểm tra xem tổng tần suất còn lại có đủ để lấp đầy các vị trí '?' còn lại hay không (tổng tần suất >= số lượng '?' còn lại).
- Nếu thỏa mãn, ta chọn ngay ký tự đó vì nó là nhỏ nhất có thể. Sau đó cập nhật tần suất và chuyển sang vị trí tiếp theo.
- Nếu duyệt hết mà không thể chọn ở bước 2 (trong khi input đảm bảo có nghiệm), ta in -1.
Cách Greedy Đơn giản hóa (Dùng cho contest)
#include <stdio.h>
#include <string.h>
int main() {
int n;
scanf("%d", &n);
char s[n + 1];
scanf("%s", s);
int f[26];
for (int i = 0; i < 26; i++) {
scanf("%d", &f[i]);
}
// Giảm tần suất cho các ký tự đã có
for (int i = 0; i < n; i++) {
if (s[i] != '?') {
f[s[i] - 'a']--;
if (f[s[i] - 'a'] < 0) {
printf("-1");
return 0;
}
}
}
// Lấp đầy các ký tự '?' từ a đến z
// Cách này chỉ đúng nếu input đảm bảo luôn có nghiệm và ta chỉ cần xâu bất kỳ.
// Nhưng để có xâu lexicographically nhỏ nhất, ta cần ưu tiên 'a' vào các vị trí '?' đầu tiên.
// Code này gán 'a' vào '?' đầu tiên, 'b' vào '?' tiếp theo... (theo thứ tự f[])
// Tuy nhiên, code dưới đây của Solution 1 thực chất là:
// Duyệt từng '?', từ a->z, chỗ nào f[j] > 0 thì chọn.
// Vì f[] được giảm từ các ký tự có sẵn, nên f[] còn lại chính là số lượng cần thêm.
// Và do ta ưu tiên j nhỏ nhất, nên kết quả sẽ là lexicographically nhỏ nhất.
//
// Lưu ý: Cách này bỏ qua việc kiểm tra tổng tần suất còn lại.
// Nó chỉ hoạt động đúng khi "số lượng '?' = tổng tần suất còn lại".
// Vì input đảm bảo tổng f = n, và ta đã trừ đi các ký tự có sẵn,
// nên số lượng '?' (chưa được gán) = tổng f[] còn lại.
// Do đó, ta chỉ cần chọn bất kỳ ký tự nào còn tần suất, và ưu tiên ký tự nhỏ nhất.
for (int i = 0; i < n; i++) {
if (s[i] == '?') {
for (int j = 0; j < 26; j++) {
if (f[j] > 0) {
s[i] = (char)('a' + j);
f[j]--;
break;
}
}
}
}
printf("%s", s);
return 0;
}
- Time Complexity: O(n * 26)
- Space Complexity: O(n)
Đây là cách tiếp cận đơn giản hơn, dựa trên giả định rằng tổng số lượng ký tự cần thêm (từ f[]) luôn bằng số lượng dấu '?'.
- Giảm tần suất các ký tự có sẵn.
- Duyệt qua xâu, gặp '?' thì chọn ký tự đầu tiên trong bảng chữ cái ('a' đến 'z') có tần suất còn lại > 0.
- Gán ký tự đó và giảm tần suất.
Cách này đúng vì:
- Xâu kết quả có thứ tự từ điển nhỏ nhất: Ta ưu tiên 'a' cho '?' đầu tiên, 'b' cho '?' thứ hai... (trong phạm vi tần suất cho phép).
- Đảm bảo tần suất: Vì tổng số '?' = tổng f[] sau khi trừ, nên việc lấp đầy lần lượt đảm bảo không còn thừa hay thiếu.
Cảnh báo: Nếu bài toán có thêm ràng buộc phức tạp hơn (ví dụ: chỉ được dùng một số ký tự nhất định ở một số vị trí), cách này có thể sai. Nhưng với bài này, nó là hợp lệ và phổ biến trong contest.
Cách Phương pháp tối ưu (Tính toán trước)
#include <iostream>
#include <string>
#include <vector>
#include <numeric>
using namespace std;
int main() {
int n;
cin >> n;
string s;
cin >> s;
vector<int> target(26);
for (int i = 0; i < 26; ++i) cin >> target[i];
// Đếm số lượng ký tự '?' và tần suất hiện tại
int q_count = 0;
vector<int> current(26, 0);
for (char c : s) {
if (c == '?') q_count++;
else current[c - 'a']++;
}
// Kiểm tra tính hợp lệ ban đầu
for (int i = 0; i < 26; ++i) {
if (current[i] > target[i]) {
cout << -1 << endl;
return 0;
}
}
// Tính số lượng cần thêm của mỗi ký tự
vector<int> need(26);
for (int i = 0; i < 26; ++i) need[i] = target[i] - current[i];
// Kiểm tra tổng cần thêm có bằng q_count không
int sum_need = 0;
for (int x : need) sum_need += x;
if (sum_need != q_count) {
cout << -1 << endl;
return 0;
}
// Duyệt lại xâu và gán
int ptr = 0; // Con trỏ duyệt mảng need
for (int i = 0; i < n; ++i) {
if (s[i] == '?') {
// Tìm ký tự đầu tiên cần thêm
while (ptr < 26 && need[ptr] == 0) ptr++;
if (ptr < 26) {
s[i] = (char)('a' + ptr);
need[ptr]--;
}
}
}
cout << s << endl;
return 0;
}
- Time Complexity: O(n + 26)
- Space Complexity: O(n)
Phương pháp này tách biệt việc tính toán số lượng và việc gán giá trị.
- Đọc dữ liệu, đếm số lượng '?' và tần suất các ký tự có sẵn.
- Tính mảng
need[26]thể hiện số lượng mỗi ký tự cần thêm. - Duyệt qua xâu, nếu gặp '?', ta gán lần lượt các ký tự theo thứ tự từ 'a' đến 'z' dựa trên mảng
need.- Ví dụ: Nếu
need['a']> 0, gán 'a' và giảmneed['a']. - Khi
need['a']= 0, sang 'b'.
- Ví dụ: Nếu
Vì ta muốn xâu lexicographically nhỏ nhất, việc gán lần lượt các ký tự nhỏ nhất có thể vào các '?' từ trái sang phải là chính xác. Phương pháp này hiệu quả và dễ hiểu, ít lỗi hơn so với việc kiểm tra điều kiện lặp lại.
Phân tích độ phức tạp
| Cách tiếp cận | Time | Space | Tên |
|---|---|---|---|
| 1 | O(n * 26 * 26) ~ O(n) | O(n) | Greedy (Tham lam) |
| 2 | O(n * 26) | O(n) | Greedy Đơn giản hóa (Dùng cho contest) |
| 3 | O(n + 26) | O(n) | Phương pháp tối ưu (Tính toán trước) |
Bài học kinh nghiệm
- Để xâu có thứ tự từ điển nhỏ nhất, ta phải ưu tiên đặt ký tự 'a' vào vị trí '?' đầu tiên, 'b' vào vị trí '?' thứ hai, v.v., miễn là tần suất cho phép.
- Các ký tự có sẵn trong xâu đã chiếm một phần tần suất, ta cần trừ chúng đi trước khi quyết định gán cho các vị trí '?'.
- Tổng số lượng ký tự cần thêm (từ tần suất còn lại) phải bằng chính xác số lượng dấu '?' trong xâu.
Lỗi thường gặp
- Quên kiểm tra xem tần suất của các ký tự có sẵn có vượt quá tần suất cho phép không (ví dụ: có quá nhiều 'a' trong xâu).
- Sai lệch trong việc nhập/xuất (như dùng
scanf("%c")có thể đọc nhầm ký tự newline). - Gán ngẫu nhiên các ký tự còn lại vào '?' mà không theo thứ tự ưu tiên 'a' -> 'z', dẫn đến kết quả không phải là nhỏ nhất.
Bình luận