Hướng dẫn giải của FWORD
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
Từ có ~N~ kí tự, ~M~ vị trí bị mờ (dấu #). Mỗi vị trí mờ có ~K~ chữ cái được phép. Các từ sắp xếp tăng dần tương ứng với hệ đếm hỗn hợp cơ số ~K~, nên từ thứ ~X~ tương ứng với số ~X-1~ viết trong hệ cơ số ~K~.
Sub 1: liệt kê hết từ — dùng khi ~K^M \le 10^6~
Sinh tất cả các từ, sắp xếp rồi lấy từ thứ ~X~. Nếu chỉ nộp sub này: đúng 8/12 test.
Sub 2: hệ đếm hỗn hợp — ~O(M)~
Lấy ~X-1~ trong hệ cơ số ~K~ với ~M~ chữ số, chữ số cuối ứng với dấu # cuối cùng. Đúng 12/12 test.
Chương trình hoàn chỉnh
main đọc dữ liệu và sắp xếp các chữ cho từng vị trí mờ. Nếu ~K^M \le 10^6~ 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 w; // xau co dau # o cac vi tri bi mo
vector<string> opt; // opt[i]: k chu cai co the dien vao vi tri mo thu i (da sap xep)
vector<int> pos; // vi tri cua cac dau # trong xau
// Sub 1: liet ke het cac tu (k^m <= 10^6), sap xep roi lay tu thu X. Dung khi tong so tu nho.
void sub1() {
vector<string> all;
vector<int> idx(m, 0);
while (true) {
string t = w;
for (int i = 0; i < m; i++) t[pos[i]] = opt[i][idx[i]];
all.push_back(t);
int i = m - 1;
while (i >= 0 && ++idx[i] == k) { idx[i] = 0; i--; }
if (i < 0) break;
}
sort(all.begin(), all.end());
cout << all[X - 1] << "\n";
}
// Sub 2: cac tu xep theo thu tu tu dien = he dem hon hop co so k, chu so hang cao nhat ung voi dau # dau tien.
// Lay chu so cua X-1 o he co so k, tu dau # cuoi cung len dau.
void sub2() {
long long idx = X - 1;
for (int i = m - 1; i >= 0; i--) {
int d = idx % k;
idx /= k;
w[pos[i]] = opt[i][d];
}
cout << w << "\n";
}
int main() {
cin >> n >> m >> k >> X;
cin >> w;
for (int i = 0; i < n; i++)
if (w[i] == '#') pos.push_back(i);
opt.resize(m);
for (int i = 0; i < m; i++) {
cin >> opt[i];
sort(opt[i].begin(), opt[i].end());
}
// Dung sub1 khi so tu k^m nho (<= 10^6)
double total = 1;
for (int i = 0; i < m; i++) total *= k;
if (total <= 1e6) sub1();
else sub2();
return 0;
}
Bình luận