Hướng dẫn giải của [VT Thiếu nhi] BÀI 14: SIMILAR
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
Hai số là "tương đồng" nếu có cùng tổng chữ số. Cần tìm hiệu lớn nhất giữa hai số tương đồng nằm trong đoạn ~[l, r]~, với ~r \le 10^7~. Đề không nói rõ trường hợp không có cặp nào; lời giải in 0 trong trường hợp đó.
Sub 1: Vét cạn — ~O((r - l)^2 \log r)~, dùng khi ~r - l \le 2000~
Thử mọi cặp ~i < j~ trong đoạn; nếu cùng tổng chữ số thì cập nhật hiệu ~j - i~ lớn nhất. Nếu chỉ nộp sub này: đúng 10/20 test (các test lớn bị quá giờ).
Sub 2: Min và max theo tổng chữ số — ~O((r - l) \log r)~
Với mỗi tổng chữ số ~s~, chỉ cần số nhỏ nhất và số lớn nhất có tổng chữ số ~s~ trong đoạn. Đáp án là ~\max_s (mx_s - mn_s)~. Với ~r \le 10^7~ tổng chữ số không vượt 63, nên dùng mảng 100 phần tử. Nếu chỉ nộp sub này: đúng 20/20 test.
Chương trình hoàn chỉnh
~main~ đọc ~l, r~. Nếu ~r - l \le 2000~ gọi sub1, ngược lại gọi sub2.
#include <bits/stdc++.h>
using namespace std;
long long l, r;
// Tong chu so cua x
int digitSum(long long x) {
int s = 0;
while (x > 0) { s += x % 10; x /= 10; }
return s;
}
// Sub 1: vet can. Thu moi cap i < j trong [l,r] co cung tong chu so, lay hieu j - i lon nhat.
// O((r-l)^2 * log). Dung khi r - l <= 2000.
void sub1() {
long long best = 0;
for (long long i = l; i <= r; i++)
for (long long j = i + 1; j <= r; j++)
if (digitSum(i) == digitSum(j)) best = max(best, j - i);
cout << best << "\n";
}
// Sub 2: voi moi tong chu so s, chi can so nho nhat va lon nhat co tong chu so s trong [l,r].
// Hieu lon nhat = max over s (max_s - min_s). O((r-l) * log r).
void sub2() {
const int MAXS = 100; // tong chu so <= 63 voi r <= 10^7
vector<long long> mn(MAXS, LLONG_MAX), mx(MAXS, LLONG_MIN);
for (long long x = l; x <= r; x++) {
int s = digitSum(x);
mn[s] = min(mn[s], x);
mx[s] = max(mx[s], x);
}
long long best = 0;
for (int s = 0; s < MAXS; s++)
if (mx[s] != LLONG_MIN) best = max(best, mx[s] - mn[s]);
cout << best << "\n";
}
int main() {
freopen("SIMILAR.INP", "r", stdin);
freopen("SIMILAR.OUT", "w", stdout);
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> l >> r;
if (r - l <= 2000) sub1();
else sub2();
return 0;
}
Bình luận