Hướng dẫn giải của Số cởi mở (Đề Long An 2021)
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
Đếm chữ số cởi mở trong S và tìm số cởi mở lớn nhất tạo từ xâu con của S.
Sub 1: Vét cạn, ~O(n^3)~
Xét mọi xâu con liên tiếp toàn chữ số cởi mở (1, 2, 3, 5, 7), lấy xâu lớn nhất. Nếu chỉ nộp sub này: đúng 10/10 test.
Sub 2: Duyệt các đoạn liên tiếp, ~O(n)~
Mỗi đoạn chữ số cởi mở liên tiếp cho ra số lớn nhất của đoạn đó là chính đoạn đó (không có số 0 đứng đầu), nên chỉ cần so sánh các đoạn. Đúng 10/10 test.
Chương trình hoàn chỉnh
main đọc S và gọi sub1 (|S| ≤ 250). Khi đi thi nên viết như vậy: sub sau có sai hoặc chưa kịp làm thì vẫn ăn điểm sub trước.
#include <bits/stdc++.h>
using namespace std;
string S;
// Chu so coi mo: 1, 2, 3, 5, 7 (khong co duong khep kin)
bool openDigit(char c) {
return c == '1' || c == '2' || c == '3' || c == '5' || c == '7';
}
// Tra ve true neu a "lon hon" b: so dai hon thi lon hon; cung do dai thi so sanh tung chu so
// (cac chu so coi mo khac 0 nen khong co so 0 dau)
bool better(const string &a, const string &b) {
if (a.size() != b.size()) return a.size() > b.size();
return a > b;
}
// Sub 1: vet can. Voi moi xau con S[i..j], neu toan chu so coi mo thi xet xem no co lon nhat khong
void sub1() {
int n = S.size();
int cnt = 0;
for (char c : S)
if (openDigit(c)) cnt++;
string best = "";
for (int i = 0; i < n; i++)
for (int j = i; j < n; j++) {
if (!openDigit(S[j])) break; // xau con dai hon chua chu so khong coi mo thi bo
string cand = S.substr(i, j - i + 1);
if (better(cand, best)) best = cand;
}
cout << cnt << "\n" << best << "\n";
}
// Sub 2: chi can xet cac doan chu so coi mo lien tiep (moi doan la mot xau con cuc dai).
// Xau con lon nhat tao tu mot doan la chinh doan do (them chu so vao dau chi lam so lon hon).
void sub2() {
int cnt = 0;
string best = "", run = "";
for (char c : S) {
if (openDigit(c)) {
cnt++;
run += c;
} else {
if (better(run, best)) best = run;
run = "";
}
}
if (better(run, best)) best = run;
cout << cnt << "\n" << best << "\n";
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> S;
if (S.size() <= 250) sub1(); // do dai S toi da 250: vet can O(n^3) van nhanh
else sub2();
return 0;
}
Bình luận