题目链接

好奇的薯队长

题目描述

输入一个正整数 （），计算从 到 （包括 ）的所有整数中，数字 '1' 一共出现了多少次。

例如，对于 ，包含 '1' 的数字有 。它们含 '1' 的个数分别为 ，总计 个。

解题思路

这是一个典型的数位 DP 问题。如果直接从 遍历到 ，对每个数进行判断，当 很大时会导致超时。正确的做法是按位来统计数字 '1' 出现的次数。

我们可以从个位开始，依次统计个位、十位、百位……上出现 '1' 的总次数，然后将它们相加。

对于任意一个数 ，当我们分析其中某一位（假设其位值为 ，例如，个位 ，十位 ，百位 ）时，我们可以将 拆分为三部分：

  • high: 高位部分。high = n / (p * 10)。

  • current: 当前位上的数字。current = (n / p) % 10。

  • low: 低位部分。low = n % p。

例如，当 并且我们分析十位时 ()：

  • high = 132 / 100 = 1

  • current = (132 / 10) % 10 = 3

  • low = 132 % 10 = 2

现在，我们来分析在十位上出现 '1' 的情况：

  1. 高位部分决定的 '1' 的数量：

    当高位从 到 high - 1 (即 ) 时，当前位都可以是 '1'，而低位可以是任意数字 ( 到 )。

    • 高位为 时，十位是 '1' 的数有 10-19。

    • 总共有 high 种高位情况，每种情况下低位都有 种可能（ 到 ）。

    • 所以这部分的贡献是 high * p。

  2. 当前位数字 current 决定的 '1' 的数量：

    当高位固定为 high (即 ) 时，情况取决于 current 的值：

    • 如果 current > 1 (例如 , current=3): 十位是 '1' 的情况已经完整地出现了一个周期，即从 110 到 119。这又贡献了 次。

    • 如果 current == 1 (例如 , current=1): 十位是 '1' 的情况只出现了部分，即从 110 到 112。这部分贡献的次数由低位 low 决定，共 low + 1 次。

    • 如果 current < 1 (即 current=0): 高位为 high 时，当前位不可能是 '1'（否则数就大于 了），所以没有贡献。

总结公式：

对于位值 ，'1' 在该位上出现的总次数为：

  • count = high * p

  • 如果 current == 1，则 count += low + 1

  • 如果 current > 1，则 count += p

我们从 开始循环，每次令 ，直到 ，将每一位计算出的 count 累加起来即可得到最终答案。

代码

#include <iostream>

using namespace std;
using ll = long long;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    ll n;
    cin >> n;

    ll total_ones = 0;
    ll p = 1; // p 是位值，1, 10, 100...

    while (p <= n) {
        ll high = n / (p * 10);
        ll current = (n / p) % 10;
        ll low = n % p;

        total_ones += high * p;
        
        if (current == 1) {
            total_ones += low + 1;
        } else if (current > 1) {
            total_ones += p;
        }

        // 防止 p*10 溢出
        if (p > n / 10) {
            break;
        }
        p *= 10;
    }

    cout << total_ones << endl;

    return 0;
}

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        long n = sc.nextLong();

        long totalOnes = 0;
        long p = 1; // p 是位值，1, 10, 100...

        while (p <= n) {
            long high = n / (p * 10);
            long current = (n / p) % 10;
            long low = n % p;

            totalOnes += high * p;

            if (current == 1) {
                totalOnes += low + 1;
            } else if (current > 1) {
                totalOnes += p;
            }

            // 防止 p * 10 溢出
            if (p > n / 10) {
                break;
            }
            p *= 10;
        }

        System.out.println(totalOnes);
    }
}

import sys

def solve():
    try:
        n_str = sys.stdin.readline()
        if not n_str:
            return
        n = int(n_str)
        
        total_ones = 0
        p = 1 # p 是位值，1, 10, 100...
        
        while p <= n:
            high = n // (p * 10)
            current = (n // p) % 10
            low = n % p
            
            total_ones += high * p
            
            if current == 1:
                total_ones += low + 1
            elif current > 1:
                total_ones += p
            
            p *= 10
        
        print(total_ones)

    except (IOError, ValueError):
        return

solve()

算法及复杂度

  • 算法：数位 DP、数学

  • 时间复杂度： 或 。循环的次数等于 的十进制位数。

  • 空间复杂度：。只使用了有限个变量来存储中间结果。