计数问题

P1179 [NOIP2010 普及组] 数字统计
题目描述
请统计某个给定范围[L,R]的所有整数中，数字2出现的次数。

比如给定范围[2,22]，数字2在数2中出现了1次，在数12中出现1次，在数20中出现1次，在数21中出现>1次，在数22中出现2次，所以数字2在该范围内一共出现了6次。

输入格式
2个正整数L和R，之间用一个空格隔开。

输出格式
数字2出现的次数。
说明/提示
1≤L≤R≤100000

1. 枚举法

只要遍历\([L,R]\)的每个数的每位数字进行统计就可得到答案，复杂度是\(O(nlogn)\)。

完整代码

#include <iostream>
using namespace std;
int main(){
    int l,r;
    cin>>l>>r;
    int cnt = 0;
    for(int i = l;i<=r;i++){
        int tmp = i;
        while(tmp){
            if(tmp%10 == 2) cnt++;
            tmp/=10;
        }
    }
    cout<<cnt<<endl;
    return 0;
}

这个复杂度对于这道题的数据量而言已经够了，但是数据量超过 \(10^8\) 量级后就不可接受了，需要用到公式法。

2.公式法

假设 \(f(n,num)\) 是从 \([1,n]\) 所有整数出现数字 \(num\) 的次数和，那么想要得到 \([L,R]\) 内所有整数出现数字 \(num\) 的次数和可以通过 \(f(r,num)-f(l-1,num)\) 得到，其中 \(0\leq num\leq 1\) 。

我们可以通过考虑每位数字得到 \(f(n,num)\) :

\(1\leq num\leq 9\) 的情况

假设一个 \(p\) 位正整数 \(n\) 的数位构成情况为 \(\overline{n_{p-1}n_{p-2}\cdots n_1n_0}\) ，其中 \(n_i\) 是第 \(i\) 位数的数字 \((0\leq i\leq p-1)\) 。
考虑 \([1,n]\) 中某个数 \(m\) 其 \(p\) 位构成情况为 \(\overline{m_{p-1}m_{p-2}\cdots m_1m_0}\) (不够p位数可以补前导0)。

1. \(n_i<num\)

• 若 \(m\) 的 \(i+1\) 到 \(p-1\) 位的数字构成的新数小于 \(n\) 的 \(i+1\) 到 \(p-1\) 位的数字构成的新数，即 $$\overline{m_{p-1}\cdots m_{i+1}}<\overline{n_{p-1}\cdots n_{i+1}}$$
  那么 \(m\) 可以满足 \(m_i=num\) 且无论第 \(i-1\) 位及以后的数字如何也一定在 \([1,n]\) 中。
• 当 $$\overline{m_{p-1}\cdots m_{i+1}}\geq \overline{n_{p-1}\cdots n_{i+1}}$$ 因为 \(ni<num\) ，如果此时使 \(m_i=num\) ，那么 $$\overline{m_{p-1}\cdots m_{i+1}m_i}>\overline{n_{p-1}\cdots n_{i+1}n_i}$$ 则无论 \(m\) 第 \(i-1\) 位及以后的数字如何都会 \(m>n\) 从而不在 \([1,n]\) 的范围中。
• 综上，当 \(n_i<num\) 只有 $$\overline{m_{p-1}\cdots m_{i+1}}<\overline{n_{p-1}\cdots n_{i+1}}$$ 时成立，且此时 \([1,n]\) 第 \(i\) 位出现 \(num\) 的次数为 $$\overline{n_{p-1}\cdots n_{i+1}}\times10^i$$

2. \(n_i=num\)

