P1980 [NOIP2013 普及组] 计数问题
阅读原文时间:2023年07月15日阅读:1

题目链接:https://www.luogu.com.cn/problem/P1980

术语

以下的英文术语均可以翻译为数字。

  • digit: 一个数字字符,十进制就是 0-9 之间的一个字符;
  • numeral: 用来表示数字的符号化表示,如 “Three”、“3”、“III”;
  • number: 一种抽象的数字概念。

为了区分,下文中均使用英文术语。

注意:关于 numeral 和 number 区别见: 如何在英文写作中正确的表达数字?

十进制数表示法

十进制数(decimal numeral)由一串有限长度的 digit 序列组成,

\[a_ma_{m-1}\ldots a_0
\]

其中,\(a_i \in \{0,1,2,3,4,5,6,7,8,9\}\)。

numeral \(a_ma_{m-1}\ldots a_0\) 表示了 number \(a_m10^m+a_{m-1}10^{m-1}+\cdots+a_{0}10^0\)。

注意:关于十进制数的详细介绍见 Wikipedia Decimal

前置 \(0\)

为简化问题,我们假设我们的 numeral 可以出现前置 \(0\),即,从最左侧开始,可以出现多个连续的 \(0\),如 \(03\),\(003\)。通过前置 \(0\), 我们可以使用三个 digit 来包含一位数、二位数、三位数的 number

三个 digit

为简化问题,我们目前只考虑三位数之内的 number,且忽略 \(n\)(目前可视作 \(n = 999\),用来包含所有的一位数、二位数、三位数)。

根据题目,我们需要统计出 digit \(x\) 在所有 numeraldigit 中出现的次数。这里我们列出部分的 numeral

\[\begin{array}
{c|c|c}
a_2&a_1&a_0\\
\hline
0&0&0\\
0&0&1\\
0&0&2\\
0&0&3\\
\vdots&\vdots&\vdots\\
9&9&6\\
9&9&7\\
9&9&8\\
9&9&9\\
\end{array}
\]

令 \(C_i\) 等于第 \(i\) 位上 \(x\) 出现的总次数,那么\(x\) 在所有 numeraldigit 中出现的次数为 \(S=\sum_{i=0}^2C_i\)。

我们通过 \(x = 1\) 来进行说明。首先我们令 \(a_2 = 1\),此时百位上的数字已经固定,\(a_1\) 和 \(a_0\) 分别有 \(0\) 到 \(9\) 十种可能,且彼此互不影响,所以 \(C_2 = 10 \times 10 = 100\),同理我们得到 \(C_0=C_1=100\)。从而,我们最终得到 \(S=100+100+100=300\)。

通过上面的方式,我们可以得到任意 \(x\) 对应的 \(S\)。

注意:digit \(0\) 比较特殊,我们这里暂时未考虑。

考虑 \(n\) 呢?

上面的问题只看 digit 的个数,但忽略了 \(n\)。如果我们也要将 \(n\) 考虑在内呢?

这里以 \(n=123\),\(x=3\) 进行举例。首先我们可以知道 \(a_2 = 3\) 是不可能的,所以此时 \(C_2 = 0\)。下面我们考虑 \(a_1 = 3\),此时 \(a_2\) 必须小于 \(1\), 所以只有 \(a_2 = 0\) 一种可能,由于向前面借了一位, \(a_0\) 可以包含 \(0\) 到 \(9\) 十种可能,从而我们得到 \(C_1 = 10\)。然后我们考虑 \(a_0 = 3\),当 \(a_2 = 1\) 时,需满足 \(a_1 \leqslant 2\);当 \(a_2 = 0\) 时,\(a_1\) 可以包含 \(0\) 到 \(9\) 十种可能,加起来我们有 \(C_0 = 3 + 10 = 13\) 种可能。最终,我们得到 \(S=0+10+13=23\)。

这里以 \(n=123\),\(x=2\) 进行举例。首先我们可以知道 \(a_2 = 2\) 是不可能的,所以此时 \(C_2 = 0\)。下面我们考虑 \(a_1 = 2\),此时 \(a_2\) 有 \(0\) 和 \(1\) 两种可能,当 \(a_2 = 1\), 需满足 \(a_1 \leqslant 3\);当 \(a_2 = 0\), \(a_1\) 可以包含 \(0\) 到 \(9\) 十种可能,从而我们得到 \(C_1 = 4 + 10 = 14\)。然后我们考虑 \(a_0 = 2\),当 \(a_2 = 1\) 时,需满足 \(a_1 \leqslant 2\);当 \(a_2 = 0\) 时,\(a_1\) 可以包含 \(0\) 到 \(9\) 十种可能,加起来我们有 \(C_0 = 3 + 10 = 13\) 种可能。最终,我们得到 \(S=0+14+13=27\)。

