牛牛在研究数字,他非常喜欢各数位之间数字差异小的数。所以他定义了一种“近亲数”,他规定一个正整数中如果最大数字<=最小数字*2,那么这个正整数数就叫做近亲数。
举个例子,1,9,11,968,874都是近亲数,10,625,407,33542都不是近亲数。
牛牛想知道闭区间[L,R]中共有多少个近亲数,你能告诉牛牛吗?
第一行一个正整数T代表查询次数。
接下来两行每行两个正整数L,R,代表要查询的区间。
输出T行,每行一个整数,代表闭区间[L,R]中近亲数的个数。
3 1 9 21 21 13 20
9 1 0
#include <bits/stdc++.h> using namespace std; typedef long long ll; vector<ll> a; int const LIMIT = 1e8; void dfs(int l, int r, int sum) { if (sum > LIMIT) { return; } if (sum > 0) { a.emplace_back(sum); } for (int i = l; i <= r; i++) { dfs(l, r, sum * 10 + i); } } int main(void) { vector<pair<int, int>> p = { {1, 2}, {2, 4}, {3, 6}, {4, 8}, {5, 9} }; for (auto& x : p) { dfs(x.first, x.second, 0); } sort(a.begin(), a.end()); a.erase(unique(a.begin(), a.end()), a.end()); int t; cin >> t; while (t--) { int l, r; cin >> l >> r; int pos1 = lower_bound(a.begin(), a.end(), l) - a.begin(); int pos2 = upper_bound(a.begin(), a.end(), r) - a.begin(); cout << pos2 - pos1 << endl; } return 0; }