12088: 755

12088: 755

时间限制: 1 Sec   内存限制: 128 MB

题目描述

You are given an integer N. Among the integers between 1 and N (inclusive), how many Shichi-Go-San numbers (literally "Seven-Five-Three numbers") are there?

Here, a Shichi-Go-San number is a positive integer that satisfies the following condition:

When the number is written in base ten, each of the digits 7, 5 and 3 appears at least once, and the other digits never appear.
Constraints
1≤N<10⁹
N is an integer.

输入

Input is given from Standard Input in the following format:

N

输出

Print the number of the Shichi-Go-San numbers between 1 and N (inclusive).

样例输入 Copy

575

样例输出 Copy

4

提示

There are four Shichi-Go-San numbers not greater than 575: 357,375,537 and 573.

解析：这道题我一开始报错因为遗漏了每个数字至少出现一次的条件。

dfs bfs都可以，我用的是dfs

#include<bits/stdc++.h>

using namespace std;

long long a;

bool b[5];

int n;long long now;

int dfs(int x){

// cout<<now<<endl;

int ans=0;

if(x>=3){

int know=now;b[1]=0;b[2]=0;b[3]=0;

while(know){

if(know%10==3)b[1]=1;

else if(know%10==5) b[2]=1;

else b[3]=1;

know/=10;

}

if(now<=a){

if(b[1]&&b[2]&&b[3]) ans=1;

}

}

if(x>=n) return ans;

now=now*10+3;ans+=dfs(x+1);now/=10;

now=now*10+5;ans+=dfs(x+1);now/=10;

now=now*10+7;ans+=dfs(x+1);now/=10;

return ans;

}

int main(){

scanf("%lld",&a);

long long i=a;n=0;

while(i){n++;i/=10;}now=0;

cout<<dfs(0)<<endl;

return 0;

}