753数[AtCoder-4276]简析
题意:从1到N,有多少个数字含有且仅含有3,5,7,程序输出这个数量
数学模型就是小于等于T的正整数中,有多少个数字仅含7,5,3并且7,5,3三个数都有。最小的一个显然是357,次大的是375。给具有这种性质的数字起个名字就叫“357数”。如果一个数字仅含3,5,7,但可能不全含有,我们给这种性质的数字称为“偏357数”。如果k是357数,那么给k后边续一位3,或者5,或者7的时候,它们仍然是357数。如果k是“偏357数”,也是可能形成357数的,比如3335,后续一位7仍然能形成”357数”。
我们记下一个“偏357数”的三个状态:含有3,含有5,含有7。函数f(int k,bool r3,bool r5,bool r7) 表示一个”偏357数”或”357数”k,当r3与r5与r7都是true时,k是357数,否则是偏357数。
如果k不大于T,为它后续一个3并令r3=true,后续5并令r5=true,后续7并令r7=true,这样新得到的数k*10+3,k*10+5,k*10+7就是新的”偏357数”或”357数”,就是调用要f(k*10+3,true,r5,r7),f(k*10+5,r3,true,r7),f(k*10+7,r3,r5,true).每次调用f()先看k的三个标志位是否全为true,若是则增加计数。直到当k超过T时结束判断,输出357数的计数结果。
除了用三个变量分别标明状态,还可以用一个数字作为标志位。r3,r5,r7表示分别用二进数001B,010B,100B表示,每次得到新的数就用标志进行按位或运算flag|1,flag|2,flag|4,当标志位flag是111B=7的时候说明此数是357数。
递归写法比较简短
[Python 3]
def dfs(s,flag):
if s>N:
return 0
ret =1 if flag==7 else 0
ret+=dfs(s*10+3,flag|1)
ret+=dfs(s*10+5,flag|2)
ret+=dfs(s*10+7,flag|4)
return ret
N=int(input())
print(dfs(0,0)
[C++]
#include <cstdio>
int N,count=0;
void dfs(long long,unsigned char);
int main(void)
{
scanf("%d",&N);
dfs(0,0);
printf("%d\n",count);
return 0;
}
void dfs(long long nextNum,unsigned char flag357)
{
if(nextNum<=N)
{
if(flag357==07) // 07 is BIN 111
count++;
dfs(nextNum*10+3,flag357|01); // BIN 001
dfs(nextNum*10+5,flag357|02); // BIN 010
dfs(nextNum*10+7,flag357|04); // BIN 100
}
}
不用递归的话,可以用一个队列模拟这个过程
#include <cstdio>
#include <utility>
#include <vector>
#include <queue>
int main(void)
{
int N,x,flag,count;
std::queue<std::pair<int,int>> Q;
std::pair<int,int> p;
scanf("%d",&N);
x=0;
flag=0;
p.first=x;
p.second=flag;
count=0;
Q.push(p);
while(!Q.empty())
{
p=Q.front();
Q.pop();
x=p.first;
flag=p.second;
if(flag==7)
count++;
if(((long long)x)*10+3<=N)
{
p.first=x*10+3;
p.second=flag|01;
Q.push(p);
}
if(((long long)x)*10+5<=N)
{
p.first=x*10+5;
p.second=flag|02;
Q.push(p);
}
if(((long long)x)*10+7<=N)
{
p.first=x*10+7;
p.second=flag|04;
Q.push(p);
}
}
printf("%d\n",count);
return 0;
}