• 当 $$\overline{m_{p-1}\cdots m_{i+1}}<\overline{n_{p-1}\cdots n_{i+1}}$$ 时，次数 $$\overline{n_{p-1}\cdots n_{i+1}}\times 10^i$$ 显然成立。
• 当 $$\overline{m_{p-1}\cdots m_{i+1}}=\overline{n_{p-1}\cdots n_{i+1}}$$时，若 \(m\) 满足 \(m_i=num\) ，那么只要 $$\overline{m_{i-1}\cdots m_0}\leq \overline{n_{i-1}\cdots n_0}$$ 即可，此时次数为 $$\overline{n_{i-1}\cdots n_0}+1$$ 我们约定 \(i=0\) 时，$$\overline{n_{i-1}\cdots n_0}=0$$
• 当 $$\overline{m_{p-1}\cdots m_{i+1}}> \overline{n_{p-1}\cdots n_{i+1}}$$ 那么无论 \(m\) 第 \(i-1\) 位及以后的数字如何都会 \(m>n\) ，从而不在 \([1,n]\) 的范围中。
• 综上，当 \(n_i\geq num\) 只有 $$\overline{m_{p-1}\cdots m_{i+1}}\leq \overline{n_{p-1}\cdots n_{i+1}}$$ 时成立，且此时 \([1,n]\) 第 \(i\) 位出现 \(num\) 的次数为 $$\overline{n_{p-1}\cdots n_{i+1}}\times 10^i+\overline{n_{i-1}\cdots n_0}+1$$

3. \(n_i>num\)

• 当 $$\overline{m_{p-1}\cdots m_{i+1}}<\overline{n_{p-1}\cdots n_{i+1}}$$ 时，次数 $$\overline{n_{p-1}\cdots n_{i+1}}\times 10^i$$ 显然成立；
• 当 $$\overline{m_{p-1}\cdots m_{i+1}}=\overline{n_{p-1}\cdots n_{i+1}}$$时，因为 \(n_i>num\) ，若使 \(m_i=num\),则 $$\overline{m_{p-1}\cdots m_{i+1}m_i}<\overline{n_{p-1}\cdots n_{i+1}n_i}$$ 从而无论第 \(i-1\) 位及以后的数字如何也一定在 \([1,n]\) 中，次数为 \(10^i\) 。
• 当 $$\overline{m_{p-1}\cdots m_{i+1}}> \overline{n_{p-1}\cdots n_{i+1}}$$ 那么无论 \(m\) 第 \(i\) 位及以后的数字如何都会 \(m>n\) ，从而不在 \([1,n]\) 的范围中。
• 综上，当 \(n_i\geq num\) 只有 $$\overline{m_{p-1}\cdots m_{i+1}}\leq \overline{n_{p-1}\cdots n_{i+1}}$$ 时成立，且此时 \([1,n]\) 第 \(i\) 位出现 \(num\) 的次数为 $$(\overline{n_{p-1}\cdots n_{i+1}}+1)\times 10^i$$

\(num=0\)的情况

这种情况下，我们知道如果某一位是 \(0\) ，那么这个整数一定有不为 \(0\) 的更高位，就需要排除在上一种情况下 \(\overline{m_{p-1}\cdots m_{i+1}}=0\) 的一种可能了。显然在三个可能的 \(num\) 和 \(n_i\)关系下，都可能出现这种情况，所以在每次计算完之后需要减去一个关于 \(\overline{n_{p-1}\cdots n_{i+1}}\) 的所有情况，即减去 \(10^i\) 。

运用以上的结论，每次只需要遍历一次两个端点的位数，是 \(O(logn)\)的算法。

完整代码

#include <iostream>
#define ll long long

using namespace std;

ll f(ll n,ll num){
    ll base = 1,cnt = 0;
    while(base<=n){
        ll pre = n/(base*10);
        ll suf = n%base;
        ll now = n/base%10;
        if(now<num) cnt+=pre*base;
        else if(now == num) cnt+=pre*base + suf + 1;
        else cnt+=(pre+1)*base;
        if(!num) cnt-=base;
        base*=10;
    }
    return cnt;
}

int main(){
    std::ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    ll l,r;
    cin>>l>>r;
    cout<<f(r,2)-f(l-1,2)<<endl;
}