第十屆藍橋杯大賽-特別數的和-C++

解法一（暴力獲取）：

#include<stdio.h>
#include<stdlib.h>

int main(void)
{
    int n;
    int times = 0;
    int num = 0;

    printf("輸入整數n: ");
    scanf("%d", &n);

    for(int i = 0; i <= n; i++)
    {
        for(int temp = i; temp > 0; temp = temp / 10)
        {
            if(temp % 10 == 0 || temp % 10 == 1 || temp % 10 == 2 || temp % 10 == 9)
            {
                times++;
                num += i;
                break;
            }
        }
    }

    printf("%d\n", times);
    printf("%d\n", num);
    
    printf("\n");
    system("pause");
}

 解法二：

解題計算思路

實作代碼：

#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<string.h>

int get_level(int n)  // 獲取該整數的級別， <10, <100, ....
{
    int n_level = 0;

    while(n)
    {
        n_level++;
        n /= 10;
    }

    return n_level;
}

int get_sum(int level) // 獲取 1+ 2+ 3 + 4 + ...  的值
{
    int sum = 0;
    for(int i = 1; i < pow(10.0, level - 1); i++)
    {
        sum += i;
    }
    return sum;
}

int main(void)
{
    long long **info;  
    // info[i][j]    
    // j 代表相應位數的資訊， 例如 j = 1代表個位數級， j = 2代表十位數級
    // i = 0 存放著總數量和總和
    // i = 1 代表對應位數中符合條件的數字的數量
    // i = 2 代表對應位數中符合條件的數字的和
    int n;
    int n_level;
    int special_number[4] = {0, 1, 2, 9};  // 存放那些特殊的值
    //獲取 1+ 2+ 3 + 4 + ... + 9 的值
    int sum;  // 存盤 1+ 2+ 3 + 4 + ... 的總和值


    printf("輸入整數n: ");
    scanf("%d", &n);

    n_level = get_level(n);

    // 建立相應的二維陣列
    info = (long long **)malloc(3 * sizeof(long long *));
    for(int i = 0; i <= 2; i++)
    {
        info[i] = (long long *)malloc((n_level + 1) * sizeof(long long));
        // 初始化其值為 0
        memset(info[i], 0, (n_level + 1) * sizeof(long long));
    }

    // 數值累計
    for(int temp_level = 1; temp_level <= n_level; temp_level++)
    {
        sum = get_sum(temp_level);
        if(temp_level == 1)
        {
            for(int i = 0; special_number[i] <= n && i < 4; i++)
            {//依次加 0, 1, 2, 9
                info[1][temp_level]++;
                info[2][temp_level] += special_number[i];
            }
        }
        else{
            for(int i = 1; i * pow(10.0, temp_level - 1) <= n  && i < 10; i++)
            {
                if(((i + 1) * pow(10.0, temp_level - 1) < n) && (i == 1 || i == 2 || i == 9))
                {// 符合條件時，將該位所有數值都加起來
                    // 將數值拆開 先計算最高位數上的值的和，再計算除了最高位數上其他的數值和
                    info[1][temp_level] += pow(10.0, temp_level - 1);
                    info[2][temp_level] += sum + i * pow(10.0, temp_level - 1) * pow(10.0, temp_level - 1); 
                }
                else if((i + 1) * pow(10.0, temp_level - 1) < n)
                {
                    if(temp_level == 2)
                    {
                        info[1][temp_level] += info[1][temp_level - 1];
                        info[2][temp_level] += info[2][temp_level - 1] + i * pow(10.0, temp_level - 1) * info[1][temp_level - 1];
                    }
                    else
                    {
                        info[1][temp_level] += info[1][temp_level - 1] + pow(10.0, temp_level - 2);
                        info[2][temp_level] += info[2][temp_level - 1] + i * pow(10.0, temp_level - 1) * (info[1][temp_level - 1] + pow(10.0, temp_level - 2)) + get_sum(temp_level - 1);
                    }
                }
                else
                {// 逐個加
                    for(int temp_n = i * pow(10.0, temp_level - 1); temp_n <= n && temp_n < (i + 1) * pow(10.0, temp_level - 1); temp_n++)
                    {
                        for(int temp = temp_n; temp > 0; temp = temp / 10)
                        {
                            if(temp % 10 == 0 || temp % 10 == 1 || temp % 10 == 2 || temp % 10 == 9)
                            {
                                info[1][temp_level]++;
                                info[2][temp_level] += temp_n;
                                break;
                            }
                        }
                    }
                }
            }
        }
    }

    // 將所有總和加起來
    for(int temp_level = n_level; temp_level > 0; temp_level--)
    {
        info[1][0] += info[1][temp_level];
        info[2][0] += info[2][temp_level];
    }

    // 輸出總和結果
    printf("%d\n", info[1][0] - 1);
    printf("%d\n", info[2][0]);


    printf("\n");
    system("pause");
}

標籤：其他

上一篇：CodeForces - 1245D（思維+最小生成樹）

下一篇：CodeForces - 1250L（思維+貪心）