这里以 \(n=123\),\(x=1\) 进行举例。首先我们令 \(a_2=1\),当 \(a_1=2\) 时,需满足 \(a_0 \leqslant 3\);当 \(a_1 \leqslant 1\) 时,\(a_0\) 可以包含 \(0\) 到 \(9\) 十种可能,故 \(C_2 = 4 + 10 + 10 = 24\)。下面我们考虑 \(a_1 = 1\),此时 \(a_2\) 有 \(0\) 和 \(1\) 两种可能,当 \(a_2 \leqslant 1\), \(a_0\) 可以包含 \(0\) 到 \(9\) 十种可能,从而我们得到 \(C_1 = 10 + 10 = 20\)。然后我们考虑 \(a_0 = 1\),当 \(a_2 = 1\) 时,需满足 \(a_1 \leqslant 2\);当 \(a_2 = 0\) 时,\(a_1\) 可以包含 \(0\) 到 \(9\) 十种可能,加起来我们有 \(C_0 = 3 + 10 = 13\) 种可能。最终,我们得到 \(S=24+20+13=57\)。

我们发现上面的统计方式,通过程序来处理的话比较麻烦,最好一种统一的方式来处理各种情况,

移除 digit \(x\),再看看!

  • \(x > a_i\),

    当 \(x > a_i\),我们令 \(a_{i-1} \gets a_{i-1} - 1\),\(a_k \gets 9 \text{ for } k > i\)。比如对于 \(n = 123\), \(x=3\),\(i = 2\),我们得到 \(039\),我们移除 \(a_2\) 得到 \(09\),在对 \(09 + 1\) 得到 \(10\),我们发现这正好等于 \(C_2\);

  • \(x = a_i\),

    当 \(x = a_i\),不进行额外操作。比如对于 \(n = 123\), \(x=2\),\(i = 2\),我们得到 \(123\),我们移除 \(a_2\) 得到 \(13\),在对 \(13 + 1\) 得到 \(14\),我们发现这也正好等于 \(C_2\);

  • \(x < a_i\),

    当 \(x = a_i\),我们令 \(a_k \gets 9 \text{ for } k > i\)。比如对于 \(n = 123\), \(x=1\),\(i = 2\),我们得到 \(119\),我们移除 \(a_2\) 得到 \(19\),在对 \(19 + 1\) 得到 \(20\),我们发现这又正好等于 \(C_2\)。

上面的方法可以总结为,

  1. 首先判断 \(x\) 和 \(a_i\) 的大小关系;
  2. 根据判断结果来对其他的 digit 进行修改;
  3. 移除 \(x\) 对应的 \(a_i\),得到一个新的 numeral
  4. 计算 numeral 对应的 number
  5. 最后在对得到的结果 \(+1\) 即可。

注意:如果 \(a_i\) 最高位,且 \(x > a_i\),那么此时没有可以借位的 digit,所以 \(C_i = 0\)。

注意:digit \(0\) 比较特殊,我们这里暂时未考虑。

多出来 \(0\)?

如果我们按照前面的方法对 \(x = 0\) 进行统计,我们会发现 \(0\) 的次数被多统计了一些。

为了解释这个问题,这里我们再次以三个 digitnumeral 进行说明。

对于任意一个三位数的 \(n\),我们之前的方法会把所有有一个前置 \(0\) 和有两个前置 \(0\) 的 numeral 包含进来,比如 \(010\),\(001\)。而这些前置 \(0\) 实际上不应该被统计进来,为了得到正确的答案,我们可以在最终结果的地方减去多统计的前置 \(0\) 。

前置 \(0\) 的个数为 \(a_2 = 0\) 的 numeral 个数,以及 \(a_2=0\) 同时 \(a_1 = 0\) 的numeral 个数,因为题目中 number 不包含 \(0\),所以我们最终还要加上 \(a_2=0\) 同时 \(a_1 = 0\) 同时 \(a_0 = 0\) 的情况。最终我们可以得到多统计的前置 \(0\) 个数为 \(100 + 10 + 1 = 10^2 + 10^1 + 10^0 = 111\)。

由此我们可以推广 \(m\) 个 digitnumeral 多统计的前置 \(0\) 为 \(\sum_{i=0}^{m-1} 10^i\)。

结论

  • \(x \ne 0\) 时,采用移除 digit \(x\) 的方法即可。
  • \(x = 0\) 时,采用移除 digit \(x\) 方法的同时还需要减去多余的前置 \(0\)。

代码如下:

// https://www.luogu.com.cn/problem/P1980
// https://www.cnblogs.com/revc/p/17087297.html

#include <iostream>
#include <cmath>

int main()
{
    int n, x;

    std::cin >> n >> x;

    int digits[7];

    int m = 0;  // the number of digits
    while(n > 0) // NOTE: store digits in reverse order
    {
        digits[m++] = n % 10;
        n /= 10;
    }

    int S = 0;
    for (int i = 0; i < m; i++)
    {
        int C = 0;
        int borrow = 0;
        if (x > digits[i])
        {
            if (i+1 == m) continue; /* fail to borrow */
            borrow = 1;
            digits[i+1]--;
        }

        for (int j = m - 1; j > i; j--)
        {
            C = C * 10 + digits[j];
        }

        for (int j = i - 1; j >= 0; j--)
        {
            C = C * 10 + (digits[i]==x ? digits[j] : 9);
        }

        digits[i+1] += borrow;
        S += C + 1;
    }

    if (x == 0)
    {
        int subtrahend = 1;
        while(m--)
        {
            S -= subtrahend;
            subtrahend *= 10;
        }
    }

    std::cout << S << std::endl;

    return 0;
}

手机扫一扫

移动阅读更方便

阿里云服务器
腾讯云服务器
七牛云服务器

你可能感兴趣的文章