Hướng dẫn giải của [2526 KS2 THCS] Bài 3: Ghép chữ số 9 [BAI3]
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ỗi lần gộp hai chữ số kề nhau có tổng 9 thành một chữ số 9. Đếm số xâu khác nhau đạt số chữ số 9 nhiều nhất.
Sub 1: Sinh xâu bằng BFS, ~|a| \le 18~ ~O(2^{|a|})~
Sinh mọi xâu có thể đạt được và đếm xâu có nhiều chữ số 9 nhất. Chạy riêng subtask này đạt 15/33 test.
Sub 2: Công thức, ~|a| \le 10^5~ ~O(|a|)~
Các cặp hợp lệ (tổng 9) tạo thành đoạn liên tiếp. Đoạn có v chữ số cho (v+1)/2 cách nếu v lẻ, 1 cách nếu v chẵn; đáp số là tích các cách. Chạy riêng subtask này đạt 33/33 test.
Chương trình hoàn chỉnh
Nếu |a| <= 18 dùng sub 1, ngược lại dùng sub 2.
#include <bits/stdc++.h>
using namespace std;
string a;
// Sub 1: sinh moi xau dat duoc bang BFS (dung khi so chu so <= 18), dem so xau co nhieu chu so 9 nhat
void sub1() {
set<string> seen;
queue<string> q;
seen.insert(a);
q.push(a);
while (!q.empty()) {
string t = q.front();
q.pop();
for (size_t i = 0; i + 1 < t.size(); i++) {
if ((t[i] - '0') + (t[i + 1] - '0') == 9) {
string nt = t.substr(0, i) + "9" + t.substr(i + 2);
if (!seen.count(nt)) {
seen.insert(nt);
q.push(nt);
}
}
}
}
int best = -1;
long long cnt = 0;
for (const string& t : seen) {
int c = count(t.begin(), t.end(), '9');
if (c > best) { best = c; cnt = 1; }
else if (c == best) cnt++;
}
cout << cnt << "\n";
}
// Sub 2: cong thuc O(N). Chu so 9 chi tao ra tu cap lien ke co tong 9 (khong ghep duoc voi 9).
// Cac cap hop le lien tiep tao thanh doan v chu so (v = so cap + 1): co (v+1)/2 cach ghep toi da neu v le,
// 1 cach neu v chan. Ket qua la tich cac cach cua moi doan.
void sub2() {
int n = a.size();
auto ok = [&](int p) { return (a[p] - '0') + (a[p + 1] - '0') == 9; };
long long ans = 1;
int i = 0;
while (i < n - 1) {
if (!ok(i)) { i++; continue; }
int j = i;
while (j < n - 1 && ok(j)) j++;
int v = (j - i) + 1;
if (v % 2 == 1) ans *= (v + 1) / 2;
i = j;
}
cout << ans << "\n";
}
int main() {
cin >> a;
if (a.size() <= 18) sub1();
else sub2();
return 0;
}
Bình luận