题目描述

给定两个正整数 $n$ 和 k，求从 $1$ 到 $n$ 这 $n$ 个正整数的十进制表示中 $k$ 出现的次数。

输入格式

共一行，包含两个整数 $n$ 和 $k$。

输出格式

输出一个整数，表示答案。

数据范围

$1 \le n \le 10 ^ 6,$
$1 \le k \le 9$

输入样例：

12 1

输出样例：

5

样例解释

从 1 到 12 这些整数中包含 1 的数字有 1,10,11,12，一共出现了 5 次 1。

解题思路

法一（暴力）：191ms

我们可以从 $1$ 遍历到 $n$，分别统计每个数中 $k$ 出现的次数。

怎么统计一个数 $x$ 中 $k$ 出现的次数呢？我们可以不断取 $x$ 的末尾，判断它是否为 $k$，再把 $x$ 除以 $10$（舍弃末位）。

// 核心代码
int count (int x, int k) // 统计一个数 x 中 k 出现的次数
{
    int res = 0;
    while (x)
    {
        res += x % 10 == k, x /= 10; // 判断末位是否为 k，舍弃末位
    }
    return res;
}

这样一直把函数结果累加到答案上，最后输出答案即可。

时间复杂度：$\Theta (n \log n)$。

法二（递归）：241ms

与法一一致，只不过 count 函数变成了递归函数。

int count (int x, int k)
{
    return x ? count (x / 10, k) + (x % 10 == k) : 0;
}

时间复杂度：$\Theta (n \log n)$。

法三（记忆化 搜索 递归）：83ms

与法二差不多，只是多了个数组用来记忆化。$f _ i$ 表示 $i$ 中含有几个 $k$。即数组有存结果就用数组的结果，没有则再计算一遍存进数组。

int f[N];
bool v[N] = {1};

int count (int x, int k)
{
    if (v[x])
    {
        return f[x];
    }
    f[x] = count (x / 10, k) + (x % 10 == k), v[x] = 1;
    return f[x];
}

时间复杂度：理论上 $\Theta (n)$。

法四（数位 DP）：63ms

$f _ i$ 表示 $i$ 中含有几个 $k$。观察可得到转移方程 $f _ i = f _ {\big \lfloor {i \over 10} \big \rfloor} + b _ {i \bmod 10}$，其中 $b _ j$ 为 $j$ 是否等于 $k$（$0 \le j \le 9$）。如此递推即可。

for (int i = 1; i <= n; i ++)
{
    f[i] = f[i / 10] + (i % 10 == k);
}

时间复杂度：$\Theta (n)$。

法五（数学）：11ms

这个比较难理解。首先依次考虑 $ 1 \sim n$ 的每一位，从右往左数第 $i$ 上的 $1$ 的个数为：

• 首先考虑完整的一段，如 $\begin {cases} n = 304 \\\ k = 1 \\\ i = 3 \end {cases}$ 中的 $100 \sim 199$，百位都为 $1$。完整的一段中 $k$ 的个数为 $10 ^ {i - 1}$，$1 \sim n$ 中有 $\lfloor {n \over 10 ^ i} \rfloor$ 个完整的段。因此完整的段中有 $10 ^ {i - 1} \times \lfloor {n \over 10 ^ i} \rfloor$个 $k$。

• 然后考虑可能存在的不完整的段，如 $\begin {cases} n = 2118 \\\ k = 1 \\\ i = 3 \end {cases}$，中的 $2100 \sim 2118$，百位都为 $1$。我们观察发现不完整的段一定出现在末尾，且只有一段。我们需分 $3$ 种情况讨论：

• 当 $0 \le n \bmod 10 ^ i < 10 ^ {i - 1} \times k$ 时，即第 $i$ 位没有不完整的一段，个数为 $0$。

• 当 $10 ^ {i - 1} \times k \le n \bmod 10 ^ i < 10 ^ {i - 1} \times (k + 1)$ 时，即第 $i$ 位有不完整的一段，个数为 $n \bmod 10 ^ i - 10 ^ {i - 1} \times k + 1$。
• 当 $10 ^ {i - 1} \times (k + 1) \le n \bmod 10 ^ i < 10 ^ i$ 时，即第 $i$ 为后面“不完整的一段”其实是完整的，个数为 $10 ^ {i - 1}$。

这三个式子可以用一个 $\max$ 和一个 $\min$ 连成一个式子，即个数为 $\max \{\min \{n \bmod 10 ^ i - 10 ^ {i - 1} \times k + 1, 10 ^ {i - 1}\}, 10 ^ {i - 1}\}$。

放代码：

// nn = n, p 表示 10 ^ (i - 1)
while (nn) // nn 用来遍历 n 的位数遍
{
    ans += n / p / 10 * p + max (min (n % (p * 10) - p * k + 1, p), 0);
    p *= 10, nn /= 10; // 更新 p 和 nn
}

时间复杂度：$\Theta (\log n)$。

AC Code

法一（350B）

#include <iostream>
using namespace std;

int n, k, ans;

int count (int x, int k) // 统计一个数 x 中 k 出现的次数
{
    int res = 0;
    while (x)
    {
        res += x % 10 == k, x /= 10;
    }
    return res;
}

int main ()
{
    cin >> n >> k;
    for (int i = 1; i <= n; i ++)
    {
        ans += count (i, k); // 累加答案
    }
    cout << ans;
    return 0;
}

法二（300B）

#include <iostream>
using namespace std;

int n, k, ans;

int count (int x, int k)
{
    return x ? count (x / 10, k) + (x % 10 == k) : 0;
}

int main ()
{
    cin >> n >> k;
    for (int i = 1; i <= n; i ++)
    {
        ans += count (i, k);
    }
    cout << ans;
    return 0;
}

法三（400B）

#include <iostream>
#define N 1000005
using namespace std;

int n, k, ans, f[N];
bool v[N] = {1};

int count (int x, int k)
{
    if (v[x])
    {
        return f[x];
    }
    f[x] = count (x / 10, k) + (x % 10 == k), v[x] = 1;
    return f[x];
}

int main ()
{
    cin >> n >> k;
    for (int i = 1; i <= n; i ++)
    {
        ans += count (i, k);
    }
    cout << ans;
    return 0;
}

法四（250B）

#include <iostream>
#define N 1000005
using namespace std;

int n, k, ans, f[N];

int main ()
{
    cin >> n >> k;
    for (int i = 1; i <= n; i ++)
    {
        f[i] = f[i / 10] + (i % 10 == k), ans += f[i];
    }
    cout << ans;
    return 0;
}

法五（300B）

#include <iostream>
using namespace std;

int n, k, nn, p = 1, ans;

int main ()
{
    cin >> n >> k, nn = n;
    while (nn)
    {
        ans += n / p / 10 * p + max (min (n % (p * 10) - p * k + 1, p), 0);
        p *= 10, nn /= 10;
    }
    cout << ans;
    return 0;
}

感谢观看！

上一篇

下一篇

$$\href {/blog/content/29204/} {\color {DarkOrchid} {【寒假每日一题】题解}}$$