给定一个正整数 n,保证 n 的十进制表示不含 47 以外的数字。请你统计,[1,n] 范围内一共有多少个正整数满足其十进制表示不含 47 以外的数字。注意,统计时不要漏掉 n

输入格式

一个正整数 n

输出格式

一个整数,表示满足条件的正整数数量。

数据范围

前 3 个测试点满足 1 ≤ n ≤ 100。 所有测试点满足 1 ≤ n ≤ 10^9。

输入样例1

4

输出样例1

1

输入样例2

7

输出样例2

2

输入样例3

77

输出样例3

6

题目分析

  • DFS 出 1e9 以内的符合条件的数
  • 将这些数存于数组内
  • 由小到大排序
  • 二分查找 n 对应的下标(这里有前缀和的思想)
  • 或者使用哈希表

代码实现

#include <iostream>
#include <set>
using namespace std;
using LL = unsigned long long;
const int N = 10;

LL n;
set <LL> st;
void dfs(LL num, LL digit) {
    if (digit > N) return ;
    if(st.find(num) == st.end()) st.insert(num);
    dfs(num * 10 + 7, digit + 1), dfs(num* 10 + 4, digit + 1);
}
int main () {
    ios::sync_with_stdio(0);
    cin.tie(0);
    dfs(4,1), dfs(7,1);
    cin >> n;
    LL cnt = 0;
    for(auto val : st) {
        if(val > n) break;
        ++cnt;
    }
    cout << cnt;
    return 0;
}

0 条评论

发表回复

Avatar placeholder

您的电子邮箱地址不会被公开。 必填项已用*标注

友情链接:Ctips' blog, Colza’s blog

站点状态:Status