NOIP2013数字统计：暴力枚举与数位处理技巧

1. 题目背景与需求解析

这道来自NOIP2013普及组的计数问题，考察的是选手对数字处理和循环结构的掌握能力。题目要求统计在1到n的所有整数中，数字x（0≤x≤9）出现的总次数。看似简单的需求背后，实际上隐藏着几个需要特别注意的边界条件。

1.1 问题重述与示例分析

题目给出两个整数n和x，要求计算从1到n的所有整数中，数字x出现的次数。例如当n=11，x=1时：

• 1出现1次（数字1）
• 10出现1次（十位上的1）
• 11出现2次（十位和个位的1）
  总次数为1+1+2=4次

1.2 核心考察点

这道题主要考察三个方面的能力：

1. 数字的逐位处理能力
2. 循环结构的正确使用
3. 边界条件的处理（特别是x=0的情况）

注意：当x=0时，需要特别注意数字的最高位不可能为0，这会影响统计逻辑

2. 解题思路与算法选择

2.1 暴力枚举法

最直观的解法是对1到n的每个数字进行逐位检查：

python复制count = 0
for i in range(1, n+1):
    while i > 0:
        if i % 10 == x:
            count += 1
        i = i // 10

这种方法时间复杂度为O(nlogn)，对于n≤1,000,000的数据规模完全够用。

2.2 数学规律法

更高效的解法是利用数位DP的思想，通过数学规律计算每个数位上x出现的次数。这种方法可以将时间复杂度降到O(logn)，但对于普及组题目来说，暴力法已经足够。

3. 代码实现与细节处理

3.1 C++实现示例

cpp复制#include <iostream>
using namespace std;

int main() {
    int n, x, count = 0;
    cin >> n >> x;
    
    for (int i = 1; i <= n; ++i) {
        int num = i;
        while (num > 0) {
            if (num % 10 == x) {
                count++;
            }