Hướng dẫn giải của [Beginner Free Contest 19] FWORD
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 một xâu có các ô mờ '#', mỗi ô mờ có K chữ cái có thể điền. Các từ tạo được xếp theo thứ tự từ điển, cần tìm từ thứ X.
Sub 1: Thử tăng bộ đếm — ~O(X)~, dùng khi ~M = 1~ (khi đó ~X \le K \le 26~)
Khi chỉ có một ô mờ, các từ khác nhau đúng ở ô đó. Bắt đầu từ chữ cái nhỏ nhất (chữ đầu tiên sau khi sắp xếp) và tăng chỉ số lên ~X-1~ lần. Cách này không dùng được khi có nhiều ô mờ vì ~X~ có thể rất lớn.
Nếu chỉ nộp sub này: đúng 7/12 test.
Sub 2: Đổi số sang hệ mixed radix — ~O(N + M \log K)~, dùng khi mọi trường hợp còn lại
Thứ tự từ điển của các từ chính là thứ tự của dãy chỉ số lựa chọn, trong đó ô mờ bên trái là chữ số hàng cao nhất. Vì mỗi ô có số lựa chọn cố định, ta đổi ~X-1~ sang hệ có cơ số bằng số lựa chọn của từng ô, đi từ ô mờ bên phải sang bên trái. Mỗi chữ số cho biết chọn chữ cái nào trong danh sách đã sắp xếp của ô đó. Lưu ý: cần sắp xếp và bỏ các chữ cái trùng trong mỗi dòng gợi ý.
Nếu chỉ nộp sub này: đúng 12/12 test.
Chương trình hoàn chỉnh
Bài có hai subtask: ~M = 1~ (60%) và không ràng buộc thêm (40%). Sub 1 chỉ đúng khi ~M = 1~, còn sub 2 đúng cho mọi trường hợp.
Chương trình đọc ~N, M, K, X~ và xâu. Nếu ~M = 1~ thì gọi sub1, ngược lại gọi sub2.
#include <bits/stdc++.h>
using namespace std;
int N, M, K;
long long X;
string s; // xau: dau '#' la vi tri bi mo
vector<string> cand; // cand[i]: cac chu cai co the dien vao o mo thu i (da sap xep, khong trung)
// Sub 1: M = 1 (X <= K <= 26). Bat dau tu chu cai dau tien, tang bo dem X-1 lan.
void sub1() {
long long idx = 0;
for (long long step = 1; step < X; step++) idx++;
string res = s;
for (size_t p = 0; p < res.size(); p++)
if (res[p] == '#') { res[p] = cand[0][idx]; break; }
cout << res << "\n";
}
// Sub 2: tong quat. Cac tu sap xep tu dien tuong duong voi dem theo he mixed radix:
// o mo ben trai la chu so quan trong nhat. Doi X-1 ra he mixed radix roi chon chu cai tuong ung.
void sub2() {
vector<char> pick(M);
long long x = X - 1;
for (int i = M - 1; i >= 0; i--) {
long long b = cand[i].size();
pick[i] = cand[i][x % b];
x /= b;
}
string res;
int bi = 0;
for (size_t p = 0; p < s.size(); p++) {
if (s[p] == '#') res += pick[bi++];
else res += s[p];
}
cout << res << "\n";
}
int main() {
cin >> N >> M >> K >> X;
cin >> s;
cand.resize(M);
for (int i = 0; i < M; i++) {
string t;
cin >> t;
sort(t.begin(), t.end());
t.erase(unique(t.begin(), t.end()), t.end());
cand[i] = t;
}
if (M == 1) sub1();
else sub2();
return 0;
}
Bình luận