753数[AtCoder-4276]简析

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

发表回复

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