P8680 [蓝桥杯 2019 省 B] 特别数的和

[蓝桥杯 2019 省 B] 特别数的和

题目描述

小明对数位中含有 2、0、1、9 的数字很感兴趣（不包括前导 0），在 1 到 40 中这样的数包括 1、2、9、10 至 32、39 和 40，共 28 个，他们的和是 574。

请问，在 1 到 n 中，所有这样的数的和是多少？

输入格式

输入一行包含一个整数 n。

输出格式

输出一行，包含一个整数，表示满足条件的数的和。

样例 #1

样例输入 #1

40

样例输出 #1

574

提示

对于 20% 的评测用例，1 ≤ n ≤ 10。

对于 50% 的评测用例，1 ≤ n ≤ 100。

对于 80% 的评测用例，1 ≤ n ≤ 1000。

对于所有评测用例，1 ≤ n ≤ 10000。

蓝桥杯 2019 省赛 B 组 F 题。

分析

本题最简单的解决方法就是暴力破解了，直接对每一个数进行判断，是否含有2、0、1、9四个数字

提交答案

#include <cstdio>
bool judge(int x){
    int t ;
    while(x){
        t = x % 10 ;
        if (t == 2 || t == 0 || t == 9 || t == 1)
            return true ;
        else
            x /= 10 ;
    }
    return false ;
}
int main(){
    int n , sum = 0 ;
    scanf("%d" , &n) ;
    for(int i = 1 ; i <= n ; ++ i){
        if(judge(i))
            sum += i ;
    }
    printf("%d\n" , sum) ;
    return 0 ;
}

以下为非暴力解法，比较麻烦
本题是有规律可循的，上面的代码解法简单。但是符合要求的数仅仅只包含两种 特别数在个位的的，即51 ， 52 ， 60等 特别数字不在个位的，如15 ， 28 ， 95等。因此暴力破解的方法中有超过半数的判断是没有必要的。
所以我们可以将数字分为十个一组，选取其中一个进行判断，如果除去个位含有特别数，则这一组数都是符合要求的，否则这十个数仅有四个符合要求。这里我选取的是从0~9为一组，代码如下：

#include <cstdio>
bool judge(int x){
    int t ;
    while(x){
        t = x % 10 ;
        if (t == 2 || t == 0 || t == 9 || t == 1)
            return true ;
        else
            x /= 10 ;
    }
    return false ;
}
int main(){
    int n , sum = 0 , t , b ;
    scanf("%d" , &n) ;
    //for中每次操作都是对一组数进行操作，所以要排除n所在的一组和第一组
    for(int i = 1 ; i < n && n >= 10 ; i += 10){
        if(judge(i / 10))
            sum += i * 10 + 35 ;
        else
            sum += i * 4 + 8 ;
    }
    b = n / 10 * 10 ;
    //判断n除去个位数是否含有特别的数，如果含有，则这组数中<=n的都符合要求
    if(judge(n / 10))
        for(int i = b ; i <= n ; ++ i)
            sum += i ;
    //如果n除去个位不含特殊数，则判断最后一组数中含有哪些特殊数
    else{
        t = n % 10 ;
        if(t < 9){
            if(t < 2){
                if(t < 1)
                    sum += b ;
                else
                    sum += b * 2 + 1 ;
            }
            else
                sum += b * 3 + 3 ;
        }
        else
            sum += b * 4 + 12 ;
    }
    printf("%d" , sum) ;
    return 0 ;
}