Hướng dẫn giải của Số đối xứng (Đề chọn ĐTQG Phú Thọ 2015-2016)
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
Số đối xứng là số đọc xuôi và ngược giống nhau. Cần đếm số đối xứng trong đoạn [a; b], với b lên tới 10^{18}. Đáp án bằng F(b) - F(a - 1), trong đó F(N) là số đối xứng không lớn hơn N.
Sub 1: Vét cạn — ~O(b - a)~, dùng khi ~b \le 10^6~
Duyệt từng số trong đoạn và kiểm tra đối xứng. Nếu chỉ nộp sub này: đúng 24/32 test.
Sub 2: Đếm theo độ dài — ~O(\text{số chữ số}^2)~
Số đối xứng có L chữ số được quyết định bởi nửa đầu gồm h = (L+1)/2 chữ số, có 9 \cdot 10^{h-1} cách. Với độ dài bằng độ dài N, lấy nửa đầu P của N, tạo số đối xứng S từ P. Nếu S không lớn hơn N thì P được tính, nên số lượng là P - 10^{h-1} + 1; ngược lại là P - 10^{h-1}. So sánh S với N bằng chuỗi, vì cùng độ dài. Sub 2 đúng 32/32 test.
Chương trình hoàn chỉnh
Hàm main đọc a, b. Nếu b \le 10^6 gọi sub 1, còn lại gọi sub 2.
#include <bits/stdc++.h>
using namespace std;
long long a, b;
// Kiểm tra x có phải số đối xứng (đọc xuôi và ngược giống nhau)
bool isPal(long long x) {
string s = to_string(x);
string r(s.rbegin(), s.rend());
return s == r;
}
// Sub 1: thử từng số trong [a, b], O(b - a) * số chữ số. Dùng khi b <= 10^6.
void sub1() {
long long cnt = 0;
for (long long x = a; x <= b; x++)
if (isPal(x)) cnt++;
cout << cnt << "\n";
}
// Sub 2: đếm F(N) = số đối xứng trong [1, N], rồi đáp án = F(b) - F(a - 1).
// Số đối xứng có L chữ số được xác định bởi nửa đầu h = ceil(L / 2) chữ số:
// - số đối xứng L chữ số có đúng 9 * 10^(h-1) cách (chữ số đầu khác 0);
// - với L = độ dài của N: lấy nửa đầu P của N, đối xứng của P là S. Nếu S <= N thì P được tính,
// số lượng là P - 10^(h-1) + 1; nếu S > N thì P - 10^(h-1).
long long F(long long N) {
if (N <= 0) return 0;
string s = to_string(N);
int L = s.size();
long long total = 0;
// các độ dài nhỏ hơn L: đếm đầy đủ
for (int len = 1; len < L; len++) {
int h = (len + 1) / 2;
long long pw = 1;
for (int i = 1; i < h; i++) pw *= 10;
total += 9 * pw;
}
// độ dài bằng L
int h = (L + 1) / 2;
long long lowP = 1;
for (int i = 1; i < h; i++) lowP *= 10; // 10^(h-1)
string prefix = s.substr(0, h);
long long P = stoll(prefix);
// tạo số đối xứng S từ P (độ dài L)
string mirror = prefix;
string rev(prefix.rbegin(), prefix.rend());
if (L % 2 == 0) mirror += rev;
else mirror += rev.substr(1);
// so sánh S với N (cùng độ dài, so sánh chuỗi là đúng)
total += P - lowP + (mirror <= s ? 1 : 0);
return total;
}
// Sub 2: công thức đếm O(số chữ số^2)
void sub2() {
cout << F(b) - F(a - 1) << "\n";
}
int main() {
freopen("CAU2.INP", "r", stdin);
freopen("CAU2.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