Codeforces Round 861 (Div. 2) A. Lucky Numbers
定义一个数的幸运值是这个数的数位的最大值减去最小值，如 \(luckiness_{769} = 9 - 6 = 3\) 。给出 \(l\) \(r\) ，求 \([l, r]\) 中最幸运的数，若最幸运的数有多个，任意一个为答案。
考虑拆分数位，然后枚举。以 \(O(d)\) 的复杂度计算幸运值。则线性扫一遍的复杂度为 \(O(n d)\) 。由 \(1 \leq l < r \leq 10^6\) ， \(d_{max} = 6\) 。\(t\) 组数据的上限复杂度为 \(O(t n d)\) ，达到 \(1E9\) 级别。
性质：连续 \(100\) 个数中对 \(100\) 取模的余数取遍 \([0, 99]\) ，也就是最后两位取遍 \([0, 99]\) 。
于是可以 \(O(1)\) 计算答案，遍历 \([l, min(l + 99, r)]\) 即可。
view
#include <bits/stdc++.h>
void solve() {
int l, r; std::cin >> l >> r; r = std::min(l + 99, r);
auto get = [&](int x) {
std::vector<int> d;
while (x) {
d.push_back(x % 10);
x /= 10;
}
return *max_element(d.begin(), d.end()) - *min_element(d.begin(), d.end());
};
int mx = 0, p = l;
for (int i = l; i <= r; i++) if (mx < get(i)) { mx = get(i); p = i; }
std::cout << p << '\n';
}
signed main() {
int _ = 1; std::cin >> _;
while (_--) { solve(); }
return 0;
}