牛牛的近亲数

[编程题]牛牛的近亲数

热度指数：128 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

牛牛在研究数字，他非常喜欢各数位之间数字差异小的数。所以他定义了一种“近亲数”，他规定一个正整数中如果最大数字<=最小数字*2，那么这个正整数数就叫做近亲数。

举个例子，1,9,11,968,874都是近亲数，10,625,407,33542都不是近亲数。

牛牛想知道闭区间[L,R]中共有多少个近亲数，你能告诉牛牛吗？

输入描述:

第一行一个正整数T代表查询次数。
接下来两行每行两个正整数L,R，代表要查询的区间。

输出描述:

输出T行，每行一个整数，代表闭区间[L,R]中近亲数的个数。

示例1

输入

输出

9
1
0

算法知识视频讲解

heartのc

数字不是很多，暴力打个表，然后二分。

#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;
}

发表于 2021-02-06 20:28:18 回复(0)