Hướng dẫn giải của Bốc số
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
Với mỗi lá thăm (dãy ~N~ chữ số, ~N \le 100~, và số ~k~), chọn một dãy con các chữ số giữ nguyên thứ tự, không bắt đầu bằng số 0, chia hết cho 5 (nếu ~k = 0~) hoặc chia hết cho 3 (nếu ~k = 1~), sao cho số tạo thành là lớn nhất.
Sub 1: vét cạn tập con — ~O(2^N \cdot N)~, dùng khi ~N \le 18~
Thử mọi tập con chữ số, giữ tập con chia hết và có giá trị lớn nhất. Nếu chỉ nộp sub này: đúng 4/20 test.
Sub 2: quy hoạch theo số dư — ~O(N \cdot M)~ với ~M \in \{3, 5\}~
Với mỗi số dư ~r~, giữ chuỗi con lớn nhất có số dư ~r~ trong tiền tố đã xét. Hai chuỗi cùng số dư thì chuỗi lớn hơn luôn cho kết quả lớn hơn sau mỗi lần nối thêm chữ số, nên chỉ cần giữ một chuỗi. Đúng 20/20 test.
Chương trình hoàn chỉnh
main đọc t và từng lá thăm. Nếu ~N \le 18~ thì gọi sub1, ngược lại gọi sub2.
#include <bits/stdc++.h>
using namespace std;
string s; // day chu so cua la tham hien tai
int k; // dieu kien: k=0 thi chia het cho 5, k=1 thi chia het cho 3
// So sanh hai so viet duoi dang chuoi (khong co so 0 o dau):
// so dai hon thi lon hon, cung do dai thi so sanh tu dien.
bool greaterNum(const string &a, const string &b) {
if (a.size() != b.size()) return a.size() > b.size();
return a > b;
}
// Sub 1: vet can moi tap con cac chu so (N <= 18). Moi tap con kiem tra chia het, lay so lon nhat.
void sub1() {
int N = s.size(), M = (k == 0 ? 5 : 3);
string best = "";
for (int mask = 1; mask < (1 << N); mask++) {
string t;
for (int i = 0; i < N; i++)
if (mask >> i & 1) t += s[i];
if (t[0] == '0') continue;
int r = 0;
for (char c : t) r = (r * 10 + (c - '0')) % M;
if (r == 0 && greaterNum(t, best)) best = t;
}
cout << best << "\n";
}
// Sub 2: quy hoach theo so du. best[r] = so lon nhat (chuoi con cua tien to da xet) co so du r.
// Voi cung so du, so lon hon cho ket qua lon hon sau moi lan them chu so, nen chi can giu mot so cho moi so du.
void sub2() {
int M = (k == 0 ? 5 : 3);
vector<string> best(M);
vector<bool> has(M, false);
for (char ch : s) {
int d = ch - '0';
vector<string> nb = best;
vector<bool> nh = has;
auto upd = [&](int r, const string &cand) {
if (!nh[r] || greaterNum(cand, nb[r])) { nb[r] = cand; nh[r] = true; }
};
if (d != 0) upd(d % M, string(1, ch)); // bat dau mot so moi
for (int r = 0; r < M; r++)
if (has[r]) upd((r * 10 + d) % M, best[r] + ch); // noi chu so vao so cu
best = nb;
has = nh;
}
cout << (has[0] ? best[0] : string("")) << "\n";
}
int main() {
freopen("B2.INP", "r", stdin);
freopen("B2.OUT", "w", stdout);
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t;
cin >> t;
while (t--) {
cin >> s >> k;
if (s.size() <= 18) sub1();
else sub2();
}
return 0;
}
Bình luận