Hướng dẫn giải của Số lẻ (đề Cần Thơ 2021)
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 các số nguyên trong đoạn ~[a, b]~ có tổng các chữ số là số lẻ, với ~b \le 10^9~. Đặt ~cnt(n)~ là số lượng số trong ~[0, n]~ thỏa mãn thì đáp án là ~cnt(b) - cnt(a-1)~.
Sub 1: Duyệt từng số — ~O(b-a)~, dùng khi ~b \le 10^6~
Với mỗi số tính tổng chữ số và đếm. Nếu chỉ nộp sub này: đúng 28/30 test (2 test lớn quá thời gian).
Sub 2: Đếm theo chữ số — ~O(\log b)~
Để tính ~cnt(n)~, duyệt các chữ số của ~n~ từ trái sang phải; tại vị trí ~i~ thử các chữ số ~d~ nhỏ hơn chữ số của ~n~, các vị trí còn lại ~k~ điền tự do. Nếu ~k \ge 1~ thì đúng một nửa trong ~10^k~ cách điền cho tổng lẻ (đổi chữ số cuối đổi tính chẵn lẻ); nếu ~k = 0~ thì xét trực tiếp tính chẵn lẻ của tổng. Cuối cùng cộng thêm chính ~n~ nếu tổng chữ số của nó lẻ. Nộp riêng sub này đúng 30/30 test.
Chương trình hoàn chỉnh
Hàm ~main~ đọc ~a, b~; nếu ~b \le 10^6~ gọi sub1, ngược lại gọi sub2. 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. Chương trình đạt 30/30 test.
#include <bits/stdc++.h>
using namespace std;
long long a, b;
int digitSum(long long x) {
int s = 0;
while (x) { s += x % 10; x /= 10; }
return s;
}
// Sub 1: duyệt từng số trong [a, b], O(b - a), dùng khi b <= 10^6
void sub1() {
long long cnt = 0;
for (long long x = a; x <= b; x++)
if (digitSum(x) % 2 == 1) cnt++;
cout << cnt << "\n";
}
// đếm số trong [0, n] có tổng chữ số lẻ
long long countOdd(long long n) {
if (n < 0) return 0;
string s = to_string(n);
int len = s.size();
long long res = 0;
int par = 0; // tính chẵn lẻ của tổng các chữ số đã cố định ở đầu
for (int i = 0; i < len; i++) {
int rest = len - i - 1; // số vị trí còn tự do phía sau
long long total = 1;
for (int j = 0; j < rest; j++) total *= 10;
for (int d = 0; d < s[i] - '0'; d++) {
int p = (par + d) & 1;
if (rest == 0) res += p; // không còn chữ số nào: chỉ xét p
else res += total / 2; // đúng một nửa cách điền cho tổng lẻ
}
par = (par + s[i] - '0') & 1;
}
res += par; // chính n
return res;
}
// Sub 2: quy hoạch chữ số — đáp án = countOdd(b) - countOdd(a-1), O(log b)
void sub2() {
cout << countOdd(b) - countOdd(a - 1) << "\n";
}
int main() {
freopen("sole.inp", "r", stdin);
freopen("sole.out", "w", stdout);
ios::sync_with_stdio(false); cin.tie(nullptr);
cin >> a >> b;
if (b <= 1000000) sub1();
else sub2();
return 0;
}
Bình luận