定义一个数的幸运值是这个数的数位的最大值减去最小值,如 \(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;
}
- Codeforces Numbers Round Lucky 861codeforces numbers round lucky codeforces round 861 div 题解codeforces round 861 educational codeforces numbers round codeforces chains 1766d lucky codeforces divisible numbers version codeforces numbers 1841c ranom educational codeforces round rated codeforces round 911 div codeforces round 864 div